# Final for Math 454(2), Fall 2020, Dr. Z. #Start: Dec. 15, 9:00am #Due: Dec. 16, 9:00am. EMAIL to ShaloshBEkhad@gmail.com #Subject: ComboFinal #with an attachment called #ComboFinalFirstLast.txt: e.g. ComboFinalDoronZeilberger.txt (PLEASE observe capitalization) #INDICATE WHETHER IT IS OK to POST YOUR TEST Each bunch of problems is with increasing difficulty. Full answers to all parts (a) would be needed to pass the class with a C (provided that all the homework, attendance quizzes and projects have been submitted). Parts (b),(c), (d), ... are more challenging. Some of the (harder) problems may require coding. Some of the problems are really challenging, and I don't expect every one to do all of them (even the A students). YOU CAN USE Maple, of course, the Lectures, Maple code, posted solutions, and more generally the internet, EXCEPT you have to do it by yourself, and EXPLAIN EVERYTHING! FIRST DO THE (a) questions, then the (b) questions, etc., so you won't run out of time. 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] (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 [Hint: this is part of the 3D ballot problem, you are welcome to look it up.] (c) 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] (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) (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. 2. (a) How many words in the alphabet {0,1,2,3} are there of length 30? (b) How many words in the alphabet {1,2,3,4} are there that add-up to 300? (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. (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) (e) Let a(n) be as in (d). What is the limit of a(n+1)/a(n) as n goes to infinity. 3. (a) What is the egf enumerating set-partitions. How many are there of the set {1,2,...,51}? (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}? (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}? (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}? 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. (b) What is Sum(s[2](n)*x^n/n!, n=0..infinity)? Is s[2](n) in the OEIS? (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? 5. (a) How many integer partitions are there of 1000? (b) How many integer partitions of 1000 are there where all the parts are odd? (c) How many integer partitions of 1000 are there where all the parts are different than each other? (d) How many integer partitions of 1000 are there where all the parts are different than each other and all the parts are odd. 6. (a) How many rooted labelled trees are there with 31 vertices? (b) How many rooted labelled trees are there with 31 vertices where the root has exactly two children. (c) How many rooted labelled trees are there with 31 vertices where each vertex must have either zero, one, three, or four children. (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. 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). (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