#OK to post

Soham Palande

# 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


#########################################################################################

1. 


(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]


    Using the explicit formula for the number of walks from [0,0,0] to [a,b,c] in the 3D 
    "Manhattan lattice":

    (a+b+c)!/(a!*b!*c!)


    (30 + 25 + 20)! / (30! * 25! * 20!)


    =  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


    Using dynamical Programming, 

    F:= proc(x,y,z) local a,b:
    option remember:

    #all the invalid conditions return 0
    if x<0 or y<0 or z<0 or x<y or y<z then
     0:

    #if we have reached x=0, then we know we can get to [0,0,0]
    elif x=0 then
     1:

    else 
     F(x-1,y,z)+F(x,y-1,z)+F(x,y,z-1):
    fi:

    end:


    F(30,25,20)

    = 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]


    Using the dynamical programming approach, 

    F:= proc(x,y,z) local a,b:
    option remember:

    #all the invalid conditions return 0
    #here we don't have to have x>=y>=z

    if x<0 or y<0 or z<0 then
     0:

    #if we have reached x=0, then we know we can get to [0,0,0]
    elif x=0 and y=0 then
     1:

    else 
     #the steps are [1,0,0], [0,1,0], [0,0,1], [1,1,1], [2,2,2]
  
     F(x-1,y,z)+F(x,y-1,z)+F(x,y,z-1)+F(x-1,y-1,z-1)+F(x-2,y-2,z-2):
    fi:

    end:

    F(30,25,20)

    = 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)



    Using the dynamical programming approach, 

    F:= proc(x,y,z) local a,b:
    option remember:

    #all the invalid conditions return 0
    #here we only check for x<y and x<z 

    if x<0 or y<0 or z<0 or x<y or x<z then
     0:

    #if we have reached x=0, then we know we can get to [0,0,0]
    elif x=0 then
     1:

    else 
     #the steps are [1,0,0], [0,1,0], [0,0,1], [1,1,1], [2,2,2]
  
     F(x-1,y,z)+F(x,y-1,z)+F(x,y,z-1)+F(x-1,y-1,z-1)+F(x-2,y-2,z-2):
    fi:

    end:


    F(30,25,20)

    = 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.


    Extending NuGW from ComboProject 3,

    GoodWalks:=proc(Pt,A) local a:
    option remember:

    for j from 1 to nops(Pt)-2 do

     if (Pt[j]<Pt[j+1] or Pt[j]<0 or Pt[j+1]<0 then
      RETURN(0):
     elif Pt=[0,0,0] then
      RETURN(1):
    
     else
      add(GoodWalks(Pt-a,A),a in A):
     fi:
    
    end:

    This can be given by the Catalan numbers.

    C(n, k) = (k*n)! * Product(i!/(n+i)!, i=0..k-1):


#########################################################################################


2.


(a)  How many words in the alphabet {0,1,2,3} are there of length 30?


     For each position in the word of length 30, we have to make 4 independent choices so      
     the number of words in 
     the alphabet {0,1,2,3} are there of length 30 is:

     4^(30)

     = 1152921504606846976
________________________________________________________________________________________


(b) How many words in the alphabet {1,2,3,4} are there that add-up to 300?


    Using dynamical programming:


    F:= proc(n) local a,b:
    option remember:

    if n<0 then
     RETURN(0):
    fi:

    if n=0 then
     RETURN(1):
    fi:

    RETURN(F(n-1)+F(n-2)+F(n-3)+F(n-4)):

    end:

    F(300)

   =18012939919656512113252584133785878056327163962817704791464695718041992634738504938769

_________________________________________________________________________________________


(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.

    This is the number of compositions of n which is 2^(n-1)

    We will use the technique of weighted enumeration. 

    Sum(x/(1-x))^k,k=0..infinity)= 1/(1- x/(1-x))

    convert(normal(1/(1- x/(1-x))),parfrac)
   
    = 1/2-1/2/(-1+2*x) = 2^(n-1)
________________________________________________________________________________________
    

(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)

    Using Maple function sum, 

    assume(abs(x)<1)

    normal(1/(1-sum(x^(3*i+1),i=0..infinity)))
    
    f(x) = Sum(a(n)*x^n,n=0..infinity) = (x^3-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.

    We know that a(n) is the coefficient of x^n in the Taylor expansion of f(x) as defined 
    in d.

    Empirically, the ratio appears to be constant for a(n+1)/a(n)

    s:=[seq(coeff(taylor(f,x=0,5001),x,i),i=1..5000)]:
    evalf(s[5000]/s[4999])
    
    a(n+1)/a(n) -> 1.465571232

    Now, solving for the ratio using Maple,

    1/fsolve(denom(f))

    1.465571232


    

########################################################################################


3.  


(a) What is the egf enumerating set-partitions. How many are there of the set 
    {1,2,...,51}?


    Let the number of set partitions for an n-element set (Bell Numbers) be denoted by 
    b(n). Then the egf can be   
    written as:

    Sum(b(n)* (x^n)/(n!), n=0..infinity)

    Let a(n) be the number of non-empty sets of the form {1,2,...n}. Then, when n=0, there 
    is no such empty set 
    while for each n>=1, there is exactly 1 such set so the egf is:

    A(x) = 0 + Sum((x^n)/n!,n=1..infinity) = e^(x) - 1

    Using the Fundamental Theorem of Exponential Generating Functions, we get that the egf  
    enumerating set 
    partitions is:

    B(x) = Sum(b(n)* (x^n)/n!, n=0..infinity) = e^(e^(x) - 1)

_________________________________________________________________________________________    


(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}

    
    Obviously, we cannot have an empty component i.e. having size 0.

    Let,

    f:=exp(x)-1:  # since the size of the component must be positive

    Since, the number of components of the set partition can be in {1,4,7,10,...},
    
    We have F:= Sum(f^((3*i)+1)/((3*i)+1)!,i=0..infinity)

    coeff(taylor(add(f^((3*i)+1)/((3*i)+1)!,i=0..20),x=0,55),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}?

        
    The components must have an odd size.

    f:=add(x^(2*i+1)/(2*i+1)!,i=0..52):
 
    Since, the number of components of the set partition can be any non-negative integer,

    We have F:= Sum(f^i/i!,i=0..infinity)

    coeff(taylor(add(f^i/i!,i=0..40),x=0,55),x,51)*51!; 

    = 101595492022700597152023265105229031385409994

________________________________________________________________________________________



(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}?


    The components must have an odd size.

    f:=add(x^(2*i+1)/(2*i+1)!,i=0..52):
 
    Since, the number of components of the set partition can be in {1,4,7,10,...},

    We have F:= Sum(f^((3*i)+1)/((3*i)+1)!,i=0..infinity)

    coeff(taylor(add(f^((3*i)+1)/((3*i)+1)!,i=0..20),x=0,55),x,51)*51!;  

    = 30143119660583350838086153637731292910753195




######################################################################################


4.

(a) Write all super-set partitions with n=3.


    {{1, 2, 3}}

    {{1, 2}, {3}}

    {{1, 3}, {2}}

    {{1}, {2, 3}}

    {{1}, {2}, {3}}

_____________________________________________________________________________________


(b) What is Sum(s[2](n)*x^n/n!, n=0..infinity)?  Is s[2](n) in the OEIS?
    

    Sum(s[2](n)*x^n/n!, n=0..infinity)

    These are the famous Bell Numbers.

    The e.g.f. is:

    = exp(exp(x)-1)

_____________________________________________________________________________________

(c) 
    




########################################################################################


5. 

(a) How many integer partitions are there of 1000?

    Using Euler's theorem, he number of integer partitions is

    = Sum(p(n) * (x^n),n=0..infinity)

    = 1/(1-x)(1-x^2)(1-x^3)...

    = Product(1/(1-x^i), i=1..infinity)

    Using Maple, 

    f:=mul(1/(1-q^i),i=1..1000):
    f:=taylor(f,q=0,1001):
    coeff(f,q,1000)


    = 24061467864032622473692149727991
_________________________________________________________________________________________


(b) How many integer partitions of 1000 are there where all the parts are odd?

    Using Euler's generating function 1/((1-q)*(1-q^3)*(1-q^5)*...)

    f:=mul(1/(1-q^(2*i+1)),i=0..trunc(1000/2)):
    
    f:=taylor(f,q=0,1001):
    
    coeff(f,q,1000)
    
    = 8635565795744155161506

_________________________________________________________________________________________


(c) How many integer partitions of 1000 are there where all the parts are different than 
    each other?

    Using Euler's generating function (1+q)*(1+q^2)*(1+q^3)...
    
    f:=mul(1+q^i,i=1..1000):
    
    f:=taylor(f,q=0,1001):
    
    coeff(f,q,1000)

    = 8635565795744155161506

    #This makes sense since, according to Euler's theorem, the number of integer 
    partitions of n into distinct  
    parts is equal to the number of integer partitions of n into odd parts.

_________________________________________________________________________________________


(d) How many integer partitions of 1000 are there where all the parts are different than 
    each other and all the 
    parts are odd.


    The number of self conjugate partitions of n, f(n) (symmetric Ferrer's diagrams), is 
    also the number of odd and 
    distinct partitions partitions of n. 

    The generating function can be obtained by combining the Euler's generating functions 
    for odd and distinct 
    partitions

    We use the generating function for distinct parts but use only odd powers, i in the 
    expression 
    Product(1+x^i,i=0..infinity)

    F:=mul((1+(x^((2*i)+1))),i=0..510):

    coeff(taylor(F,x=0,1005),x,1000)

    = 517035762467311





#########################################################################################    

6. 


(a) How many rooted labelled trees are there with 31 vertices?

    The number of rooted labelled trees on n vertices is exactly n times the number of 
    unrooted labelled trees on n
    vertices

    = n * n^(n-2) = n^(n-1)
   

    For 31 vertices, we have 31^(30) = 550618520345910837374536871905139185678862401
_________________________________________________________________________________________


(b) How many rooted labelled trees are there with 31 vertices where the root has exactly 
    two children

    The number of ways of choosing 3 vertices from 31 vertices is 31C3. For each of these 
    choices, 1 must be chosen as the root and the other two will be the children. So, we 
    multiply by 3C2 * 2! since the tree is labelled (the two chosen vertices can go on 
    either side). Now there are 28 remaining vertices which must be divided into two    trees. The sizes of the trees can be any of 1, 2, 3, 4...28. So the number of possible trees is Prod(j^(j-1),j=1..28)

    

_________________________________________________________________________________________    


(c) How many rooted labelled trees are there with 31 vertices where  each vertex must have 
    either zero, one, three,
    or four children.


    Each vertex must have either 0 or the number of children in S={1,3,4}

   
    f := 1 + z^1/1! + z^3/3! + z^4/4!:
   
    //setting the functional equation sequence using the function provided in lecture code
    L := FunEqToSeq(f, z, 31):

    L[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.

    
    f := z^1/1! + z^3/3! + z^4/4!:

    L := FunEqToSeq(exp(z) - f, z, 31):
 
    L[31]*31! 

    = 2863465748628395267057869436794752181





########################################################################################

7.


(a) Either by hand, or with Maple, find BT(4).


    BT(4)= { [[[],[]],[[],[]]] ,

             [[[[],[]],[]],[]] ,

             [[],[[[],[]],[]]] , 

             [[[],[[],[]]],[]] , 

             [[],[[],[[],[]]]] }
  
 
    b(4) = 5
_________________________________________________________________________________________


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

    Let b(n) be the number of unlabeled complete binary trees with n leaf nodes. 

    Since a tree is minimally connected, removing any node that is not a leaf node results 
    in the tree having several connected components. 

    Suppose you have a tree as defined above. Remove the root node.

    We have the following cases:

    Case 1: We have an empty tree (tree has only one node)
   
    ogf:= x^0 = 1

    We cannot have 1 connected component, since, according to our definition, we have a 
    tree with one leaf vertex as the root node itself, a tree with 2 leaf vertices as the 
    root node with two children... 

    Case 2: We get exactly 2 connected components

    ogf:= B(x)^2

    Since the tree is ordered, we divide the above expression by x.

    We cannot have more than 2 connected components in the tree since it is a complete 
    binary tree. 


    The root itself is also a rooted tree with 1 node ogf: x
    
    B(x) = x(1 + B(x)^2/x)
    
         = x + B(x)^2


    The explicit expression is B(x) = (1 - sqrt(1-4x))/2

    

########################################################################################