> #ok to post
> #Yifan Zhang, 12/15/2020, Final Exam
> ------------------------------------------------------
> #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]
> NuW:=proc(Pt,A) local a:
> option remember:
> 
> if Pt[1]<0 or Pt[2]<0 or Pt[3]<0 then
> RETURN(0):
> elif Pt=[0,0,0] then
> RETURN(1):
> else
> add(NuW(Pt-a,A),a in A):
> fi:
> end:
> NuW([30,25,20], {[1,0,0],[0,1,0],[0,0,1]});
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
> 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[2]<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]});
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],[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).
> NuGW2:=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(NuGW2(Pt-a,A),a in A):
> fi:
> 
> end:
> NuGW2([30,25,20], {[1,0,0],[0,1,0],[0,0,1],[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.
> #The sequence generated is Catalan numbers.
> #Formula of a(n) = 0!*1!*..*(k-1)! *(k*n)! / ( n!*(n+1)!*..*(n+k-1)! )
> 
> ------------------------------------------------------
> #Q2.
> #(a) How many words in the alphabet {0,1,2,3} are there of length 30?
> 4^30;
1152921504606846976
> 
> #(b) How many words in the alphabet {1,2,3,4} are there that add-up to 300?
> #Wt. Enumerator: x^1+x^2+x^3+x^4
> coeff(sum((x^1+x^2+x^3+x^4)^k, k=1..300),x,300);

18012939919656512113252584133785878056327163962817704791464695718041992634738504
938769
> 
> #(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.
> #Wt. Enumerator of atom: x+x^2+x^3+x^4+... = x/(1-x)
> #Wt. Enumerator of k-letters: (x/(1-x))^k
> #Wt. Enumerator of all words: Sum((x/(1-x))^k, k=0..infinity) = (-1+x)/(2*x-1)
> #Number of words that add-up to n: taylor((-1+x)/(2*x-1), x=0, n);
> 
> #(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)
> CompsGFcon:=proc(a,C,x) local c:
> factor( 1/(1-add(x^c, c in C)/(1-x^a))):
> end:
> GFseq:=proc(f,x,N) local f1,i:
> f1:=taylor(f,x=0,N+1):
> [seq(coeff(f1,x,i),i=0..N)]:
> end:
> CompsGFcon(3,{1},x);
(-1+x)*(x^2+x+1)/(x^3+x-1)
> #Generating function (-1+x)*(x^2+x+1)/(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.
> a:=n->GFseq((-1+x)*(x^2+x+1)/(x^3+x-1),x,n+1)[n]:
> evalf(a(101)/a(100));
1.465571232
> evalf(a(1001)/a(1000));
1.465571232
> evalf(a(10001)/a(10000));
1.465571232
> #As n goes to infinity, the limit of a(n+1)/a(n) = 1.465571232
> 
> ------------------------------------------------------
> #Q3.
> #(a) What is the egf enumerating set-partitions. How many are there of the set
> {1,2,...,51}?
> #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}?
> f:=add((exp(x)-1)^(3*k+1)/(3*k+1)!, k=0..17):
> coeff(taylor(f,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}?
> f:=add((sinh(x))^k/k!, k=0..51):
> coeff(taylor(f, 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}?
> f:=add((sinh(x))^(3*k+1)/(3*k+1)!, k=0..17):
> coeff(taylor(f, x = 0, 52), x, 51)*51!;
30143119660583350838086153637731292910753195
> 
> ------------------------------------------------------
> #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.
> #Total of 3 element : {{{1}},{{2}},{{3}}}
> #Total of 2 element : {{{1,2}},{{3}}}
> # {{{1},{2}},{{3}}}
> # {{{1,3}},{{2}}}
> # {{{1},{3}},{{2}}}
> # {{{2,3}},{{1}}}
> # {{{2},{3}},{{1}}}
> #Total of 1 element: {{{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?
> #exp(exp(exp(x)-1)-1)
> seq(coeff(taylor(exp(exp(exp(x)-1)-1), x=0, 50),x,i)*i!, i=1..20);
1, 3, 12, 60, 358, 2471, 19302, 167894, 1606137, 16733779, 188378402,
2276423485, 29367807524, 402577243425, 5840190914957, 89345001017415,
1436904211547895, 24227076487779802, 427187837301557598, 7859930038606521508
> #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?
> #for m=3, exp(exp(exp(exp(x)-1)-1)-1)
> seq(coeff(taylor(exp(exp(exp(exp(x)-1)-1)-1), x=0, 50),x,i)*i!, i=1..20);
1, 4, 22, 154, 1304, 12915, 146115, 1855570, 26097835, 402215465, 6734414075,
121629173423, 2355470737637, 48664218965021, 1067895971109199,
24795678053493443, 607144847919796830, 15630954703539323090,
421990078975569031642, 11918095123121138408128
> #A000307
> #for m=4, A000357
> #for m=5, A000405
> #for m=6, A001669
> #for m=7, A081624
> #for m=8, A081629
> #for m=9, A081697
> #for m=10, A081740
> #for m=11, NOT FOUND
> 
> ------------------------------------------------------
> #Q5.
> #(a) How many integer partitions are there of 1000?
> pnk:=proc(n,k) local k1:
> option remember:
> 
> if k>n then RETURN(0): fi:
> 
> if k=n then RETURN(1): fi:
> 
> if n=1 then if k=1 then RETURN(1): else RETURN(0): fi:fi:
> 
> add(pnk(n-k,k1),k1=1..k):
> 
> end:
> pn:=proc(n) local k: add(pnk(n,k),k=1..n): end:
> pn(1000);
24061467864032622473692149727991
> 
> #(b) How many integer partitions of 1000 are there where all the parts are
> odd?
> pnkC:=proc(n,k,C,m) local k1,S:
> option remember:
> if k>n then
> RETURN(0):
> fi:
> 
> if k=n then
> if member(k mod m, C) then
> RETURN(1):
> else
> RETURN(0):
> fi:
> fi:
> 
> if n=1 then
> if member(1,C) then
> RETURN(1):
> else
> RETURN(0):
> fi:
> fi:
> 
> if not member(k mod m, C) then
> RETURN(0):
> fi:
> 
> 
> S:=0:
> for k1 from 1 to k do
> 
> if member(k1 mod m,C) then
> S:=S+ pnkC(n-k,k1,C,m):
> fi:
> 
> od:
> S:
> end:
> 
> pnC:=proc(n,C,m) local k:
> add(pnkC(n,k,C,m),k=1..n):
> end:
> pnC(1000, {1}, 2);
8635565795744155161506
> 
> #(c) How many integer partitions of 1000 are there where all the parts are
> different than each other?
> pnkD:=proc(n,k,d) local k1:
> option remember:
> 
> if k>n then RETURN(0): fi:
> 
> if k=n then RETURN(1): fi:
> 
> if n=1 then if k=1 then RETURN(1): else RETURN(0): fi:fi:
> 
> add(pnkD(n-k,k1,d),k1=1..k-d):
> 
> end:
> 
> pnD:=proc(n,d) local k:
> add(pnkD(n,k,d),k=1..n):
> end:
> 
> pnD(1000,1);
8635565795744155161506
> #The number of distinct integer partitions = the number of odd 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.
> pnkDC:=proc(n,k,d,C,m) local i:
> option remember:
> 
> if k > n or not member(k mod m, C) then
> return 0:
> fi:
> 
> if k = n then
> return 1:
> fi:
> 
> add(pnkDC(n-k,i,d,C,m),i=1..k-d):
> 
> end:
> 
> 
> pnDC:=proc(n,d,C,m) local i:
> 
> add(pnkDC(n,i,d,C,m), i = 1..n):
> 
> end:
> pnDC(1000,1,{1},2);
517035762467311
> 
> ------------------------------------------------------
> #Q6.
> #(a) How many rooted labelled trees are there with 31 vertices?
> read `M22.txt`;
> TreeSeq(31)[31];
17761887753093897979823770061456102763834271
> 
> #(b) How many rooted labelled trees are there with 31 vertices where the root
> has exactly two children.
> coeff(TreeSeqL(31, t)[31],t,2);
1788467407283698212855309926400000000
> 
> #(c) How many rooted labelled trees are there with 31 vertices where each
> vertex must have either zero, one, three, or four children.
> SeqRTchild:=proc(S,N) local i, r, z, L:
> r:=1;
> 
> for i from 1 to nops(S) do
> 
> r:= r+ (z^S[i]/S[i]!);
> 
> od:
> 
> L:=FunEqToSeq(r,z,N):
> [seq(L[i]*i!, i=1..N)];
> 
> end:
> 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.
> SeqRTchildNone:=proc(S,N) local i, r, z, L:
> r:=exp(z);
> 
> for i from 1 to nops(S) do
> 
> r:= r- (z^S[i]/S[i]!);
> 
> od:
> 
> L:=FunEqToSeq(r,z,N):
> [seq(L[i]*i!, i=1..N)];
> 
> end:
> SeqRTchildNone({1,3,4}, 31)[31];
2863465748628395267057869436794752181
> 
> ------------------------------------------------------
> #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).
> #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
> #Proof:
> #Since every tree is either a single leaf or a root with two subtrees, for
> every root or father node B(x), it has its own node value x, and two subtrees
> B(x)^2, so the recurrence B(x) = x+B(x)^2.
> 
> 
> 
>