# Okay to post
# Tifany Tong, December 15th, 2020, Final Exam

# 1a.) [0,0,0] -> [30,25,20]

# (30 + 25 + 20)! / (30! * 25! * 20!) = 2478456799816702091914145225486880

# 1b.)

# NuGW([30, 25, 20], {[0, 0, 1], [0, 1, 0], [1, 0, 0]}) =
#                 41512613892711511465063226481480

# I got the NuGW function from the ComboProj3 Maple functions. 

# 1c.) NuW([30, 25, 20], {[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 1], [2, 2, 2]}) =
#               31831650298097356165593942880232160

# I got the NuW function from the ComboProj3 Maple functions.

# 1d.) 
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], {[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 1], [2, 2, 2]}) =
#               3818966446210163616599115660989544

# I modified the NuGW function conditions. 

# 1e.) 

#3d:
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); end if; end proc
SeqGW := proc(A, K) local i; [seq(NuGW([i, i, i], A), i = 1 .. K)]; end proc

#2d:
NuGW1 := proc(Pt, A) local a; option remember; if Pt[1] < 0 or Pt[2] < 0 or Pt[1] < Pt[2] then RETURN(0); elif Pt = [0, 0] then RETURN(1); else add(NuGW1(Pt - a, A), a in A); end if; end proc
SeqGW1 := proc(A, K) local i; [seq(NuGW1([i, i], A), i = 1 .. K)]; end proc;

#4d:
NuGW2 := proc(Pt, A) local a; option remember; if Pt[1] < 0 or Pt[2] < 0 or Pt[3] < 0 or Pt[4] < 0 or Pt[1] < Pt[2] or Pt[2] < Pt[3] or Pt[3] < Pt[4] then RETURN(0); elif Pt = [0, 0, 0, 0] then RETURN(1); else add(NuGW2(Pt - a, A), a in A); end if; end proc;
SeqGW2 := proc(A, K) local i; [seq(NuGW2([i, i, i, i], A), i = 1 .. K)]; end proc;

# I got the first 20 terms of each via the SeqGW functions for each of the dimensions (2d,3d, and 4d). I saw the pattern that it followed
# was k-dimensional Catalan numbers.

# The general form for k-dimensional appears to be:
# (k*n)! * mul(i!/(n+i)!, i=0..k)

# 2a.) For each of the letters in the length 30-word, there are 4 choices: 0,1,2, or 3. Thus, there are a total of
# 4^30 = 1152921504606846976 words.

# 2b.) add(coeff((x^4 + x^3 + x^2 + x)^k, x, 300), k = 75 .. 300) =
# 18012939919656512113252584133785878056327163962817704791464695718041992634738504938769

# The weight enumerator of alphabet {1,2,3,4} is x+x^2+x^3+x^4. k represents the length. We know that at minimum (with just 4's), the 
# length can be 75 while at max (with just 1's) the length can be 300. So I add the coefficient of x^300 of (x^4 + x^3 + x^2 + x)^k for k = 75
# to 300 to get my answer.

# 2c.) The weight enumerator of the alphabet is: x + x^2 + x^3 + ... = x/1-x. 
# Thus, the weight enumerator of all words: sum((x/1-x)^k, k=0..infinity) = 1/(1 - x/(1-x)) = (1-x)/(1-2x)
# taylor((1-x)/(1-2x),x=0,10) = 1 + x + 2*x^2 + 4*x^3 + 8*x^4 + 16*x^5 + 32*x^6 + 64*x^7 + 128*x^8 + 256*x^9 + O(x^10)

# From here, we can see that the explicit formula is 2^(n-1). 

# 2d.) The weight enumerator of the alphabet {1,4,7,10...} is x + x^4 + x^7 + x^10 + ... = x/(1-x^3) 
# The enumerator for all words is:
# f:= (1/(1-x/(1-x^3))) = (x^3-1)/(x^3+x-1)

# g:=taylor(f, x = 0, 30) =
#          2    3      4      5      6      7      8       9
# 1 + x + x  + x  + 2 x  + 3 x  + 4 x  + 6 x  + 9 x  + 13 x 
#          10       11       12       13       14        15
#    + 19 x   + 28 x   + 41 x   + 60 x   + 88 x   + 129 x  
#           16        17        18        19        20         21
#    + 189 x   + 277 x   + 406 x   + 595 x   + 872 x   + 1278 x  
#            22         23         24         25         26
#    + 1873 x   + 2745 x   + 4023 x   + 5896 x   + 8641 x  
#             27          28          29    / 30\
#    + 12664 x   + 18560 x   + 27201 x   + O\x  /

# convert(f, parfrac) =
#                                 x     
#                          1 - ----------
#                               3        
#                              x  + x - 1

# The generating function is 1-(x)/(x^3+x-1). 

# 2e.) The limit of a(n+1)/a(n) seems to approach 1.465571232. I tested the values of higher values of n of 
# evalf(coeff(taylor(f,x,n+2), x, n+1)/(coeff(taylor(f,x,n+1), x, n))) such as n=10000. 

# 3a.) The egf of set partitions is exp(exp(x)-1).
 
# 51!*coeff(taylor(exp(exp(x)-1),x=0,52),x,51) = 3263983870004111524856951830191582524419255819477

# 3b.)

# f:=exp(x)-1:
# The egf is: sum((f^(3i+1))/(3i+1)!, i=0..infinity) 

# coeff(taylor(add(f^(3*i + 1)/(3*i + 1)!, i = 0 .. 52), x = 0, 52), x, 51)*51! =
#        1089030250824782148720306369738651363734233026160

# 3c.) 
# f:=sinh(x)
# sum(x^(2n+1)/(2n+1)!, n=0..infinity) = sinh(x). Then, the egf is sum(f^i/(i!), i = 0..infinity) = e^(sinh(x)) 
# since the components themselves can only be of odd size and the number of components can be anything.

# coeff(taylor(add(f^(i)/(i)!, i = 0 .. 52), x = 0, 52), x, 51)*51! = 101595492022700597152023270326642584710021120

# 3d.) 

# f:= sum(x^(2n+1)/(2n+1)!, n=0..infinity) = sinh(x)
# The egf is: sum((f^(3i+1))/(3i+1)!, i=0..infinity) 

# coeff(taylor(add(f^(3*i + 1)/(3*i + 1)!, i = 0 .. 52), x = 0, 52), x, 51)*51! = 
#           30143119660583350838086153637731292910753195

# 4a.) 


# My notation here means that {1} = a, {2} = b, {3} = c. Then I show the possible partitions after for each case. 

# {1} {2} {3} --> a b c --> {a,b,c}, {a,b}{c}, {a}{b,c}, {a,c}{b}, {a}{b}{c} -->

# - { {1},{2},{3} }
# - { {{1},{2}},{{3}} }
# - { {{1}},{{2},{3}} }
# - { {{1},{3}},{{2}} }
# - { {{1}},{{2}},{{3}} }

# {1,2}, {3} --> a b --> {a,b}, {a}{b}

# - { {{1,2},{3}} }
# - { {{1,2}},{{3}} }

# {1,3}, {2} --> a b --> {a,b}, {a}{b}

# - { {{1,3},{2}} }
# - { {{1,3}},{{2}} }

# {2,3}, {1} --> a b --> {a,b}, {a}{b}

# - { {{2,3},{1}} }
# - { {{2,3}},{{1}} }

# {123} --> a --> {a}  
# - {{1,2,3}}

# There are a total of 12. 


# 4b.) 

# I use the same notation as 4a. 

# n = 1:
# {1} --> a --> {a}

# 1 total

# n = 2:
# {1} {2} --> a b --> {a,b}, {a}{b}

# {1,2} --> a --> {a} 

# 3 total

# n = 3:
# 12 total

# n= 4:
# {1} {2} {3} {4} - 15
# {1,2} {3} {4}
# {1,3} {2} {4}
# {1,4} {2} {3} 
# {2,3} {1} {4}
# {2,4} {1} {3}
# {3,4} {1} {2} - (4 C 2) * 2 = 12
# {2,3} {1,4}
# {2,4} {1,3}
# {3,4} {1,2} 
# {1,2} {3,4}
# {1,3} {2,4}
# {1,4} {2,3}  - (4 C 2) * 2 * (2 C 2) * 2/2 = 12
# {1,2,3} {4}
# {1,2,4} {3}
# {1,3,4} {2}
# {2,3,4} {1}  - (4 C 3) * 5 = 20 
# {1,2,3,4}    - 1

# 60 numbers

# {1}{2}{3}{4}{5} -> 52
# {1,2} {3,4,5} --> (5 C 2) * 2 * (3 C 3) * 5 = 10 * 2 * 1 * 5 = 100
# {1,2} {3,4} {5} --> (5 C 2) * 2 * (3 C 2) * 2 = 10 * 2 * 3 * 2 = 120/2 = 60
# {1,2} {3} {4} {5} --> (5 C 2) * 2 = 20
# {1,2,3} {4,5} --> (5 C 3) * 5 * (2 C 2) * 2 = 10 * 5 * 2 = 100
# {1,2,3} {4} {5} --> (5 C 3) * 5 = 50
# {1,2,3,4} {5} --> (5 C 4) * 15 = 75
# {1,2,3,4,5} --> 1

# 52 + 100 + 60+ 20 + 100 + 50 +75 + 1 = 212 + 120 + 125 + 1 = 358

# Sequence: 1,3,12,60, 358

# This is in the OEIS as A258. The egf is exp(exp(exp(x)-1)-1).

# 4c.) N/A 

# 5a.) 

# I used the pn function from lecture 24's maple code.

# pn(1000) = 24061467864032622473692149727991

# 5b.) 

# I used the pnC functin from lecture 24's maple code. 

# pnC(1000, {1}, 2) = 8635565795744155161506

# 5c.) 

# I used the pnD functin from lecture 24's maple code. 

# pnD(1000, 1) = 8635565795744155161506

# 5d.) 

 pnkDC := proc(n, k, C, m, d) local k1, S:
 option remember:
 if n < k 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) and k = 1 then RETURN(1):
   else RETURN(0): fi: 
fi:
if not member(k mod m, C) then RETURN(0): fi:
S := 0:

for k1 to k - d do
    if member(k1 mod m, C) then S := S + pnkDC(n - k, k1, C, m, d): fi: 
od:
S: 
end:

pnDC := proc(n, d, C, m) local k:
add(pnkDC(n, k, C, m, d), k = 1 .. n):
end: 

# pnDC(1000, 1, {1}, 2) = 517035762467311

# 6a.) 

# L := TreeSeqL(31, t);
# add(coeff(L[31], t, i), i = 1 .. 31) = 550618520345910837374536871905139185678862401

# 6b.)

# For a rooted labelled tree with 31 vertices to have a root with exactly 2 children, we first have to choose one of the 31
# vertices to be the root. Then, we there are two subtrees that will represent the children. The total number of vertices in these
# subtrees must sum to 30. Thus, when we sum from k=1 to 29 (as we cannot have an empty tree), we choose k of the possible 30 to represent
# one tree and the remaining to represent the other tree. From this, we find the number of trees corresponding to that number of vertices. We 
# divide by 2 to avoid overcounting. 


test := proc(n) local t, L, i:
L := TreeSeqL(n, t):
add(coeff(L[n], t, i), i = 1 .. n):
end:

# 31/2*add(binomial(30, k)*test(k)*test(30 - k), k = 1 .. 29) = 
#          205662364170099390000000000000000000000000000



# 6c.)

FunEqToSeq := proc(PHI, z, N) local f, i, j, x:
f := x:
for i 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:

SeqRTchild := proc(S, N) local i, mid, s, L, ans:
mid := 1 + add(z^s/s!, s in S):
L := FunEqToSeq(mid, z, N):
seq(L[i]*i!, i = 1 .. N):
end:


# SeqRTchild({1, 3, 4}, 31)[31] = 388391178300656853181332829972846230000000


# 6d.) 

SeqRTchildNone := proc(S, N) local i, mid, s, L, ans:
mid := add(z^s/s!, s in S):
L := FunEqToSeq(exp(z) - mid, z, N):
seq(L[i]*i!, i = 1 .. N):
end:

# SeqRTchildNone({1,3,4}, 31)[31] = 2863465748628395267057869436794752181

# 7a.) 

# BT(4) = 

# {
#  [[[],[]],[[],[]]],
#  [[],[[],[[],[]]]], 
#  [[],[[[],[]],[]]],
#  [[[[],[]],[]],[]],
#  [[[],[[],[]]],[]]
# }

# Graphically these represent:

#                          o			
#                        /   \
#                       o     o
#                      / \   / \
#                     o   o o   o

#			   o
#      			  / \
#                        o   o
#                           / \
#                          o   o
#                             / \
#                            o   o

#			  o
#			 / \
#                       o   o
#                          / \
#                         o   o
#                        / \
# 			o   o

#                          o
#			  / \
#                        o   o
#                       / \
#		       o   o
#                     / \
#                    o   o

#			  o
#      			 / \
#                       o   o
#                      / \
#		      o   o
#                        / \
#                       o   o


# 7b.) N/A