#Ok to post homework
#Tifany Tong, November 15th, 2020, HW #19

# Question 1

# If we have two combinatorial families, where there is no overlap between the two 
# families. As a result, the total number of pairs between the two families is:

# c(n) = The summation from k=0 to n [(n Choose k) a(k) * b(n-k)] where we 
# choose k objects to be from the first combinatorial family. a(k) is the number of
# ways to get k objects from the first combinatorial family and then b(n-k) is the 
# number of ways to get n-k objects from the second combinatorial family. 

# Now, we sum from n = 0 to n = infinity and multiply both sides by x^n/n! to convert it
# c(n) to its exponential generating function (egf). 

# This gives us on one side: 
# the summation from n=0 to infinity( c(n)/n! * x^n ). Now, let's split it up further:

# the summation from n = 0 to infinity(the summation from k = 0 to n( a(k)/k! * x^k *
# b(n-k)/(n-k)! * x^(n-k)). 

# From here we can split it to 

# (the summation from k =0 to infinity (a(k)/k!) * x^k) * (the summation from n-k = 0 to infinity
# (b(n-k)/(n-k)! * x^(n-k)). 

# Thus, we see that there is egf(A) and egf(B), giving us egf(c) = egf(A) * egf(B).

# --------------------------------------------------

# Question 2

# a(n) = n *(n-1) *(n-2) 
# a(0) = 0
# a(1) = 0
# a(2) = 0 
# a(3) = 6
# a(4) = 24
# a(5) = 5*4*3 = 60
# a(6) = 6*5*4 = 120
# a(7) = 7*6*5 = 210
# a(8) = 8*7*6 = 336
# a(9) = 9*8*7 = 504
# a(10) = 10*9*8 = 720
# a(11) = 11*10*9 = 990
# a(12) = 12*11*10 = 1320

# EXPONENTIAL GENERATING FUNCTION:

# sum(n*(n - 1)*(n - 2)*x^n/n!, n = 3 .. infinity) = x^3*e^x

# ORDINARY GENERATING FUNCTION:

# with(gfun);
# guessgf([0, 0, 0, 6, 24, 60, 120, 210, 336, 504, 720, 990, 1320], x, ['ogf']) = 
#                   [6*x^3/(x^4 - 4*x^3 + 6*x^2 - 4*x + 1), ogf]

# -------------------------------------------------------------

# Question 3

# i. coeff(taylor(exp(exp(x) - 1)*exp(exp(x) - 1), x = 0, 101), x, 100)*100! =
# 8663596160414579370929462118642102157718701575160263708542728387
# 1117865337554218116225569701173834817160231371909161518471870

# ii. Since the order doesn't matter in a set as compared to an ordered pair,
# we can just divide the previous value we got, giving us

# coeff(taylor(exp(exp(x) - 1)*exp(exp(x) - 1), x = 0, 101), x, 100)*100!/2! = 
# 43317980802072896854647310593210510788593507875801318542713641935558932668777109058112784850586917408580115685954580759235935