#OK to post homework
#Sam Minkin, 10/25, Assignment 13

QUESTION #1:

A = {s,a,m,u,e,l,i,n,k}

The consonants in A are s,m,l,n,k
The vowels in A are a,u,e,i

|A| = 9

(i) The total number 100-letter words in this alphabet is 9^100. 
The number of 100-letter words in this alphabet where two vowels can be adjacent is:
(99 choose 1)*9^98*5^2 = 99*9^98*5^2 since there are 5 consonants and 99 ways to group 2 adjacent letters.

So, the number of 100-letter words in this alphabet where no two consonants can be adjacent is 9^100 - 99 * 9^98 * 5^2.

(ii) Following the same reasoning as part (i), we have that:
There are 9^100 total 100-letter words
The number of 100-letters words in this alphabet which contains at least one adjacent pair of vowels is (99 choose 1)*9^98*4^2 = 99 * 9^98 * 4^2, since there are 4 vowels and 99 ways to group adjacent letters .

So, the number of 100-letter words in this alphabet where no two vowels can be adjacent is 9^100 - 99 * 9^98 * 4^2.

(iii) The number of 100-letter words in the alphabet which contain at least one adjacent pair of consonants and one adjacent pair of vowels are:
(99 choose 1)*(97 choose 1)*9^96*4^2*5^2 = 99*97*9^96*4^2*5^2 since there are 99 ways to pick 1 adjacent pair and then 97 ways to pick 1 adjacent pair from the remaining spots.

Based on the principle of inclusion and exclusion, we can find the number of 100-letter "words" in the alphabet where no two vowels can be adjacent and no consonants can be adjacent by subtracting the number of 100-letter words where no two consonants can be adjacent added to the number of 100-letter words where no two vowels can be adjacent and then adding back the overcomunted sequences which contain at least one pair of adjacent vowels and one adjacent pair of consonants: 

9^100 - (99*9^98*5^2 + 99*9^98*4^2) + 99*97*9^96*4^2*5^2

(iv) In general, we have that a(n) is given by:

9^n - n-1*9^(n-2)*(5^2 + 4^2) + (n-1)*(n-3)*9^(n-4)*4^2*5^2.

Running, add(a(n)*t^n,n=0..infinity) gives us:
f := 3694/2187 + 9*t + 2840/81*t^2 - 9*t^3 - 2202*t^4 - 31707*t^5 - 327564*t^6 - 2744685*t^7 - 17622846*t^8 - 47652543*t^9 + 994857552*t^10 + ...


QUESTION #2:

Write all the possible states:

Let f=farmer, s=sheep, c=cabbage, w=wolf

1:(fwsc, ), 
2:(ws,fc), (End)      6:(w,fcs) (End)
3:(wc,fs), 5:(fwc,s)  7:(c,fws) 8:(fc,ws) (End)
4:(sc,fw)  (End)                9:(fcs,w) 10:(c,fsw) (End)
					  11:(s,fcw) 12:(fs,cw) 13:( ,fscw) (Win)

So, the set of vertices is:
V = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}, where 14=Win and 15=End

We have the following directed graph:

G=[{2,3,4}, {15}, {5}, {15}, {6,7}, {15}, {8,9}, {15}, {10,11}, {15}, {12}, {13}, {14}, {}, {}]

Running, seq(Paths(G,1,14,k),k=4..15)) returns:
{[1, 3, 5, 7, 9, 11, 12, 13, 14]} Which is the way to win.


QUESTION #4:

Write all the possible states:

1:(MMMCCC, )-- 2:(MMMC,CC)-- 4
	    -- 3:(MMCC,MC)-- 4
	    -- 4:(MMMCC,C)--2,3,5:(MMM,CCC)--2--6:(MC,MMCC)--3--7:(CC,CMMM)--8:(CCC,MMM)--

	   9:(C,MMMCC)--7	
                      --6
                      --10:( ,MMMCCC)

So, the set of vertices is:
V = {1,2,3,4,5,6,7,8,9,10}, where 10=Win.

We have the following undirected graph:
G=[{2,3,4},{1,4,5,6},{1,4,6,7},{1,2,3,5},{2,4},{2,3,9},{3,8,9,10},{7,9,10},{7,6,8,10},{7,8,9}]

Running, seq(Paths(G,1,10,k),k=3)) returns:
{[1, 3, 7, 10]} which is a path to win.