#OK to post test
#Kent Mei, 12/15/20, Final Exam

#---------------------------------
#Part 1

#a) 
#Using an explicit formula, we get that the number of ways to 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] is equal to (30+25+20)!/(30!*25!*20!)
#The answer is 2478456799816702091914145225486880 ways.

#(To double check, we can use NuW([30,25,20],{[1,0,0],[0,1,0],[0,0,1]}); from the ComboProject3.txt and we get the same answer).

#~~~~~~~~~~

#b)
#We can use NuGW([30,25,20],{[1,0,0],[0,1,0],[0,0,1]}); from ComboProject3.txt.

#The answer is 41512613892711511465063226481480 ways.

#~~~~~~~~~~

#c)
#NuGW([30,25,20],{[1,0,0],[0,1,0],[0,0,1],[1,1,1],[2,2,2]});

#The answer is 702157829467026190582908694797444 ways.

#~~~~~~~~~~

#d)
#We can modify NuGW to get the answer:

NuGWAlt:=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(NuGWAlt(Pt-a,A), a in A):
fi:

end:

#NuGWAlt([30,25,20],{[1,0,0],[0,1,0],[0,0,1],[1,1,1],[2,2,2]});

#The answer is 3818966446210163616599115660989544 ways.

#~~~~~~~~~~

#e)
#Wrote a maple program NuKDimGoodWalks which determines the number of good walks in the k-dimensional case.
#Used to see if there are any trends.

NuKDimGoodWalks:=proc(Pt,k) local i, pt, sum:
option remember:

if (Pt = [0$k]) then
	return 1:
fi:

for i from 1 to k do:
	if (Pt[i]<0) then
		return(0):
	fi:
	if i < k then
		if (Pt[i] < Pt[i+1]) then
			return(0):
		fi:
	fi:
od:

sum := 0:
for i from 1 to k do:

	pt:= Pt:
	pt[i] := Pt[i]-1:

	sum := sum + NuKDimGoodWalks(pt,k):

od:

sum:

end:


#[seq(NuKDimGoodWalks([n$2],2),n = 1..10)]
#[1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796
#Catalan numbers: (2n)!/(n!(n+1)!)

#[seq(NuKDimGoodWalks([n$3],3),n = 1..10)]
#[1, 5, 42, 462, 6006, 87516, 1385670, 23371634, 414315330, 7646001090]
#3D Catalan numbers: 2*(3n)!/(n!(n+1)!(n+2)!)

#[seq(NuKDimGoodWalks([n$4],4),n = 1..10)]
#[1, 14, 462, 24024, 1662804, 140229804, 13672405890, 1489877926680, 177295473274920, 22661585038594320]
#4D Catalan numbers: 12*(4n)!/(n!(n+1)!(n+2)!(n+3)!)

#[seq(NuKDimGoodWalks([n$5],5),n = 1..10)]
#[1, 42, 6006, 1662804, 701149020, 396499770810, 278607172289160, 231471904322784840, 219738059326729823880, 232553551737813227594400]
#5D Catalan numbers: 1!*2!*3!*4!*(5n)! / (n!(n+1)!(n+2)!(n+3)!(n+4)!)


#Going off of the pattern from the above sequences, it seems like an explicit formula in terms of n and k is:
#1!*2!*3!*...*(k-1)!*(kn)! / (n!(n+1)!(n+2)!...(n+k-1)!)

#or alternatively,
#Product(i! / (n+i)!, i = 0..k-1) * (kn)!




#---------------------------------
#Part 2

#a) 
#There are 30 positions in a word of length 30 and each position there are 4 choices of "numbers" in the alphabet to choose from.
#So, the total number of words in the alphabet given of length 30 is 4^30 =

#The answer is 1152921504606846976 words.

#~~~~~~~~~~

#b)
#Using the procedures CompsGF(S,x) and GFseq(f,x,N) from M8.txt,
#gf := CompsGF({1,2,3,4}, x);
#GFseq(gf,x,300)[301];

#The answer is 18012939919656512113252584133785878056327163962817704791464695718041992634738504938769 words.


#~~~~~~~~~~

#c)

#An explicit formula for a(n) is a(n) = 2^(n-1). (Also, a(0) = 1).

#To explain this, note that as a base case, a(1) = 1 = 2^0 since there is only one word that adds up to 1 which is 1.
#Using induction, assume that a(m) = 2^(m-1) for all 1 <= m < k. We need to show that a(k) = 2^(k-1). 
#In order to form a composition of integers that adds up to k, we can append k to all words of length 0, append k-1 to all words of length 1, and so on until we append 1 to all words of length k-1. 
#So, this means that a(k) = a(0) + a(1) + ... + a(k-2) + a(k-1)
#a(k) = 1 + Sum(2^(m-1), m=1..k-1)
#a(k) = 1 + (2^(k-1) - 1)
#a(k) = 2^(k-1) as desired.

#So, by induction, the answer is a(n) = 2^(n-1).


#~~~~~~~~~~

#d)

#Note that Sum(a(n)*x^n, n = 0..infinity) is equivalent to the generating function for a(n).

#Using the procedure CompsGFcon(a,C,x) from M8.txt

#gf := CompsGFcon(3,{1},x);
#The answer is (x-1)*(x^2+x+1)/(x^3+x-1).


#~~~~~~~~~~

#e)

#Using Maple, I did:
#L:=GFseq(gf,x,5000):
#evalf(L[5000]/L[4999]);
#1.4655712318767680266567312252199391080255775684723

#Searching information about this value, I ended up learning that this sequence is the Narayana sequence is the (k+1)st term of the Narayan series can be defined as N(k+1) = N(k) + N(k-2). 
#lim( N(k+1)/N(k) )= 1 + lim( N(k-2)/N(k) )
#lim( N(k+1)/N(k) )= 1 + lim( N(k-2)/N(k-1)) * lim( N(k-1)/N(k))
#If we define lim( N(k+1) / N(k)) = L, we get
#L = 1 + (1/L^2)
#L^3 - L^2 - 1 = 0

#L ~= 1.465571231876768026656731
#alternatively,
#L = the supergolden ratio which is
#L = (1+ ((29 + 3*sqrt(93)) / 2)^(1/3) + ((29 - 3*sqrt(93)) / 2)^(1/3) ) / 3 



#---------------------------------
#Part 3

#a)

#The egf enumerating set-partitions is exp(exp(x) - 1).

#f := taylor(exp(exp(x)-1),x=0,52):
#coeff(f, x, 51) * 51!

#The answer is 3263983870004111524856951830191582524419255819477 set-partitions.

#~~~~~~~~~~

#b)

#The egf for non-empty sets is just exp(x) - 1.
#The egf enumerating set partitions where the number of components belongs to {1,4,7,10,...} can be found by doing:
#assume(abs(x) < 1);
#egf := sum((exp(x)-1)^(3*n+1)/(3*n+1)!, n = 0..infinity);

#We get that the egf is:
#(exp(x)-1)*((1/3)*exp(exp(x)-1)/(exp(x)-1)-(1/3)*exp(-(1/2)*exp(x)+1/2)*cos((1/2)*3^(1/2)*(exp(x)-1))/(exp(x)-1)+(1/3)*3^(1/2)*exp(-(1/2)*exp(x)+1/2)*sin((1/2)*3^(1/2)*(exp(x)-1))/(exp(x)-1))

#Trying to simplify it in Maple gets:
#(1/3)*3^(1/2)*exp(-(1/2)*x)*sin((1/2)*3^(1/2)*x)-(1/3)*exp(-(1/2)*x)*cos((1/2)*3^(1/2)*x)+(1/3)*exp(x)


#The number of set partitions for the set {1,...,51} can be found as follows:
#coeff(taylor(egf,x=0,53),x,51) * 51!;

#The number of set partitions is 1089030250824782148720306369738651363734233026160.

#~~~~~~~~~~

#c)

#The egf for nonempty sets of odd size is 0 + Sum(1/(2*n+1)! * x^(2*n+1), n = 0..infinity) = sinh(x).
#So, since the number of components can be any non-negative integer, we can just use the fundamental theorem of exponential generating functions to get that the egf is:
#egf := exp(sinh(x))

#The number of such set partitions for the set {1,...,51} is:
#coeff(taylor(egf,x=0,53),x,51)*51!;

#101595492022700597152023270326642584710021120 set partitions.

#~~~~~~~~~~

#d)

#For this problem, we combine the ideas from parts b and c.
#The egf for nonempty sets of odd size is sinh(x)
#So, the egf for set partitions where number of components belongs to {1,4,7,...} and the components are odd is:
#egf := sum((sinh(x))^(3*n+1)/(3*n+1)!, n = 0..infinity);

#sinh(x)*((1/3)*csch(x)*exp(sinh(x))-(1/3)*csch(x)*exp(-(1/2)*sinh(x))*cos((1/2)*3^(1/2)*sinh(x))+(1/3)*csch(x)*3^(1/2)*exp(-(1/2)*sinh(x))*sin((1/2)*3^(1/2)*sinh(x)))


#The number of such set partitions is:
#coeff(taylor(egf,x=0,53),x,51)*51!;


#30143119660583350838086153637731292910753195 set partitions.


#---------------------------------
#Part 4

#a) 
#All super-set partitions with n=3:
#{ {{1}}, {{2}}, {{3}} }
#{ {{1,2}}, {{3}} }
#{ {{1},{2}}, {{3}} }
#{ {{1,3}}, {{2}} }
#{ {{1},{3}}, {{2}} }
#{ {{2,3}}, {{1}} }
#{ {{2},{3}}, {{1}} }
#{ {{1,2,3}} }
#{ {{1,2},{3}} }
#{ {{1,3},{2}} }
#{ {{2,3},{1}} }
#{ {{1},{2},{3}} }


#~~~~~~~~~~

#b)
#Sum(s[2](n)*x^n/n!, n=0..infinity) is the egf corresponding to s[2](n).

#A super-set-partition of order 2 is a set of set partitions.
#We know that the egf for the atomic object of set partitions is usually exp(exp(x)-1). However, we have to ensure that set partition itself must be nonempty so we consider the egf as exp(exp(x)-1)-1.
#Then, using the Fundamental Theorem of Exponential Generating Functions, we get that the egf corresponding to super-set-partitions of order 2 is:
#Sum(s[2](n)*x^n/n!, n=0..infinity) = exp(exp(exp(x)-1)-1);


#egf := exp(exp(exp(x)-1)-1);
#f := taylor(egf,x=0,12);
#[seq(coeff(f,x,n) * n!, n = 1..10)]
#[1, 3, 12, 60, 358, 2471, 19302, 167894, 1606137, 16733779]

#It is in the OEIS as A258.

#~~~~~~~~~~

#c)
#Following the trend of doing exp(exp(exp(exp(...)-1)-1)-1)
#and using that egf to produce the sequence s[m](n),

#m = 3: A307
#m = 4: A357
#m = 5: A405
#m = 6: A1669
#m = 7: A81624
#m = 8: A81629
#m = 9: A81697
#m =10: A81740
#m =11: N/A

#The smallest m for which it is not in the OEIS is m=11.


#---------------------------------
#Part 5

#a)

#Using pnFast(n) from M24.txt

#pnFast(1000)
#There are 24061467864032622473692149727991 integer partitions of 1000.

#~~~~~~~~~~

#b)

#Using pnOddSeq(N) from M24.txt

#pnOddSeq(1000)[1000];
#There are 8635565795744155161506 integer partitions of 1000 with only odd parts.

#~~~~~~~~~~

#c)

#Knowing from Euler's theorem, it should be the same answer as part b. But we will use Maple to check.
#Using pnDistinctSeq(N) from M24.txt

#pnDistinctSeq(1000)[1000];
#There are 8635565795744155161506 integer partitions of 1000 with distinct parts.


#~~~~~~~~~~

#d)

#Having coded pnDC(n,d,C,m) in hw24 and finding out that the sequence [seq(pnDC(n,1,{1},2),n=1..40)] matches A700 in the OEIS, we can just find the 1000th term in the OEIS b file instead of taking a lot of processing power to find the run the Maple code.

#From hw24KentMei.txt,

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:

#Alternatively, we can use the generating function to find the answer.

pnOddDistinctSeq:=proc(N) local f,q,i:
f:=mul(1+q^(2*i+1),i=0..trunc(N/2)):
f:=taylor(f,q=0,N+1):
[seq(coeff(f,q,i),i=1..N)]:
end:

#pnOddDistinctSeq(1000)[1000];

#So, we find that there are 517035762467311 integer partitions of 1000 with distinct and odd parts.


#---------------------------------
#Part 6

#a)

#The number of labeled trees with n nodes is n^(n-2).
#Rooted trees choose 1 of the n nodes to be the root so in total, there are n^(n-1) rooted labelled trees

#So, 31^30 = 550618520345910837374536871905139185678862401
#There are 550618520345910837374536871905139185678862401 rooted labelled trees with 31 vertices.

#~~~~~~~~~~

#b)

#Considering rooted labelled trees with 31 vertices where the root has exactly two children.

#We choose 1 out of 31 vertices to be the root. 
#Since the root must have two children, the children are the roots of their own rooted labelled trees except with no restrictions on the number of children for those.
#We have to allocate a number x out of 30 vertices to be for one tree and a number 30-x vertices for the other tree.
#We also have to choose x out of 30 labels to assign to the vertices in one tree and the rest are left over for the other tree.
#Note that 1|29 is the same as 29|1, so we take the number we get divided by 2.
#So, the total number of rooted labelled trees is 31 * Sum(binomial(30,x) * x^(x-1) * (30-x)^(29-x), x = 1..29) / 2;

#The total number of rooted labelled trees with 31 vertices where the root has exactly 2 children is 205662364170099390000000000000000000000000000.


#~~~~~~~~~~

#c)

#Using SeqRTChild(S,N) from hw22KentMei.txt

SeqRTchild:=proc(S,N) local eq, s, L:

eq := 1:
for s in S do
	eq := eq + (z^s / s!):
od:

L := FunEqToSeq(eq, z, N):

[seq(L[n]*n!, n = 1..N)]:
end:


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

#388391178300656853181332829972846230000000 rooted labelled trees with 31 vertices match the description.


#~~~~~~~~~~

#d)

#Using SeqRTchildNone(S,N) from hw22KentMei.txt

SeqRTchildNone:=proc(S,N) local eq, s, L:

eq := exp(z):
for s in S do
	eq := eq - (z^s / s!):
od:

L := FunEqToSeq(eq, z, N):

[seq(L[n]*n!, n = 1..N)]:
end:

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

#2863465748628395267057869436794752181 rooted labelled trees with 31 vertices match the description.

#---------------------------------
#Part 7

#a)

BT:=proc(n) local Ans, BT1, BT2, i, j, k:
option remember:

if n = 1 then
	return {[]}:
fi:

Ans := {}:

for i from 1 to n-1 do
	BT1 := BT(i):
	BT2 := BT(n-i):

	Ans := Ans union {seq(seq([BT1[j], BT[k]], j = 1..nops(BT1)), k = 1..nops(BT2))}:

od:

end:

#BT(4) (assuming the description was supposed to be the set of such creatures with n leaves) is as follows:

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

#~~~~~~~~~~

#b)

b:=proc(n) local Ans, i:
option remember:

if n = 0 then
	return 0:
fi:

if n = 1 then
	return 1:
fi:

Ans := 0:

for i from 1 to n-1 do
	Ans := Ans + bt(i)*bt(n-i):
od:

end:


#We can see from the above code that b(1) = 1 and b(n) = Sum(b(i)*b(n-i), i = 1..n-1) for all n >= 1.
#We define B(x) = Sum(b(n)*x^n, n = 0..infinity).
#Note that b(0) = 0 since there are no complete binary trees with 0 leaves.

#     B(x)       = Sum(b(n)*x^n, n = 0..infinity)
#  => B(x)       = Sum(b(n)*x^n, n = 1..infinity)
#  => B(x)^2     = (Sum(b(n)*x^n, n = 1..infinity))^2
#  => B(x)^2     = Sum( Sum(b(i)*b(n-i),i = 1..n-1), n = 1..infinity )
#  => B(x)^2.    = Sum( b(n)*x^n, n = 2..infinity )
#  => x + B(x)^2 = x + Sum( b(n)*x^n, n = 2..infinity )
#  => x + B(x)^2 = b(1)*x^1 + Sum( b(n)*x^n, n = 2..infinity )
#  => x + B(x)^2 = Sum( b(n)*x^n, n = 1..infinity )
#  => x + B(x)^2 = B(x)

# As such, we have shown that x + B(x)^2 = B(x) as desired.