> #Weiji Zheng, FINAL EXAM, 12/15/2020
;
> #OK TO POST TEST
;
> 
;
> #Q1
;
> #(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]
;
> #For this problem, we have proved the explicit formula F(a,b,c) = (a+b+c)!/(a!*b!*c!) where [a,b,c] = [30,25,20] in this case
;
> #thus, the number of walks = 
;
> (30+25+20)!/(30!*25!*20!)
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] or [0,1,0], or [0,0,1]and you MUST stay in the region x>=y>=z
;
> 
;
> #to satisfy x>=y>=z, we should use NuGW
;
> NuGW([30, 25, 20], {[1, 0, 0], [0, 1, 0], [0, 0, 1]})
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] or [0,1,0],[0,0,1], [1,1,1], or [2,2,2]
;
> 
;
> NuW([30, 25, 20], {[1, 0, 0], [0, 1, 0], [0, 0, 1], [2, 2, 2]})
2725607682792272223672771521436960
;
> 
;
> #(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)

;
> #to satisfy x>=y union x>=z, we can change the NuGW a little bit
;
> NuGW:=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(NuGW(Pt-a,A),a in A):
> fi:
> end:

> NuGW([30, 25, 20], {[1, 0, 0], [0, 1, 0], [0, 0, 1], [2, 2, 2]})
289973887959743106731754279850160
;
> #(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.
;
> 
;
> 
;
> 
;
> 
;
> 
;
> 
;
> 
;
> #Q2
;
> #(a) How many words in the alphabet {0,1,2,3} are there of length 30?
;
> #For each position of the length-of-30 words, we can put each of{0,1,2,3} which is 4 choices
;
> #So the number of words should be
;
> 4^30
1152921504606846976
;
> #(b) How many words in the alphabet {1,2,3,4} are there that add-up to 300?
;
> #we use GFseq and CompsGF in lecture 8 and get the last element 
;
> 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.
;
> #When n = 1, 2, 3, 4, 5, 6, 7, 8...
;
> #By using GFseq(CompsGF({1,2,3,4,5,6,7,8}, x), x, n)[n+1]
;
> #I get
;
> #1, 2, 4, 8, 15, 30, 59, 116...
;
> #I found the G.F. for this seqwuence on OEIS
;
> #(x^3 - x^4)/(1 - x - x^2 - x^3 - x^4 - x^5)
;
> #(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)
;
> #according to the description
;
> #a(n) = 3*n + 1
;
> 
;
> 
;
> 
;
> 
;
> 
;
> 
;
> 
;
> 
;
> #(e) Let a(n) be as in (d). What is the limit of a(n+1)/a(n) as n goes to infinity.
;
> #limit -> a(n+1)/a(n) can be rewrite as limit -> (3n+4)/(3n+1) n->infinity, which is 1
;
> # so the limit is 1
;
> 
;
> #Q3
;
> # (a) What is the egf enumerating set-partitions. How many are there of the set {1,2,...,51}?
;
> #the egf of set-partitions is exp(exp(x)-1)
;
> egf := exp(exp(x)-1)
egf := exp(exp(x)-1)
;
> coeff(taylor(exp(exp(x)-1)/(1-x),x=0,52), x, 51) * 51!;
8647396347537155182434821717636153400697809911204350359135449581447
;
> 
;
> #(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  the components themselves must be of  odd size. How many are there of the set {1,2,...,51}?

;
> 
;
> 
;
> 
;
> 
;
> #Q4
> #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.
;
> #{{1,2,3}}
;
> #{{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?
;
> 
;
> 
;
> #1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570
;
> #A000110
;
> 
;
> 
;
> 
;
> 
;
> 
;
> #(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?
;
> 
;
> 
;
> 
;
> 
;
> 
;
> 
;
> 
;
> 
;
> #Q5
;
> #(a) How many integer partitions are there of 1000?
;
> with(combinat):

> numbpart(1000)
24061467864032622473692149727991
;
> #(b) How many integer partitions of 1000 are there where all the parts are odd?
;
> #I initialize an official maple libiary "440244integer_partition" to use "oddparts"
;
> oddparts(10)
> [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 3, 3], [1, 3, 3, 3], [1, 1, 1, 1, 1, 5], [1, 1, 3, 5], [5, 5], [1, 1, 1, 7], [3, 7], [1, 9]]
> #in this way, I can use nops(oddparts(1000)) to get the answer
;
> #can also use the generating function
;
> 
;
> #1/(1-x) * 1/(1-x^3) * 1/(1-x^5) * ... * 1/(1-x^1999)
;
> 
;
> 
;
> #(c) How many integer partitions of 1000 are there where all the parts are different than each other?
;
> 
;
> #number of integer partition without duplicates = 
;
> 
;
> #generatiing functions:
> #(1+x)(1+x^2)(1+x^3)(1+x^5)...(1+x^1000)
;
> 
;
> 
;
> #(d) How many integer partitions of 1000 are there where all the parts are different than each other and all the parts are odd.
;
> 
;
> #not change, since
;
> #(1+x)(1+x^2)(1+x^3)(1+x^5)...(1+x^1000) =
;
> #(1-x^2)/(1-x) * (1-x^4)/(1-x^2) * (1-x^6)/(1-x^3) * ... * (1-x^2000)/(1-x^1000) =
;
> #1/(1-x) * 1/(1-x^3) * 1/(1-x^5) * ... * 1/(1-x^1999) =
;
> #the G.F. of "odd part partitions"
;
> 
;
> 
;
> #Q6
;
> #(a) How many rooted labelled trees are there with 31 vertices?
;
> #n^(n-2) = 
;
> 31^29
17761887753093897979823770061456102763834271
;
> #(b) How many rooted labelled trees are there with 31 vertices where the root has exactly two children.
;
> #Write a procedure
;
> T2child:=proc(N) local i, a, z, L:
> a:=1;
> a:= a+ (z^2/2!);
> L:=FunEqToSeq(a,z,N):
> [seq(L[i]*i!, i=1..N)];
> end:
> T2child(31)
[1, 0, 3, 0, 60, 0, 3150, 0, 317520, 0, 52390800, 0, 12843230400, 0, 4382752374000, 0, 1986847742880000, 0, 1155153277710432000, 0, 838011196011749760000, 0, 742058914068404412480000, 0, 787724078011075453248000000, 0, 987468397792455300321600000000, 0, 1443283810213452666950050560000000, 0, 2432835272591051151727678975200000000]
;
> #n = 2432835272591051151727678975200000000
;
> #(c) How many rooted labelled trees are there with 31 vertices where  each vertex must have either zero, one, three, or four children.
;
> 
;
> #USE the procedure SeqRTchild in HW22
;
> SeqRTchild := proc(S, N) local i, r, s, L:
> r := 1 + add(z^s/s!, s in S):
> L := FunEqToSeq(r, z, N):
> seq(L[i]*i!, i = 1 .. N):
> end:
> SeqRTchild({1,2,3,4}, 31)
1, 2, 9, 64, 625, 7770, 117390, 2088520, 42771960, 991090800, 25635767850, 732235165200, 22890759391500, 777398836414200, 28501053507927000, 1121908690738836000, 47194400446765572000, 2112854517933207048000, 100302903229033765260000, 5032863920347902999360000, 266142789859931099850735000, 14793716799246351968271270000, 862334292493260819652189770000, 52598740360757139570304122840000, 3350601497282429844614781621000000, 222502645937108446633845155034000000, 15377726069589880161099060181555500000, 1104405005369409845057238883356756000000, 82305294967517874944444655399748251000000, 6356500157372156884942344746141640750000000, 508119985226652382713840418251162448830000000
;
> #508119985226652382713840418251162448830000000
;
> 
;
> #(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.
;
> #USE the procedure SeqRTchildNone in HW22
;
> 
;
> 
> SeqRTchildNone := proc(S, N) local i, r, s, L:
> r := add(z^s/s!, s in S):
> L := FunEqToSeq(exp(z) - r, z, N):
> seq(L[i]*i!, i = 1 .. N):
> end:
> SeqRTchildNone({1,2,3,4}, 31)
1, 0, 0, 0, 0, 6, 7, 8, 9, 10, 13871, 60996, 195637, 546560, 1411425, 427249696, 4124980929, 26013422934, 134201794555, 614270986500, 72817031988981, 1211924018940580, 12610860108434875, 103535416865167920, 734250836621295625, 45715497965321732626, 1118451164263614198837, 17224976603614475727388, 205357624826971857095129, 2077663816106417272277280, 84143481803932766681384581
;
> #841434818039327666813845
;
> 
;
> #Q7
;
> #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).
;
> #                 ¡
;
> #             |       |
;
> #             ¡       ¡
;
> #      |      |       |      |    
;
> #      ¡      ¡       ¡      ¡
;
> #    |   |  |   |   |   |   |  |
;
> #    ¡   ¡  ¡   ¡   ¡   ¡   ¡  ¡
;
> #
;
> #BZ(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
;
> 
;
> 
;
> 
;
> 
;
> 
;
> 
;