# OK to post test # Karnaa Mistry | Final for Math 454(2), Fall 2020, Dr. Z. # December 15, 2020 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] or [0,1,0], or [0,0,1] This is the classic 3D Manhattan Lattice example --> starting from the origin, each of the three atomic steps are in ony direction of one unit only --> Use the formula: (a+b+c)! / (a!*b!*c!) --> (30+25+20)! / (30!*25!*20!) = 2478456799816702091914145225486880 2478456799816702091914145225486880 ways (b) 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], or [0,0,1] and you MUST stay in the region x>=y>=z Write a Maple procedure: # --- # NuWalks3R:=proc(x,y,z) local i: option remember: if (x<0 or y<0 or z<0 or x=y Union x>=z (but y and z can be anything as long as they are both <=x) Take the region (x>=y Union x>=z) --> negation for our checking --> NOT(x=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. The case we've seen the most is probably k=2, which is the number of restricted walks (x>=y) from [0,0] to [n,n] using steps [0,1],[1,0]. This is equal to the Catalan numbers; it is mentioned in the (2D) Ballot Problem (Wolfram Mathworld). But, for larger k, there are actually higher dimensions of Catalan numbers. For the case of k=2, we have the classic (2n)!/(n!*(n+1)!). Upon researching higher dimensions of Catalan numbers, I found a draft paper by Stephanie F. Troyer and Stephen L. Snover at https://oeis.org/A005789/a005789_1.pdf. Their paper involved conceptualizing |Catalan paths| = |all paths| - |paths crossing diagonals| = (mn)!/(n!)^m - |paths crossing diagonals| From there, after using techniques involving reflection of paths across key hyperplanes they generalized that the number of Catalan paths of n symbols m dimensions equals the number of Catalan 'words' of m symbols they achieved: |Catalan paths to (n,...,n) (in R^m)| = |Catalan paths to (m,...,m) (in R^n)| While I didn't have time to fully understand their paper, other sources online write Catalan(3,n) = 1!2!(3n)!/(n!(n+1)!(n+2)!), Catalan(4,n) = 1!2!3!(4n)!/(n!(n+1)!(n+2)!(n+3)!) (this is in the paper, too). If we were to think of some pattern, we come up with the product(i!, i=1..k-1)*(kn)! / product((n+i)!, i=1..k-1), which is equal to the conclusion of the formula in the paper. However, they wrote it as (m-1)!!, which they marked as "unwise use of !!" (since n!! mainly uses numbers with the same parity as n). So, we have some type of formula: Catalan(n,k) = 1!*2!*3!*...*(k-1)!*(kn)! / (n!*(n+1)!*...*(n+k-1)!) 2. (a) How many words in the alphabet {0,1,2,3} are there of length 30? Dealing with length, there are four unique letters {0,1,2,3}, so we do |{0,1,2,3}|^30 possible words 4^30 = 1152921504606846976 1152921504606846976 words (b) How many words in the alphabet {1,2,3,4} are there that add-up to 300? The weight-enumerator of this alphabet is x^1+x^2+x^3+x^4, and the words can be any length. Using Maple, we can do add(coeff((x^1+x^2+x^3+x^4)^i,x,300),i=0..300) = 18012939919656512113252584133785878056327163962817704791464695718041992634738504938769 We only have to go up to 300 because the maximum i value is an i such that the smallest possible term (x^1)^i = 300, so 300 / i = i --> i=1 18012939919656512113252584133785878056327163962817704791464695718041992634738504938769 words (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. This equals the number of compositions of n, which has a known formula: 2^(n-1). This formula can be found in many ways, but one way is to imagine a list of n 1's, where there are n-1 spots alternating between each of the 1's in the list, like 1_1_1_1_..._1_1. For each of the n-1 spots, we can either put a symbol to continue (say, a `+`), or a symbol to stop (say, a `|`) that current component. For example, one such composition of 3 could be 1_1_1 --> 1+1|1 --> 2,1 So, for each of these n-1 spots we have two choices, and since we multiply this binary choice of 2 a total of n-1 times, we get 2^(n-1) NumCompositions(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) Weight-enumeration of {1,4,7,10,...} = x^1+x^4+x^7+x^10+... = x*(1+x^3+x^6+x^9+...) = x*(sum(x^(3*i),i=0..infinity)) = -x / (x^3 - 1) = x / (1 - x^3) normal(1/(1- x/(1-x^3))) = f = (x^3-1)/(x^3+x-1) Note that Sum(a(n)*x^n,n=0..infinity) is the infinite sum form of the generating function. So, since we've found the genearting function from (1 / 1 - w) where w = x / (1 - x^3), we have our answer after converting to parfrac: Sum(a(n)*x^n,n=0..infinity) = 1 - x/(x^3 + x - 1) (e) Let a(n) be as in (d). What is the limit of a(n+1)/a(n) as n goes to infinity. seq(coeff(taylor(f,x=0,n+1),x,n),n=0..20) = (1,) 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872 Either from the OEIS or through inspection, we can see a pattern (ignoring n=0) such that a(n+3) = a(n+2) + a(n), or a(n) = a(n-1) + a(n-3), with initial conditions a(1)=1, a(2)=1, a(3) = 1. For example, a(4) = 1+1=2; a(5) = 1+2=3; a(12) = 13+28=41. We have limit( a(n+1)/a(n), n=0..infinity), but we will rewrite a(n+1) and a(n) to make it easily computable. This is a linear recurrence relation, so we can use characteristic polynomial techniques as a(n) = r^n satisfies the recurrence. a(n) = a(n-1) + a(n-3) --> r^n = r^(n-1) + r^(n-3) --> divide all by r^(n-3) --> r^3 = r^2 + 1 Using Maple, expand(solve(r^3 = r^2 + 1, r)[1]) = 1/6*(116+12*93^(1/2))^(1/3)+2/3/(116+12*93^(1/2))^(1/3)+1/3 = P (I'll refer to it as the var P) Note that this is the only real solution of the polynomial (the others are complex) This leads to a(n) = h*P^n for a non-zero constant h that can be found using the initial conditions. However, it doesn't matter what h is: limit( a(n+1)/a(n), n=0..infinity) = limit( h*P^(n+1) / (h*P^n), n=0..infinity) --> h's cancel, P^n cancels --> P This is very close to manual estimation seq((coeff(taylor(fy,x=0,n+2),x,n+1)) / (coeff(taylor(fy,x=0,n+1),x,n)) ,n=0..LargeN)[LargeN] Therefore: limit of a(n+1)/a(n) as n goes to infinity = 1/6*(116+12*93^(1/2))^(1/3)+2/3/(116+12*93^(1/2))^(1/3)+1/3 = approx. 1.465571232 3. (a) What is the egf enumerating set-partitions. How many are there of the set {1,2,...,51}? The egf enumerating set-partitions is the sum( B(n)*x^n/n!, n=0..infinity), where B(n) is the sequence of the Bell numbers. We know this to be exp(exp(x)-1). For the set {1,2,...,51}, we do coeff(taylor(exp(exp(x)-1),x=0,52),x,51)*51! = 3263983870004111524856951830191582524419255819477 EGF = exp(exp(x)-1) Number = 3263983870004111524856951830191582524419255819477 set-partitions (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}? Take sum(x^(3*i+1)/(3*i+1)!,i=0..infinity) which is 1/3*3^(1/2)*exp(-1/2*x)*sin(1/2*3^(1/2)*x)-1/3*exp(-1/2*x)*cos(1/2*3^(1/2)*x)+1/3*exp(x) The egf is then that expression substituting x as exp(x)-1: f:= 1/3*3^(1/2)*exp(-1/2*(exp(x)-1))*sin(1/2*3^(1/2)*(exp(x)-1))-1/3*exp(-1/2*(exp(x)-1))*cos(1/2*3^(1/2)*(exp(x)-1))+1/3*exp((exp(x)-1)) Compute coeff(taylor(lp,x=0,52),x,51)*51! = 1089030250824782148720306369738651363734233026160 EGF = 1/3*3^(1/2)*exp(-1/2*(exp(x)-1))*sin(1/2*3^(1/2)*(exp(x)-1))-1/3*exp(-1/2*(exp(x)-1))*cos(1/2*3^(1/2)*(exp(x)-1))+1/3*exp((exp(x)-1)) Number = 1089030250824782148720306369738651363734233026160 set-partitions (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}? Take the exp(x)-1 part of exp(exp(x) - 1) and instead use odd sizes --> sum(x^(2*i+1)/(2*i+1)!,i=0..infinity) = sinh(x) The egf is exp(sinh(x)). Then, we can compute coeff(taylor(exp(sinh(x)),x=0,52),x,51)*51! to get 101595492022700597152023270326642584710021120 EGF = exp(sinh(x)) Number = 101595492022700597152023270326642584710021120 set-partitions (d) What is the egf enumerating set partitions are there where the number of components belongs to {1,4,7,10,...} and and the components themselves must be of odd size. How many are there of the set {1,2,...,51}? Use what was found from (b) and (c), via sum(x^(3*i+1)/(3*i+1)!,i=0..infinity) which equals 1/3*3^(1/2)*exp(-1/2*x)*sin(1/2*3^(1/2)*x)-1/3*exp(-1/2*x)*cos(1/2*3^(1/2)*x)+1/3*exp(x) Replace x with sinh(x) (from (c)) --> 1/3*3^(1/2)*exp(-1/2*sinh(x))*sin(1/2*3^(1/2)*sinh(x))-1/3*exp(-1/2*sinh(x))*cos(1/2*3^(1/2)*sinh(x))+1/3*exp(sinh(x)) Let that result be g, then we compute coeff(taylor(g,x=0,52),x,51)*51! to get 30143119660583350838086153637731292910753195 EGF = 1/3*3^(1/2)*exp(-1/2*sinh(x))*sin(1/2*3^(1/2)*sinh(x))-1/3*exp(-1/2*sinh(x))*cos(1/2*3^(1/2)*sinh(x))+1/3*exp(sinh(x)) Number = 30143119660583350838086153637731292910753195 set-partitions 4. Define a super-set-partition of order 2 to be a set of set partitions {P1,P2, ...,Pk} where k can be any positive integer and P1,P2,..., Pk are set partitions such that the labels in each of P1,P2,..,Pk are all different and altogether there n members. For example {{{2,4},{6}}, {{1},{5},{3}}} is such a creature with n=6, as is {{{1}}, {{2}},{{3}},{{4}},{{5}},{{6}}}, and many others. Let s[2](n) be the number of such creatures. (a) Write all super-set partitions with n=3. Basing off of the normal set-partitions of {1,2,3}, we have { {1,2,3}, {{1,2},{3}}, {{1,3},{2}}, {{2,3},{1}}, {{1},{2},{3}} }; These are the insides of the single-sized super-set-partitions we will have. All SP's but the first have natural split points due to their own partitioning, so we can get: { {{1,2}}, {{3}} }, { {{1,3}}, {{2}} }, { {{2,3}}, {{1}} }; Notice that within each of those 3 super-set-partitions, the set-partitions with single elements of size 2 ({{1,2}}, {{1,3}}, and {{2,3}}) can also be split up, giving us: { {{1},{2}}, {{3}} }, { {{1},{3}}, {{2}} }, { {{2},{3}}, {{1}} }; Lastly, we reimagine { {{1},{2},{3}} } as a super-set-partition with 3 elements (the only one containing 3 set-partitions): We achieve { {{1}}, {{2}}, {{3}} }, and can write the answer, which is 12 super-set partitions with n=3: { { {{1,2,3}} }, { {{1,2},{3}} }, { {{1,3},{2}} }, { {{2,3},{1}} }, { {{1},{2},{3}} }, { {{1,2}}, {{3}} }, { {{1,3}}, {{2}} }, { {{2,3}}, {{1}} }, { {{1},{2}}, {{3}} }, { {{1},{3}}, {{2}} }, { {{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? This infinite sum is an exponential generating function, which would be equal to the egf expression as some f(x). The egf for set-partitions is already known as exp(exp(x)-1), and since the super-set-partitions seem to partition the insides of those set-partitions, let's follow the same idea of how exp(exp(x)-1) was achieved, via sum((e^x - 1)^n / n!, n=0..infinity). This time, let's use f = exp(exp(x)-1) in the element of the final infinite summation, and get sum((f-1)^n / n!, n=0..infinity) (f --> f-1 to exclude the empty set partition). This gives exp(f-1) --> exp(exp(exp(x)-1)-1). Doing seq(coeff(taylor(exp(exp(exp(x)-1)-1),x=0,n+1),x,n)*n!,n=1..10) returns 1, 3, 12, 60, 358, 2471, 19302, 167894, 1606137, 16733779. Surely enough, this is in the OEIS, and it has the description "Expansion of e.g.f. exp(exp(exp(x)-1)-1)", as A000258, with a comment "a(n) is the number of ways to partition {1,2,...,n} and then partition each cell into subcels." Sum(s[2](n)*x^n/n!, n=0..infinity) = exp(exp(exp(x)-1)-1) Yes, s[2](n) is in the OEIS, A000258 (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? (Done by searching the EGF) m = 2 --> exp(exp(exp(x)-1)-1) (in the OEIS: A000258) m = 3 --> exp(exp(exp(exp(x)-1)-1)-1) (in the OEIS: A000307) m = 4 --> exp(exp(exp(exp(exp(x)-1)-1)-1)-1) (in the OEIS: A000357) m = 5 --> exp(exp(exp(exp(exp(exp(x)-1)-1)-1)-1)-1) (in the OEIS: A000405) m = 6 --> exp(exp(exp(exp(exp(exp(exp(x)-1)-1)-1)-1)-1)-1) (in the OEIS: A001669) m = 7 --> exp(exp(exp(exp(exp(exp(exp(exp(x)-1)-1)-1)-1)-1)-1)-1) (in the OEIS: A081624) m = 8 --> exp(exp(exp(exp(exp(exp(exp(exp(exp(x)-1)-1)-1)-1)-1)-1)-1)-1) (in the OEIS: A081629) m = 9 --> exp(exp(exp(exp(exp(exp(exp(exp(exp(exp(x)-1)-1)-1)-1)-1)-1)-1)-1)-1) (in the OEIS: A081697) m = 10 --> exp(exp(exp(exp(exp(exp(exp(exp(exp(exp(exp(x)-1)-1)-1)-1)-1)-1)-1)-1)-1)-1) (in the OEIS: A081740) m = 11 --> yields sequence 1, 12, 210, 4830, 137512, 4663253,.. (NOT in the OEIS) Smallest m for which it is NOT in the OEIS = 11 5. (a) How many integer partitions are there of 1000? Using gf = product(1/(1-q^i),i=1..infinity), we compute the product only up to i=1000, so we have: coeff(taylor(product(1/(1-q^i),i=1..1000),q=0,1001),q,1000) = 24061467864032622473692149727991 24061467864032622473692149727991 integer partitions (b) How many integer partitions of 1000 are there where all the parts are odd? Using gf = product(1/(1-q^(2*i+1)),i=1..infinity), we compute the product for the power 1000, meaning up to i=500 coeff(taylor(product(1/(1-q^(2*i+1)),i=0..500),q=0,1001),q,1000) = 8635565795744155161506 8635565795744155161506 integer partitions (c) How many integer partitions of 1000 are there where all the parts are different than each other? The number distinct integer partitions = The number of odd integer partitions (Euler) Doing direct computation anyway gives: coeff(taylor(product(1+q^i,i=1..1000),q=0,1001),q,1000) = 8635565795744155161506 (same as (b)) 8635565795744155161506 integer partitions (d) How many integer partitions of 1000 are there where all the parts are different than each other and all the parts are odd. Use (c), the gf is product(1+q^i,i=1..infinity), but we only compute up to 1000. Also, we'll ignore all the even parts, meaning the even powers 1+q^2, 1+q^4, while still getting an answer of distinct parts. Doing coeff(taylor(product(1+q^(2*i+1),i=0..500),q=0,1001),q,1000) yields 517035762467311 517035762467311 integer partitions 6. (a) How many rooted labelled trees are there with 31 vertices? Cayley's formula for the number of labelled trees on n nodes = n^(n-2); have n choices for a root, so we have n*n^(n-2) = n^(n-1) 31^30 = 550618520345910837374536871905139185678862401 550618520345910837374536871905139185678862401 rooted labeled trees # --- # #TreeSeqL(N,t): Like list of length N, whose n-th entry is the (ordinary) generating function of #ROOTED labelled trees on n vertices according to the weight t^#Leaves. It uses the fact that #the exponential generating function satisfies the #functional equation #T(x,t)= t*x+ x*(exp(T(x,t)-1) #Try #TreeSeqL(20,t); TreeSeqL:=proc(N,t) local L,z,n: L:=FunEqToSeq(t-1+exp(z),z,N): [seq(expand(L[n]*n!),n=1..N)]: end: # --- # (b) How many rooted labelled trees are there with 31 vertices where the root has exactly two children. There are n ways to choose a single vertex to be a root. Let's isolate this vertex, as we should assure that the rest of the graph is a tree, so we note that (from Cayley's formula) the number of possible labeled trees (no root here) is n^(n-2); since we have n-1 vertices that are not the root, we do (n-1)^(n-3) as the total number of connected acyclic graphs on these remaining vertices. Finally, we connect the root, by picking one edge from the n-2 edges, looking at its vertices, and connecting the root to those vertices via 2 edges. Now, there is a cycle, so let us remove that one edge we based the children from, and we successfully have a rooted labeled tree with n vertices and n-2+2-1 = n-1 edges. Our formula looks like t(n) = n * (n-1)^(n-3) * (n-2) For n = 31, we have 31*(30^28)*29 = 205662364170099390000000000000000000000000000 205662364170099390000000000000000000000000000 rooted labeled trees (c) How many rooted labelled trees are there with 31 vertices where each vertex must have either zero, one, three, or four children. I had a lot of trouble with (c) and (d), and couldn't figure out an answer. My approach would have been as follows: Set up the functional equation for egf of r_c(n) --> R_c(x) = sum(r_c(n)*x^n/n!,n=0..infinity) Remove the root (gives us x on its own) Find the cases where r_c(x) is nonzero (like how when we found trees where every vertex must have an even number of children) Case 0 --> ... Case 1 --> ... Case k --> ... 0 or r_c(x)^k/k! R_c(X) = Sum(r_c(x)^n/n!,n=2..infinity) minus the cases not allowed, i.e. if alternating then r_c(x)^(2*n+1)/(2*n+1) for odd, etc.. R_c(X) = x*(function of x found from above) --> we have x*PHI(z), we can do FunEqToSeq(PHI,z,N) and multiply by i! (from Lecture 22) # --- # #FunEqToSeq(PHI,z,N): #Given a function PHI of z, and a positive integer N, outputs the first N terms, starting at n=1 #of the solutions of the functional equations #f(x)=x*PHI(f(x)). Try: #FunEqToSeq(exp(z),z,10); FunEqToSeq:=proc(PHI,z,N) local f,i,j,x: #we start with f=x, and keep applying the mapping f->x*PHI(f(x)), N times, and every time only #save the terms up to and including x^N f:=x: for i from 1 to N do f:=x*subs(z=f,PHI): f:=taylor(f,x=0,N+1): f:=add(coeff(f,x,j)*x^j,j=0..N): od: [seq(coeff(f,x,j),j=1..N)]: end: # --- # L:= (FunEqToSeq(PHI,z,31): for i from 1 to 31 do L[i]:=i!*L[i]: od: --> L[31] = ... I just couldn't work out which cases were allowed or not, perhaps I missed something obvious or just can't remember. (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. Like (c), I don't have an answer but my approach would have been similar to (c) - finding the functional equation, finding cases where it is 0 or where it is actually the unknown r_c(x)^k/k!, add up (or subtract) accordingly to infinity and get the PHI(z) expression. Using the FunEqToSeq(PHI,z,31) I would find the corresponding value then multiply by 31! to get some answer. 7. A complete (unlabelled, ordered) BINARY tree is defined recursively by T= [] (denoting a single vertex, just the root) or otherwise T=[T1,T2] where T1, T2, are smaller such creatues. Let BT(n) be the number of such creatues with n leaves. For example BT(1)= {[]}; BT(2)={[[],[]]}; BT(3)= {[[], [[], []]], [[[], []], []]} . (a) Either by hand, or with Maple, find BT(4). There are going to be 5, complete binary trees with four leaves, that look like: O O O O O / \ / \ / \ / \ / \ O O O L L O O L L O / \ / \ / \ / \ / \ / \ L L L L O L L O L O O L / \ / \ / \ / \ L L L L L L L L BT(4) = {[[[],[]],[[],[]]], [[[[],[]],[]],[]], [[],[[],[[],[]]]], [[[],[[],[]]],[]], [[],[[[],[]],[]]] } = 5 creatures (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 We have B(x) = Sum(b(n)*x^n,n=0..infinity) B(x) is the generating function for the Catalan numbers, which is known to count the number of complete binary trees with n leaves, among many, many other topics. This satisfies the recurrence relation b_{n+1} = sum(b_i * b_{n-i}, i=0..n) because of recursive application. If b(n+1) is the number of complete binary trees with n+1 leaves, looking at this n+1th vertex (root of a subtree) there are i vertices to the left and n-i to the right. Assuming that b(n) gives the correct number, multiplying in that sum gives the number for that many leaves. (A classic Catalan recurrence is C_{n+1} = sum(C_i * C_{n-i}, i=0..n). From squaring B(x), we square the right hand sum, and there will be a new coefficient for a particular x^n in question. This coefficient is also sum(b_i * b_{n-i}, i=0..n) since those are all possible ways to 'choose' what coefficients are multiplied together to get x^n's coefficient. Substituting the b_{n+1} from the recurrence, we have: B(x)^2 = sum(b_{n+1}*x^n,n=0..infinity) It looks a lot like the beginning, but there is some shift. Knowing that b_1 = 1 lets us add an x to both sides: B(x)^2 + x = sum(b_{n+1}*x^n,n=0..infinity) + x We can subtract out the 1st term from the sum now since we are adding 1*x afterward, so we can end with: B(x)^2 + x = Sum(b(n)*x^n,n=0..infinity) = B(x) --> B(x) = x+ B(x)^2