#OK to post homework #William Wang, 10/19/2020, Assignment 13 #1. #A:={w,i,l,a,m,n,g} #Let w=1, i=2, l=3, a=4, m=5, n=6, g=7 #i. How many 100 letter "words" (i.e. sequences) in this alphabet are there where no two consonants can be adjacent? G1 := [{2, 4}, {1, 2, 3, 4, 5, 6, 7}, {2, 4}, {1, 2, 3, 4, 5, 6, 7}, {2, 4}, {2, 4}, {2, 4}]; G1 := [{2, 4}, {1, 2, 3, 4, 5, 6, 7}, {2, 4}, {1, 2, 3, 4, 5, 6, 7}, {2, 4}, {2, 4}, {2, 4}] normal(add(convert(GFt(G1, i, t), `+`), i = 1 .. 7)); 10 t + 7 - --------------- 2 10 t + 2 t - 1 coeff(taylor(%, t = 0, 1), t, 0); 7 coeff(taylor(`%%`, t = 0, 100), t, 99); 4591581765859975243813429665306920770687050696484067882068606976 #ii. How many 100 letter "words" (i.e. sequences) in this alphabet are there where no two vowels can be adjacent? G2 := [{1, 2, 3, 4, 5, 6, 7}, {1, 3, 5, 6, 7}, {1, 2, 3, 4, 5, 6, 7}, {1, 3, 5, 6, 7}, {1, 2, 3, 4, 5, 6, 7}, {1, 2, 3, 4, 5, 6, 7}, {1, 2, 3, 4, 5, 6, 7}]; G2 := [{1, 2, 3, 4, 5, 6, 7}, {1, 3, 5, 6, 7}, {1, 2, 3, 4, 5, 6, 7}, {1, 3, 5, 6, 7}, {1, 2, 3, 4, 5, 6, 7}, {1, 2, 3, 4, 5, 6, 7}, {1, 2, 3, 4, 5, 6, 7}] normal(add(convert(GFt(G2, i, t), `+`), i = 1 .. 7)); 10 t + 7 - --------------- 2 10 t + 5 t - 1 coeff(taylor(%, t = 0, 100), t, 99); 3337145723227833638695813627277341200279099093695123201541719026\ 863574981689453125 #iii. How many 100 letter "words" (i.e. sequences) in this alphabet are there where no two vowels can be adjacent and no consonants can be adjacent? G3 := [{2, 4}, {1, 3, 5, 6, 7}, {2, 4}, {1, 3, 5, 6, 7}, {2, 4}, {2, 4}, {2, 4}]; G3 := [{2, 4}, {1, 3, 5, 6, 7}, {2, 4}, {1, 3, 5, 6, 7}, {2, 4}, {2, 4}, {2, 4}] normal(add(convert(GFt(G3, i, t), `+`), i = 1 .. 7)); 20 t + 7 - --------- 2 10 t - 1 coeff(taylor(%, t = 0, 100), t, 99); 200000000000000000000000000000000000000000000000000 #iv. Let a(n) be the number of n-letters of words in that alphabet that have neither adjacent vowels nor adjacent consonants, and let f(t)=Sum(a(n)*t^(n),n=0..infinity). Find f(t) explicitly. a := n -> coeff(taylor(-(20*t + 7)/(10*t^2 - 1), t = 0, n), t, n - 1); a := proc (n) options operator, arrow, function_assign; coeff(taylor(-(20*t+7)/(10*t^2-1), t = 0, n), t, n-1) end proc a(1); 7 a(2); 20 a(3); 70 a(4); 200 #Thus, f(1) = 7, f(2) = 27, f(3)=97, f(4)=297, or #f(1) = 7, f(2) = 2(10) + 7, f(3) = 7(10) + 2(10) + 7, f(4) = 2(10)^2 + 7*10 + 2*10 + 7 #f(t) = 2(10 + 10^2 + 10^3 + ...) + 7(1 + 10 + 10^2 + ...) #2. #1 = [F, W, S, C][] Followers: 2 #2 = [W, C][F, S] Followers: 1, 3 #3 = [F, W, C][S] Followers: 2, 4, 5 #4 = [C][F, W, S] Followers: 3, 6 #5 = [W][F, C, S] Followers: 3, 9 #6 = [F, S, C][W] Followers: 4, 7 #7 = [S][F, W, C] Followers: 6, 8, 9 #8 = [F, S][W, C] Followers: 7, 10 #9 = [F, W, S][C] Followers: 5, 7 #10 = [][F, W, S, C] Followers: 8 Graph2 := [{2}, {1, 3}, {2, 4, 5}, {3, 6}, {3, 9}, {4, 7}, {6, 8, 9}, {7, 10}, {5, 7}, {8}]; Graph2 := [{2}, {1, 3}, {2, 4, 5}, {3, 6}, {3, 9}, {4, 7}, {6, 8, 9}, {7, 10}, {5, 7}, {8}] NuPaths(Graph2, 1, 10, 6); 0 NuPaths(Graph2, 1, 10, 7); 2 #The minimum number of steps that must be taken is 7 #How can this be done? Paths(Graph2, 1, 10, 7); {[1, 2, 3, 4, 6, 7, 8, 10], [1, 2, 3, 5, 9, 7, 8, 10]} #4. #1 = [3M, 3C, B][] Followers: 2, 3, 4 #2 = [3M, 1C][2C, B] Followers: 1, 5 #3 = [3M, 2C][1C, B] Followers: 1 #4 = [2M, 2C][1M, 1C, B] Followers: 1, 5 #5 = [3M, 2C, B][1C] Followers: 2, 4, 6 #6 = [3M][3C, B] Followers: 5, 7 #7 = [3M, 1C, B][2C] Followers: 6, 8 #8 = [1M, 1C][2M, 2C, B] Followers: 7, 9 #9 = [2M, 2C, B][1M, 1C] Followers: 8, 10 #10 = [2C][3M, 1C, B] Followers: 9, 11 #11 = [3C, B][3M] Followers: 10, 12 #12 = [1C][3M, 2C, B] Followers: 11, 13, 14 #13 = [1M, 1C, B][2M, 2C] Followers: 12, 15 #14 = [2C, B][3M, 1C] Followers: 12, 15 #15 = [][3M, 3C, B] Followers: 13, 14 Graph4 := [{2, 3, 4}, {1, 5}, {1}, {1, 5}, {2, 4, 6}, {5, 7}, {6, 8}, {7, 9}, {8, 10}, {9, 11}, {10, 12}, {11, 13, 14}, {12, 15}, {12, 15}, {13, 14}]; Graph4 := [{2, 3, 4}, {1, 5}, {1}, {1, 5}, {2, 4, 6}, {5, 7}, {6, 8}, {7, 9}, {8, 10}, {9, 11}, {10, 12}, {11, 13, 14}, {12, 15}, {12, 15}, {13, 14}] NuPaths(Graph4, 1, 15, 10); 0 NuPaths(Graph4, 1, 15, 11); 4 #The minimum number of steps that must be taken is 11 #How can this be done? Paths(Graph4, 1, 15, 11); {[1, 2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15], [1, 2, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15], [1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15], [1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15]}