#OK to post homework
#Kent Mei, 11/15/20, Assignment 19

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

#Suppose we have two combinatorial families A and B with a(n) labeled objects of size n in A and b(n) labeled objects of size n in B.
#We can create a new combinatorial family C = A x B using distinct and disjoint labels and define the size of each pair in C to be the sum of the size of the component from A and the size of the component from B.
#To obtain c(n), we need to consider every possible size value for the component from A which could go from 0 to n. Let k = the current size of the component from A and so, the current size of the component from B would be n - k.
#For the component from A, we know that there are a(k) labeled objects of size k in A. Similarly, for the component from B, we know there are b(n-k) labeled objects of size n-k in A. Since we are looking at unique pairs of an object from A and an object from B, there are a(k)*b(n-k) ways of forming these pairs.
#Finally, since we have n labels to choose from and assign, we know that there are (n choose k) i.e. binomial(n,k) ways to pick k labels for the component from A. 
#Since we are considering k from 0 to n, we add up all the possible objects for each specific k leading us to the fact that c(n) = Sum(binomial(n,k)*a(k)*b(n-k), k = 0..n).
#In order to get the egf of the sequence c(n), we need to multiply by x^n / n! and do a summation from n = 0..infty. Doing this to both sides, we get:
#Sum(c(n)*x^n/n!, n=0..infty) = Sum(x^n/n! * Sum(binomial(n,k)*a(k)*b(n-k), k = 0..n), n =0..infty)
#Since we know binomial(n,k)/n! = k! * (n-k)! and x^n = x^k * x^(n-k), we can rewrite the rhs as:
#Sum(Sum(a(k)*x^k/k! * b(n-k)*x^(n-k)/(n-k)!, k = 0..n), n = 0..infty)
#Reparameterizing, we can rewrite that as a product of two summations. 
#Sum(a(k)*x^k/k!, k = 0..infty) * Sum(b(n-k)*x^(n-k)/(n-k)!, n-k = 0..infty)
#Which is exactly
#egf(A) * egf(B).
#So, we have ended up with egf(C) = egf(A)*egf(B) as desired.

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

#Finding the OGF
#assume(abs(x)<1);
#sum(n*(n-1)*(n-2)*x^n, n = 0..infinity)
#6*x^3/(x-1)^4

#Finding the EGF
#sum(n*(n-1)*(n-2)*x^n/n!, n = 0..infinity)
#x^3*exp(x)

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

#i)
#egf := exp(exp(x)-1) * exp(exp(x)-1);
#coeff(taylor(egf,x=0,101), x, 100) * 100!;
#86635961604145793709294621186421021577187015751602637085427283871117865337554218116225569701173834817160231371909161518471870
#is the number of ordered pairs that match the description.

#ii)
#Since we are working with sets instead of ordered pairs, the total amount must be halved. Suppose we have specific set partitions of different set S1 and S2 whose total numbers is 100 and the labels are {1,...,100}. In the previous case, [S1,S2] and [S2,S1] were distinct cases and so, counted separately. However, in this case, {S1, S2} = {S2, S1} so they are no longer counted as two cases and instead just as one case. This is true for any pair S1 and S2 so we must divide the total number of cases by 2.
#43317980802072896854647310593210510788593507875801318542713641935558932668777109058112784850586917408580115685954580759235935
#is the number of sets {SP1, SP2} that match the description.