# Final for Math 454(2), Fall 2020, Dr. Z.
#OK to post 


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]? 


(30 + 25 + 20)!/(30!*25!*20!)
2478456799816702091914145225486880 ways


2. (a) How many words in the alphabet {0, 1, 2, 3} are there of length 30? 


1152921504606846976


(b) How many words in the alphabet {1, 2, 3, 4} are there that add up to 300? 


18012939919656512113252584133785878056327163962817704791464695718041992634738504938769


(e) Let a(n) be as in (d). What is the limit of a(n+1) / a(n) as n goes to infinity. 


a(n) = 3*n+1, so a(n+1) = 3*n+2). 
Lim n→ infinity ((3*n+2)/(3*n+1)) = 1. 


3. (a) What is the egf enumerating set-partitions. 


How many are there of set {1,2,...,51}? 


There are 3263983870004111524856951830191582524419255819477 partitions. The egf enumerating set-partitions is 1/((1-q)*(1-q^2)*(1-q^3)*....). 


Evaluating the infinite set of all integer partitions with distinct parts, when we pick a random integer position you can either include 1 or not, either include 2 or not, either include 3 or not, and so on and so forth. 


An integer partitions L is an element in {[ ], [1]} X {[ ], [2]} X {[ ], [3]} X …


According to the weight enumerator properties, we know that |A X B X C X…| = |A|_q * |B|_q * … 


Therefore, (1+q)*(1+q^2)*(1+q^3)*... =Product(1+q^i,i=1..infinity) is the generating function of the sequence enumerating distinct partitions. 


4. (a) Write all super-set partitions with n = 3 


{1, 2, 3}
{1, 2}, {3} 
{1, 3}, {2} 
{1}, {2, 3} 
{1}, {2}, {3} 


5. (a) How many integer partitions are there of 1000? 


24061467864032622473692149727991


(b) How many integer partitions of 1000 are there where all parts are odd? 


8635565795744155161506




6. (a) How many rooted labelled trees are there with 31 vertices? 


17761887753093897979823770061456102763834271


7. (a) Either by hand, or with Maple, find BT(4). 


BT(4) = { [[ ], [[ ], [ ], [ ]]], [[ ], [[ ], [ ]]] }