#OK to post final #William Wang, 12/15/2020, Final Exam #1. #a. In how many ways can you walk from [0,0,0] to [30,25,20] where the allowed steps are [1,0,0], [0,1,0], or [0,0,1]? (30+25+20)!/(30!25!20!) = 2478456799816702091914145225486880 #To check, use NuW procedure from ComboProject3.txt NuW([30, 25, 20], {[0, 0, 1], [0, 1, 0], [1, 0, 0]}); 2478456799816702091914145225486880 #b. In how many ways can you walk from [0,0,0] to [30,25,20] where the allowed steps are [1,0,0], [0,1,0], or [0,0,1] and you MUST stay in the region x>=y>=z? #Another procedure from ComboProject3.txt NuGW([30, 25, 20], {[0, 0, 1], [0, 1, 0], [1, 0, 0]}); 41512613892711511465063226481480 #c. In how many ways can you walk from [0,0,0] to [30,25,20] where the allowed steps are [1,0,0], [0,1,0], [0,0,1], [1,1,1], or [2,2,2]? NuW([30, 25, 20], {[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 1], [2, 2, 2]}); 31831650298097356165593942880232160 #d. In how many ways can you walk from [0,0,0] to [30,25,20] where the allowed steps are [1,0,0] or [0,1,0],[0,0,1], [1,1,1], or [2,2,2] and you must stay in x>=y Union x>=z (but y and z can be anything as long as they are both <=x)? #A modification of NuGW in ComboProject3.txt which only cares that x>=y and x>=z NuGWmodified := proc(Pt, A) local a: option remember: if Pt[1] < 0 or Pt[2] < 0 or Pt[3] < 0 or Pt[1] < Pt[2] or Pt[1] < Pt[3] then RETURN(0): elif Pt = [0, 0, 0] then RETURN(1): else add(NuGWmodified(Pt - a, A), a in A): fi: end: NuGWmodified([30, 25, 20], {[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 1], [2, 2, 2]}); 3818966446210163616599115660989544 #e. In how many ways can you walk, in the k-dimensional hyper-cubic lattice (the k-DIm Manhattan) from [0,0,..., 0] (with k 0's) to [n,n,....n] (with k n's) always staying in the region x[1]>=x[2]>=... >=x[k].? For example with n=1 there is only one way [0,0,...0]->[1,0,...0]->[1,1,0,...]->...->[1,1,1,1,1]. Give an explicit formula in terms of n and k. #With k=2, this sequence is the sequence of Catalan numbers, which has the recurrence formula (2*n)!/(n!*(n+1)!) #With k=3, this sequence is the sequence of 3-dimensional Catalan numbers, which has the recurrence formula (2*(3*n)!)/(n!*(n+1)!*(n+2)!) #With k=4, this sequence is the sequence of 4-dimensional Catalan numbers, which has the recurrence formula (12*(4*n)!)/(n!*(n+1)!*(n+2)!*(n+3)!) #The formula for k-dimensional Catalan numbers, which is the sequence of ways in the k-dimensional hyper-cubic lattice from [0,0,0,...,0] (k 0's) to [n,n,n,...,n] (k n's) is thus a(n) = 0!*1!*..*(k-1)! *(k*n)! / ( n!*(n+1)!*..*(n+k-1)!) #or Product((k-i)!,i=1..k) * (k*n)!/Product((n+j)!, j=0..k-1) --------------------------------------------------------------------------------------------------------------------------------------------- #2. #a. How many words in the alphabet {0,1,2,3} are there of length 30? {0,1,2,3}^30 --> 4^30 = 1152921504606846976 #b. How many words in the alphabet {1,2,3,4} are there that add-up to 300? #Code from M8.txt, used to answer a similar question for hw8 GFseq(CompsGF({1, 2, 3, 4}, x), x, 300)[301]; 18012939919656512113252584133785878056327163962817704791464695718041992634738504938769 #c. How many words are there in the alphabet {1,2,3,....} (all positive integers) that add-up to n? For general n. Give an explicit formula. #Let f(n) = number of words in {1,2,3,...} that add up to n. Then, f(n) = 2^(n-1) #d. Let a(n) be the number of words in the alphabet {1,4,7,10,....} (all positive integers that give remainder 1 when divided by 3) that add-up to n. Find an explicit expression for Sum(a(n)*x^n,n=0..infinity). x^1 + x^4 + x^7 + x^10 = x * (1 + x^3 + x^6 + x^9 + ...) = x/(1-x^3) 1/(1-(x/(1-x^3))) = (1-x^3)/(1-x^3-x) Sum(a(n)*x^n,n=0..infinity) = (1-x^3)/(1-x^3-x) #e. Let a(n) be as in (d). What is the limit of a(n+1)/a(n) as n goes to infinity? S := {1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82}: evalf(GFseq(CompsGF(S, x), x, 80)[81]/GFseq(CompsGF(S, x), x, 79)[80]); 1.465571232 --------------------------------------------------------------------------------------------------------------------------------------------- #3. #a. What is the egf enumerating set-partitions? How many are there of the set {1,2,...,51}? egf of set partitions: exp(exp(x)-1) coeff(taylor(exp(exp(x) - 1), x = 0, 52), x, 51)*51!; 3263983870004111524856951830191582524419255819477 #b. What is the egf enumerating set partitions where the number of components belongs to {1,4,7,10,...}, but the components themselves can be of any (positive, of course) size? How many are there of the set {1,2,...,51}? egf of set partitions where the number of components belongs to {3*n+1 for n>=0}: (exp(x)-1)^(3*i+1)/(3*i+1)! coeff(taylor(add((exp(x) - 1)^(3*i + 1)/(3*i + 1)!, i = 0 .. 26), x = 0, 52), x, 51)*51!; 1089030250824782148720306369738651363734233026160 #c. What is the egf enumerating set partitions where the number of components can be any non-negative integer but the components themselves must be of odd size? How many are there of the set {1,2,...,51}? egf of set partitions where the number of componenets can be any non-negative integer but the components themselves are of odd size: add(add(x^(2*j + 1)/(2*j + 1)!, j = 0 .. 26)^i/i!, i = 0 .. 51) coeff(taylor(add(add(x^(2*j + 1)/(2*j + 1)!, j = 0 .. 26)^i/i!, i = 0 .. 51), x = 0, 52), x, 51)*51!; 101595492022700597152023270326642584710021120 #d. What is the egf enumerating set partitions are there where the number of components belongs to {1,4,7,10,...} and the components themselves must be of odd size? How many are there of the set {1,2,...,51}? egf of set partitions where the number of components belongs to {1,4,7,10,...} and the components themselves are of odd size: add(add(x^(2*j + 1)/(2*j + 1)!, j = 0 .. 26)^(3*i+1)/(3*i+1)!, i = 0 .. 17) coeff(taylor(add(add(x^(2*j + 1)/(2*j + 1)!, j = 0 .. 26)^(3*i + 1)/(3*i + 1)!, i = 0 .. 17), x = 0, 52), x, 51)*51!; 30143119660583350838086153637731292910753195 --------------------------------------------------------------------------------------------------------------------------------------------- #4. #a. Write all super-set partitions with n=3. #Set partitions of {1,2,3}: a. {1},{2},{3} b. {1,2},{3} c. {1,3},{2} d. {2,3},{1} e. {1,2,3} Partitions of set partitions of {1,2,3} #Need to look at partitions of a,b,c,d,e #Work shown in attached image #Partitions of a {{1},{2},{3}} {{1},{2}},{{3}} {{1},{3}},{{2}} {{2},{3}},{{1}} {{1}},{{2}},{{3}} #Partitions of b {{1,2},{3}} {{1,2}},{{3}} #Partitions of c {{1,3},{2}} {{1,3}},{{2}} #Partitions of d {{2,3},{1}} {{2,3}},{{1}} #Partitions of e {{1,2,3}} #All super set partitions with n=3 is equal to (Partitions of a) union (Partitions of b) union (Partitions of c) union (Partitions of d) union (Partitions of e) #All super set partitions with n=3 is #{{1},{2},{3}}, {{1},{2}},{{3}} ,{{1},{3}},{{2}}, {{2},{3}},{{1}}, {{1}},{{2}},{{3}}, {{1,2},{3}}, {{1,2}},{{3}}, {{1,3},{2}}, {{1,3}},{{2}}, {{2,3},{1}}, {{2,3}},{{1}}, {{1,2,3}} #b. What is Sum(s[2](n)*x^n/n!, n=0..infinity)? Is s[2](n) in the OEIS? s[2](1) = 1 s[2](2) = 3 s[2](3) = 12 (From a) s[2](3) = 60 #Looking at the OEIS and reading the comments, A000258 seems to be the sequence #So Sum(s[2](n)*x^n/n!, n=0..infinity) should be exp(exp(exp(x)-1)-1) #And this makes sense since we are partitioning a set partition, and the egf of all set partitions is exp(exp(x)-1) #This agrees with the Fundamental Theorem of Exponential Generating Functions covered in Lecture 20 #c. Define a super-set-partition of order m to be a set of set-partitions of order m-1 all with different labels such that total of individuals is n. Let s[m](n) be the number of such creatures. What is the smallest m for which it is NOT in the OEIS? Sequence of s[1](n): A000110 (Bell numbers) Sequence of s[2](n): A000258 Sequence of s[3](n): A000307 Sequence of s[4](n): A000357 Sequence of s[5](n): A000405 Sequence of s[6](n): A001669 Sequence of s[7](n): A081624 Sequence of s[8](n): A081629 Sequence of s[9](n): A081697 Sequence of s[10](n): A081740 #Thus, the smallest m for which it is not in the OEIS is 11. (The description of A081740 is the 11-level labeled rooted trees with n leaves, but describes s[10](n)) --------------------------------------------------------------------------------------------------------------------------------------------- #5. #a. How many integer partitions are there of 1000? pnFast(1000); 24061467864032622473692149727991 #b. How many integer partitions of 1000 are there where all the parts are odd? #Used procedure from M24.txt #1000th element of pnOddSeq(1000) 8635565795744155161506 #c. How many integer partitions of 1000 are there where all the parts are different than each other? #Euler's Theorem: number of integer partitions of n into distinct parts = number of partitions of n into odd parts #So this is equivalent to the answer in b 8635565795744155161506 #Check: #1000th element of pnDistinctSeq(1000) 8635565795744155161506 #d. How many integer partitions of 1000 are there where all the parts are different than each other and all the parts are odd? #Uses the fact that the generating function for the number of partitions of n into distinct and odd parts is Product(1+x^(2*k+1),k=0..infinity) #This generating function is listed in the OEIS under A700, which describes the sequence of the number of partitions of n into distinct odd parts. #This sequence was uncovered to the class as a result of hw24. coeff(taylor(product(1 + x^(2*k + 1), k = 0 .. 500), x, 1001), x, 1000); 517035762467311 --------------------------------------------------------------------------------------------------------------------------------------------- #6. #a. How many rooted labelled trees are there with 31 vertices? #Used procedure TreeSeqL from M22.txt #The nth entry of TreeSeqL is the OGF of the number of rooted labelled trees on n vertices according to the weight t^(number of leaves) #Sum over all the coefficients to get the total number of rooted labelled trees on 31 vertices #degree of TreeSeqL(31, t)[31] is the highest power of t in the ogf sum(coeff(TreeSeqL(31, t)[31], t, i), i = 1 .. degree(TreeSeqL(31, t)[31])); 550618520345910837374536871905139185678862401 #b. How many rooted labelled trees are there with 31 vertices where the root has exactly two children? #Start with 31 vertices, so 30 edges #Remove the root and the 2 edges, so we now have 30 vertices and 28 edges coeff(taylor(sum(n^(n - 2)*x^n/n!, n = 1 .. 31)^2/2!, x = 0, 32), x, 30)*30!; 132685396238773800000000000000000000000000 #c. How many rooted labelled trees are there with 31 vertices where each vertex must have either zero, one, three, or four children? #Analogous to hw22 question 2iv #SeqRTchild(S,N) outputs the first N entries in the list enumerating rooted labelled trees where every vertex is either a leaf (no children) or has a number of children in S SeqRTchild({1, 3, 4}, 31)[31]; 388391178300656853181332829972846230000000 #d. How many rooted labelled trees are there with 31 vertices where each vertex can have any number of children (including no children, of course) EXCEPT that it can't have one, three, or four children. #Analogous to hw22 question 3iv #SeqRTchildNone(S,N) outputs the first N entries in the list enumerating rooted labelled trees where every vertex is either a leaf (no children) or has a number of children that is not in the set S. SeqRTchildNone({1, 3, 4}, 31)[31]; 2863465748628395267057869436794752181 --------------------------------------------------------------------------------------------------------------------------------------------- #7. #a. Either by hand, or with Maple, find BT(4). #Work shown in attached image BT(4) = { [ [[],[]] , [[],[]] ] [ [ [[],[]] , [] ] , [] ] [ [ [] , [[],[]] ] , [] ] [ [] , [ [[],[]] , [] ] ] [ [] , [ [] , [[],[]] ] ] } #b. Let b(n) be the number of complete binary trees with n leaves. For example b(1)=1, b(2)=1, b(3)=2. Let B(x)=Sum(b(n)*x^n,n=0..infinity) Prove that B(x) = x + B(x)^2