#Ok to Post
# Final for Math 454(2), Fall 2020, Dr. Z.
#Start: Dec. 15, 9:00am
#Due: Dec. 16, 9:00am. EMAIL to ShaloshBEkhad@gmail.com 
#Subject: ComboFinal
#with an attachment called
#ComboFinalFirstLast.txt: e.g. ComboFinalDoronZeilberger.txt (PLEASE observe capitalization)
#INDICATE WHETHER IT IS OK to POST YOUR TEST


QUESTION #1:

(a) Our generating function is f:=1/(1-add(x^s[1]*y^s[2]*z^s[3], s in {[1,0,0],[0,1,0],[0,0,1]})) = 1/(x-y-z).
To get the number of walks from [0,0,0] to [30,25,20], we extract the coefficient of x^30y^25z^20 in the taylor series expansion.
Running coeff(taylor(coeff(taylor(coeff(taylor(f, x = 0, 31), x, 30), y = 0, 31), y, 25), z = 0, 31), z, 20); we get:
2478456799816702091914145225486880 total walks

(b) We can find the number of good paths by extending the program in the Maple code for lecture 14, NuGPaths, to 3 variables:
NuGPaths:=proc(m,n,k) option remember:
if (m<0 or n<0 or k<0 or m<n or n<k or m<k) then 
0:
elif m=0 and n=0 and k=0 then
1:
else
NuGPaths(m-1,n,k)+NuGPaths(m,n-1,k)+NuGPaths(m,n,k-1):
fi:
end:

Running NuGPaths(30, 25, 20), we get:
41512613892711511465063226481480 total walks

(c) Our generating function is f:=1/(1-add(x^s[1]*y^s[2]*z^s[3], s in {[1,0,0],[0,1,0],[0,0,1],[1,1,1],[2,2,2]})) = 1/(-x^2*y^2*z^2 - x*y*z - x - y - z + 1)
To get the number of walks from [0,0,0] to [30,25,20], we extract the coefficient of x^30y^25z^20 in the taylor series expansion.
Running coeff(taylor(coeff(taylor(coeff(taylor(f, x = 0, 31), x, 30), y = 0, 31), y, 25), z = 0, 31), z, 20); we get:
31831650298097356165593942880232160 total walks

(d) We can extend the function in part (b) to get the answer:
NuGPathsD:=proc(m,n,k) option remember:
if (m<0 or n<0 or k<0 or m<n or n<k or m<k) then 
0:
elif m=0 and n=0 and k=0 then
1:
else
NuGPathsD(m-1,n,k)+NuGPathsD(m,n-1,k)+NuGPathsD(m,n,k-1)+NuGPathsD(m-1,n-1,k-1)+NuGPathsD(m-2,n-2,k-2):
fi:
end:

Running NuGPathsD(30, 25, 20) we get
702157829467026190582908694797444 total walks

QUESTION #2:

(a) Let x be a word of length 30 in the alphabet {0,1,2,3}.
For each position i in the word, x[i], for i=1..30, x[i] can be any of 0,1,2,or 3.
Therefore, there are 4 x 4 x 4 x 4 x ... x 4 = 4^30 possible words.

(b) Let W be the infinite set of all words in {1,2,3,4}.
We have the relation, W = EMPTY (Union) W x {1} (Union) W x {2} (Union) W x {3} (Union) W x {4}.
If take the Weight of both sides, we get:
|W| = 1 + |W|*x + |W|*x^2 + |W|*x^3 + |W|*x^4.
Let |W|=f(x). Then, solving for f(x), we have the generating function f:=1/(1-x-x^2-x^3-x^4).

The number of words in the alphabet {1,2,3,4} which add up to 300 can be found by:
coeff(taylor(f,x=0,301),x,300); which gives:
18012939919656512113252584133785878056327163962817704791464695718041992634738504938769 total words

(c) For the alphabet, S={1,2,3,4,...}, the generating function is f:=1/(1-Sum(x^s, s in S)).
In our case, Sum(x^s, s in S) = x + x^2 + x^3 + ... = x/(1-x).
So, f:=normal(1/(1-x/(1-x))).
Running, seq(coeff(taylor(f, x = 0, 50), x, i), i = 1 .. 15); we get the sequence:
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384

Since a(n)=2^{n-1} for n=1..15 we can conjecture that a(n)=2^{n-1} for all positive integers n.

(d) For the alphabet, S={1,4,7,10,...}, the generating function is f:=1/(1-Sum(x^s, s in S)).
The weight enumerator of S is x+x^4+x^7+x^10+...+x^{3n-2}+... = x/(1-x^3).
So, f:=normal(1/(1-x/(1-x^3)))=Sum(a(n)*x^n,n=0..infinity).

(e) We calculate the ratio a(n+1)/a(n) for the first 45 terms:
L := [seq(evalf(coeff(taylor(f, x = 0, 50), x, i + 1)/coeff(taylor(f, x = 0, 50), x, i)), i = 1 .. 45)].
Running this we get the sequence:
[1., 1., 2., 1.500000000, 1.333333333, 1.500000000, 1.500000000, 1.444444444, 1.461538462, 1.473684211, 1.464285714, 1.463414634, 1.466666667, 1.465909091, 1.465116279, 1.465608466, 1.465703971, 1.465517241, 1.465546218, 1.465596330, 1.465571205, 1.465563267, 1.465573770, 1.465572956, 1.465569878, 1.465571114, 1.465571699, 1.465571121, 1.465571119, 1.465571303, 1.465571245, 1.465571205, 1.465571236, 1.465571239, 1.465571228, 1.465571231, 1.465571233, 1.465571232, 1.465571231, 1.465571232, 1.465571232, 1.465571232, 1.465571232, 1.465571232, 1.465571232]
We see that the ratio is converging to ~= 1.465571232

QUESTION #3:

(a). The egf for set partitions is e^{e^x-1}.
Let f:= e^{e^x-1}, then the number of set partitions of {1,2...,51} is 51!*coeff(taylor(f,x=0,52),x,51):
3263983870004111524856951830191582524419255819477 partitions

(b). Since the sizes of our components can be of any size, then our egf for the atomic objects is:
Sum(x^n/n!,n=1..infinity) = exp(x)-1.

The number of components in each partition, though, must be in {1,4,7,10,...}. Hence, our final egf is:
f:=add((exp(x)-1)^(3*i-2)/(3*i-2)!,i=1..infinity).

We will use the approximation f:=add((exp(x)-1)^(3*i-2)/(3*i-2)!,i=1..52) to find the number of set partitions for {1,2,...,51}.
Running 51!*coeff(taylor(f, x = 0, 52), x, 51), we get:
1089030250824782148720306369738651363734233026160 partitions

(c). Since the sizes of our components must be of odd size, then our egf for the atomic objects is:
Sum(x^(2*n-1)/(2*n-1)!,n=1..infinity) = sinh(x).

The number of components in each partition can be any non-negative integer. So, our final egf is:
f:=add((sinh(x))^i/i!,i=0..infinity) .

We will use the approximation f:=add((sinh(x))^i/i!,i=1..52) to find the number of set partitions for {1,2,...,51}.
Running 51!*coeff(taylor(f, x = 0, 52), x, 51), we get:
101595492022700597152023270326642584710021120 partitions.

(d). Since the sizes of our components must be of odd size, then our egf for the atomic objects is:
Sum(x^(2*n-1)/(2*n-1)!,n=1..infinity) = sinh(x).

The number of components in each partition, though, must be in {1,4,7,10,...}. Hence, our final egf is:
f:=add((sinh(x))^(3*i-2)/(3*i-2)!,i=1..infinity).
We will use the approximation f:=add((sinh(x))^(3*i-2)/(3*i-2)!,i=1..52) to find the number of set partitions for {1,2,...,51}
Running 51!*coeff(taylor(f, x = 0, 52), x, 51), we get:
30143119660583350838086153637731292910753195 partitions


QUESTION #4:

(a) List of 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}} }

There are 8 super-set partitions with n=3

(b) It seems that we have s[2](n) = SP(n) + SP(n-1) + ... + SP(1), where SP(n) is the number of set partitions of {1,2,...,n}

So, Sum(s[2](n)*x^n/n!, n=0..infinity) = Sum(add(SP(i),i=1..n)*x^n/n!,n=0..infinity).
For n from 1 to 15, we have the sequence:

[1, 3, 8, 23, 75, 278, 1155, 5295, 26442, 142417, 820987, 5034584, 32679021, 223578343, 1606536888, ...]

It is in the OEIS: A024716. The Stirling numbers of the second kind.


QUESTION #5:

(a) Using pnFast(1000) from lecture 24's code, we can compute the number of integer partitions of 1000, using Euler's recurrence:
There are 24061467864032622473692149727991 partitions.

(b) Using pnC(1000,{1},2) from lecture 24, we can get the number of integer partitions of 1000 where all parts are odd.
Running, we get 8635565795744155161506 partitions

(c) Using pnD(1000,1) from lecture 24's code, we can get all the intger partitions of 1000 where all parts have at least 1 difference between them. 
Running, we get 8635565795744155161506 partitions.

(d) Using pnDC(1000,1,{1},2) from HW #24, we can get all the integer partitions such that the components are odd and distinct.
Running, we get 517035762467311 partitions.

QUESTION #6:

(a) The number of rooted labelled trees with n vetices is n^(n-1).
So, the number of rooted labelled trees with 31 vertices is 31^30.

(b) We have the functional equation: R(x)=x*(R(x)^2/2!).
We have that PHI(z) = z^2/2!. Then, by the Lagrange Inversion Formula, we have that the number of rooted labelled trees with 31 vertices which is given by the coefficient of x^n, can be found by (1/31)*(coeff of z^n-1 in z^(2n)/2!).
Running, FunEqToSeq(1 + z^2/2, z, 31)[31]*31!, gives us 2432835272591051151727678975200000000 rooted labelled trees.

(c) We have the functional equation: R(x)=x*(1+R(x)+R(x)^3/3!+R(x)^4/4!)
Then, PHI(z) = 1+z+z^3/3!+z^4/4!.
Running, 31!*FunEqToSeq(1+z+z^3/3!+z^4/4!,z,31)[31] gives us 388391178300656853181332829972846230000000 such rooted labelled trees.

(d) We have the functional equation: R(x)=x*(1+R(x)^2/2!+R(x)^5/5!+R(x)^6/6!+R(x)^7/7!+...) = x*(e^R(x)-R(x)-R(x)^3/3!-R(x)^4/4!).
Then, PHI(z) = e^z-z-z^3/3!-z^4/4!.
Running 31!*FunEqToSeq(e^z-z-z^3/3!-z^4/4!,z,31)[31] gives us 2863465748628395267057869436794752181 such rooted labelled trees.

QUESTION #7:

(a) We have the following trees with four leaves:

	*                         *                   *                    *                 *
      /   \                     /   \               /   \                /   \             /   \
     *     *                   *     *             *     *              *     *           *     *
    / \   / \                 / \                       / \            / \                     / \
   *   * *   *               *   *                     *   *          *  *                    *   *
                            / \                           / \           / \                  / \
                           *   *                         *   *         *   *                *   *

So, BT(4)={ [[[],[]], [[],[]]], [[[[],[]], []], []], [[], [[],[[],[]]]], [[[], [[],[]]], []], [[], [[[], []], []]] }.
|BT(4)|=5

(b) The sequence b(n)=[1,1,2,5,14,...] seems to be given by the Catalan numbers, binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).

We want to prove that B(x), given by Sum(b(n)*x^n,n=0..infinity), is equal to x+B(x)^2.

Let B be the infinite set of complete binary trees. We have that B = Single Root (Union) BxB.
If we apply the weight enumerator, we can use similar reasoning to that when we found the generating function for walks with atomic steps.

Weight(B) = Weight(Single Root) + Weight(B x B) = Weight(Single Root) + Weight(B)*Weight(B) = x + Weight(B)^2.
Let Weight(B)=B(x), then our generating function is B(x) = x + B(x)^2 as desired.