#OK to post
#Sam Minkin, 11/15, Assignment 19

QUESTION #1:

We start with sets A and B with the property that there are a(n) things of size n in A and b(n) things of size n in B. Let C=AxB={(a,b) : a \in A, b \in B}. To find the things in C of size n, we can take a thing in A of size a(k) and a thing in B of size b(n-k). Then, the total number of things of size n in C, called c(n), where the labels are disjoint and distinct, is c(n)=Sum(binomial(n,k)*a(k)*b(n-k),k=0..n).

The egf of C is defined to be Sum(c(n)/n! * x^n, n=0..infinity). By our definition of c(n), we substitue to get Sum( (Sum(binomial(n,k)*a(k)*b(n-k),k=0..n))/n! * x^n, n=0..infinity) = Sum( (Sum(a(k)*b(n-k)/k!*(n-k)! * x^n, k=0..n), n=0..infinity). Now we can split the inside of the sum in a clever way to get Sum( (Sum((a(k)/k! * x^k)*b(n-k)/(n-k)!x^{n-k}), which is equivalent to the product (Sum(a(k)/k!*x^k,k=0..infinity)(Sum(b(n-k)/(n-k)!*x^{n-k}, n-k=0..infinity))

Notice that this is the product of the egfs of A and B, which proves that egf(C)=egf(A)*egf(B)

QUESTION #2:

The ogf is Sum(a(n)*x^n,n=0..infinity) = Sum(n*(n-1)*(n-2)*x^n,n=0..infinity).
Running sum(n*(n-1)*(n-2)*x^n,n=0..infinity) in Maple gives:
6*x^3/(x - 1)^4

The egf is Sum(a(n)/n! * x^n,n=0..infinity) = Sum(n*(n-1)*(n-2)/n! * x^n, n=0..infinity).
Running sum(n*(n - 1)*(n - 2)*x^n/n!, n = 0 .. infinity) in Maple gives us:
x^3*exp(x)

QUESTION #3:

We can use of theorem that egf(AxB)=egf(A)*egf(B).
Let A be the set corresponding to SP1, the set partitions of varying length n, {1,..,n}.
Let B the set corresponding to SP2, the set partitions of varying length n, {1,..n}.

egf(A)=exp(exp(x)-1), egf(B)=exp(exp(x)-1)

(i) We know by the above theorem that we can get the desired number of ordered sets by using egf(AxB)=egf(A)*egf(B). To get the partitions whose total number is 100, we find a(100) from the taylor expansion of egf(A)*egf(B)= exp(2*exp(x)-2).

Running 100!*evalf(coeff(taylor(exp(2*exp(x) - 2), x = 0, 101), x, 100)) we get 
8.663596160*10^124 is the total number of ordered pairs.

(ii) In sets, order does not matter, so we divide the above value by 2! to get:
4.331798080*10^124 is the total number of such sets.