#Ok to post
#Michael Yen, Assignment 19, 11/15/20
#Lecture 19: Due Nov. 15, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment

#hw19FirstLast.txt

#Indicate whether it is OK to post

#1) Carefully read the section about exponential generating functions in Dr. Z.'s essay. Reproduce 
#the proof that egf(AxB)=egf(A)*egf(B) in your own words, and understand it . [It may come up in the 
#oral part of the Final Exam!]

#Let there be two combinatorial families A and B.
#There are a(n) objects of size n in the A family, and b(n) objects of size n in the B family.
#Example: (A = labeled trees, B = permutations)
#Let's take C to be C = AxB where labels are disjoint and distinct and define the size of each pair 
#to be the sum of the sizes of the components.
#Then c(n) = sum_(k=0)^n((n choose k)(a(k)b(n-k))).
#You have a quota of n objects and choose an amount from 0 to n to use for the size of the first 
#component, making the size of the second component n-k (k=0 to n). Next, you choose k labels to go 
#to the first and n-k labels to go to the second ((n choose k)(a(k)b(n-k))).
#Multiply both sides by x^n/n! to obtain:
#sum_(n=0)^(infinity)(c(n)/n!*x^n)
#=sum_(n=0)^(infinity)(sum_(k=0)^n(a(k)/k!*x^k*b(n-k)/(n-k)!*x^(n-k)))
#=sum_(k=0)^(infinity)(a(k)/k!*x^k)*sum_(n-k=0)^infinity(b(n-k)/(n-k)!x^(n-k)))
#->egf(C)=egf(A)*egf(B)

#(All Credits to Dr. Z's Essay)

#2) Using Maple or otherwise find the ordinary generating function and exponential generating #function for
#a(n)=n*(n-1)*(n-2) (n ≥ 0)

#ordinary generating function is 
#0+0+0+3*2*1*x^3+4*3*2*x^4+5*4*3*x^5+...
#=6*x^3/(x - 1)^4

#egf is 
#a(0)*x/0!+a(1)*x/1!+a(2)*x^2/2!+a(3)*x^3/3!+...
#=0+0+0+3*2*1*x^3/3!+4*3*2*x^4/4!+5*4*3*x^5/5!+...
#=x^3*exp(x)

#3) 
#(i) How many ordered pairs [SP1,SP2] are there where SP1 and SP2 are set partitions of different 
#sets whose total numbers is 100 and the labels are {1, ..., 100}

#egf(X)=exp(exp(x)-1)*exp(exp(x)-1)
coeff(taylor(exp(exp(x) - 1)*exp(exp(x) - 1), x = 0, 101), x, 100)*100!#86635961604145793709294621186421021577187015751602637085427283871117865337554218116225569701173834817160231371909161518471870

#(ii) How many sets {SP1,SP2} where SP1 and SP2 are set-partitions of different sets whose total 
#numbers is 100 and the labels are {1, ..., 100} ?

#I think this is the same as part (i), no matter if C is constructed as a set or ordered pair.
#egf(X)=exp(exp(x)-1)*exp(exp(x)-1)
#86635961604145793709294621186421021577187015751602637085427283871117865337554218116225569701173834817160231371909161518471870

#[Reminder the egf of set-partitions is exp(exp(x)-1) ]