Ok to post

1)

a) To do this problem we use the fact that one wants to get to [x, y, z] in a manhattan lattice, the number of ways to do it is Walks[x-1, y, z] + Walks[x, y-1, z] + Walks[x, y, z-1]. We can then program using maple the following function that will help us get this. 

#NuW(Pt,A): Input a Lattice Pt pt of the form [m,n,k],  and a set A of "atomic steps" (pairs with non-negative integers)
#(except that  [0,0,0] is not allowed) outputs the number of walks from [0,0,0] to Pt using these atomic steps.
#Try:
#NuW([6,4,3],{[0,0,1],[0,1,0],[1,0,0]});
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 the same way we do the 1st problem, but here we don't allow it to ever come below a certain threshold. Look at the following code to understand. 
#NuGW(Pt,A): Input a Lattice Pt pt of the form [m,n,k],  and a set A of "atomic steps" (pairs with non-negative integers)
#(except that  [0,0,0] is not allowed) outputs the number of GOOD walks (staying in x>=y>=z) from [0,0,0] to Pt using these atomic steps.
#Try:
#NuGW([6,4,3],{[0,0,1],[0,1,0],[1,0,0]});
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) Same logic as part 1 but this time instead of Walks being equals to Walks[x-1, y, z] + Walks[x, y-1, z] + Walks[x, y, z-1] 

Walks equal:

for i in {[1,0, 0], [0, 1, 0], [0, 0, 1], [1, 1, 1], [2, 2, 2]}:
	sum(walks([x, y, z] - i ))

NuW([30, 25, 20], {[1,0, 0], [0, 1, 0], [0, 0, 1], [1, 1, 1], [2, 2, 2]})
              31831650298097356165593942880232160
              
d)We just edit the condition and it gives us the desired result .

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:
3818966446210163616599115660989544

e) Ofcourse it is the famous catalan numbers in k dimensions given by C(n, k) = (k*n)! * mul(i!/(n+i)!, i=0..k-1):

I wrote code for this and was able to conjecture this formula. OEIS helped. 

Code below:
NuWalks:=proc(Pt,n, k) local A, a, i:
option remember:
with(combinat):

A:=permute([1, 0$(k-1)]):
for i from 2 to nops(Pt) do:
if Pt[i-1]<Pt[i] or Pt[i-1] < 0 or Pt[i]<0 then
RETURN(0):
fi:
od:
if Pt=[0$k] then
RETURN(1):
else
add(NuWalks(Pt-a, n, k), a in A):
fi:
end proc:

2)

a) 4^30 - 
                      1152921504606846976
Since there are 4 options for each number and there are 30 numbers, there are 4^30 words in this alphabet

b) We use the concept of weight enumerators
1 - has a weight of x
2 - has a weight of x^2
So on and so forth

The set A can be decomposed into

A = {} U 1A U 2A U 3A U 4A
|A| = 1 + x|A| + x^2|A| +x^3|A|+x^4|A|
|A| = f
f:=1/(1-x^2-x^3-x^4-x)
                                  1          
                   f := ---------------------
                          4    3    2        
                        -x  - x  - x  - x + 1
f1:=taylor(f, x=0, 301):
coeff(f1, x ,300)
18012939919656512113252584133785878056327163962817704791464695718041992634738504938769

c)We find the generating function using decomposition
x+x^2+x^3+...+x^n where n = infinity equals -x/(x - 1)

Hence the generating function is 1/(1-(-x/(x - 1)))

When we expand it we see the sequence
1, 2, 4, 8, 16, ...
and can conjecture a formula - 2^n

d) We use maple to help us out here. We can use the sum function to find this out
1/(1-sum(x^(3*i+1), i=0..infinity))
                               1     
                           ----------
                                 x   
                           1 + ------
                                3    
                               x  - 1
normal(%)
                              3      
                             x  - 1  
                           ----------
                            3        
                           x  + x - 1

These simple maple commands give us this generating function

(x^3 - 1)/(x^3 + x - 1)

e) I do it empirically coeff(taylor(f, x=0, 3500), x, 3499):
coeff(taylor(f, x=0, 3501), x, 3500):
%%/%:
evalf(%)
                          0.6823278038
It is 0.68 for a lot of the values

I go even higher
coeff(taylor(f, x=0, 6001), x, 6000):
coeff(taylor(f, x=0, 6002), x, 6001):
%%/%:
evalf(%)
                          0.6823278038

3)

a) One of my favorite theorems : 
If B is a labeled combinatorial family that can
be viewed as sets of ‘connected components’ that
belong to a combinatorial family A then
egf(B) = exp[ egf(A) ] 
Let a(n) be the number of non-empty sets of the form
{1, 2, . . . , n}. Clearly when n = 0 there is no such
(non-empty) set, while for each n ≥ 1, there is
exactly one such set, so the egf is

0 + sum(x^i/i!, i=1..infinity) = exp(x)-1
Hence the egf for bell numbers is 
exp(exp(x)-1)

3263983870004111524856951830191582524419255819477

b) 
f:=exp(x)-1;
We empirically calculate this by adding up to a certain number and then using the taylor expansion
coeff(taylor(add(f^(3*i+1)/(3*i+1)!,i=0..50),x=0,52),x,51)*51!;
                        f := exp(x) - 1
       1089030250824782148720306369738651363734233026160


c) We basically count the atoms now that is x^1/1!+x^3/3!+x^5/5!... = sinh(x)

exp(sinh(x))

101595492022700597152023270326642584710021120

d) f:=sinh(x);
coeff(taylor(add(f^(3*i+1)/(3*i+1)!,i=0..50),x=0,52),x,51)*51!;
                          f := sinh(x)
          30143119660583350838086153637731292910753195


4)

a) 
{{{1, 2, 3}}}
{{{1}},{{2, 3}}}
{{{2}},{{1, 3}}}
{{{3}}, {{1, 2}}}
{{{1}}, {{2}}, {{3}}}

b)exp(exp(x)-1) 
This is a bijection to the number of partitions of a set aka bell numbers
Yes it is in the OEIS
A000110		Bell or exponential numbers: number of ways to partition a set of n labeled elements.






5)

a) I use the Euler recurrence to find this
pnFast(n): Same as pn(n) but using Euler's recurrence  Sum((-1)^j*p(n-(3*j-1)*j/2)+(-1)^j*p(n-(3*j+1)*j/2),j=0..infinity)=0 if n>0
pnFast:=proc(n) local j,su:
option remember:
if n<0 then
RETURN(0):
elif n=0 then
RETURN(1):
else
su:=0:
for j from 1 while j*(3*j+1)/2<=n do
 su:=su-(-1)^j*pnFast(n- j*(3*j+1)/2):
od:


for j from 1 while j*(3*j-1)/2<=n do
 su:=su-(-1)^j*pnFast(n- j*(3*j-1)/2):
od:

RETURN(su):
fi:
end:
24061467864032622473692149727991

b) We can use the generating function by the great Euler
# pnOddSeq(N): Same output as [seq(pnC(i,{1},2),i=1..N)] but using Euler's generating function 1/((1-q)*(1-q^3)*(1-q^5)*...)
pnOddSeq:=proc(N) local f,q,i:
f:=mul(1/(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:

8635565795744155161506

c) It is a theorem that the above value is the same, but we still verify it using # pnDistinctSeq(N): Same output as [seq(pnC(i,{1},2),i=1..N)] but using Euler's generating function (1+q)*(1+q^2)*(1+q^3)...)
pnDistinctSeq:=proc(N) local f,q,i:
f:=mul(1+q^i,i=1..N):
f:=taylor(f,q=0,N+1):
[seq(coeff(f,q,i),i=1..N)]:
end:

8635565795744155161506

d) This was a HW problem and we wrote a maple procedure for this
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)
n = 1000
d= 1 // for distinct values
C = for odd values
                        517035762467311
It takes a while but eventually comes up
517035762467311

6) 

a) We use the simple formula n ^ (n-1) to count the number of rooted labelled trees with 31 vertices

31 ^ 30
550618520345910837374536871905139185678862401

b)

c) Each vertex has to have 1, 3, 4, or 0 number of children
hence we have 
phi:= 1+z^1/1!+z^3/3!+z^4/4!

#FunEqToSeq(PHI,z,N):
#Given a function PHI of z, and a positive integer N, outputs the first N terms, starting at n=1
#of the solutions of the functional equations
#f(x)=x*PHI(f(x)). Try:
#FunEqToSeq(exp(z),z,10);
FunEqToSeq:=proc(PHI,z,N) local f,i,j,x:

#we start with f=x, and keep applying the mapping f->x*PHI(f(x)), N times, and every time only
#save the terms up to and including x^N

f:=x:

for i from 1 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:
We then use the code we had in lecture
 
388391178300656853181332829972846230000000

d)Each vertex should not have 1, 3, 4number of children
hence we have 
phi:= 1-(z^1/1!+z^3/3!+z^4/4!)
We use the code like before and 
10304168216346930093787051875572130000000 number of trees

7) A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
By that definition BT(3) does not equal 2

a) BT(4) - {[[[], []], [[], []]]} - by definiton

BT(4) - by loose definiton{[[[], []], [[], []]], [[[[],[]],[]],[]], [[[],[[],[]]],[]], [[],[[[],[]],[]]], [[],[[],[[],[]]]]}
BT(4) = 5

b) We first start out by defining what a binary tree is. 
B = {} + {[[][]]} 
A binary tree as defined is either a leaf or an internal node followed by two binary trees. Using weight enumerators we get B = 1 +z*B^2(z)

We can solve for B(z) = (1- (1-4z)^(1/2))/2
This is the generating function, we now try to get the coefficients
By using maple and taking the taylor expansion of this we see that it is indeed the catalan numbers. The general catalan generating function is a little different though. 
It goes like E(z) = (1-sqrt(1-4z))/2
E(z) = z/(1-E(z)) - general trees is a node followed by a possible empty sequence of general trees
If we use the Lagrange inversion formula we get the catalan number. 

This establishes a bijection between general trees and binary trees. Hence proved