#OK to post
#Sam Minkin, 11/22, Assignment 20

QUESTION #1:

(i) The egf for only odd sized sets is x + x^3/3! + x^5/5! + x^7/7! + ... = x^(2i+1)/(2i+1)!
Furthermore, to have exactly 7 components we raise our egf to the 7th power.
So, all together, we have:
egf: f = (add(x^(2i+1)/(2i+1)!,i=0..50))^7/7!

Then, for n=100, we run coeff(taylor(f,x=0,101),x,100)*100! to get:
0 ways
Since 7 * (odd number) = (odd number) => n != 100

But, for, n=99, we run coeff(taylor(f,x=0,101),x,99)*99! to get:
1432502705864105319486933155268249754956466128880860547534832946097588193870904 ways

(ii) We want to find the egf for the number of set partitions of {1,2,3,...,100} with an exactly odd number of components but the sizes of the components can be any positive integer.

The egf for set partitions with any positive size components is x + x^2/2! + x^3/3! + x^4/4! + ... = sum(x^n/n!,n=1..infinity) = e^x - 1

To get exactly k components, we take egf^k/k!. So for all odd components, our egf is derived from:
f:=add((e^x-1)^(2i+1)/(2i+1)!, i=0..50) 

Then, for n=100, we run coeff(taylor(f,x=0,101),x,100)*100! to get:
23792695638183628316167125166708722722054741318989995555688894753342022292474103758734144789060946967960716668504295 ways

(iii) In this case, the size of the components can be any positive integer except for 2 and 5, which means a(2)=0 and a(5)=0, in our egf.

So, our egf is now: x + x^3/3! + x^4/4! + x^6/6! + ... + x^k/k! + ... = e^x - 1 - x^2/2! - x^5/5!

For an odd number of components, our egf is given by:
f:=add((e^x - 1 - x^2/2! - x^5/5!)^(2k+1)/(2k+1)!, k=0..50)

Then, for n=100, we run coeff(taylor(f,x=0,101),x,100)*100! to get:
537911979212289319210315022167976910293816540852093547715022508541682212897278245024355264789522538287080267265 ways


QUESTION #2:

(i) The egf for only odd sized cycles is x + x^3/3 + x^5/5 + x^7/7 + ... = x^(2i+1)/(2i+1)
Furthermore, to have exactly 7 cycles we raise our egf to the 7th power.
So, all together, we have:
egf: f := (add(x^(2i+1)/(2i+1),i=0..50))^7/7!

Then, for n=100, we run coeff(taylor(f,x=0,101),x,100)*100! to get:
0 ways
Since 7 * (odd number) = (odd number) => n != 100

But, for, n=99, we run coeff(taylor(f,x=0,101),x,99)*99! to get:
4412789849432866855490535845982398015929819543361615079756958905362022451785104704451588021842032993386513846924642714475521657088079162245120000000000000 ways

(ii) We want to find the egf for the number of permutations of {1,2,3,...,100} with an exactly odd number of cycles but the sizes of the cycles can be any positive integer.

The egf for permutations with any positive size cycles is x + x^2/2 + x^3/3 + x^4/4 + ... = sum(x^n/n,n=1..infinity) = -log(1-x)

To get exactly k components, we take egf^k/k!. So for all odd components, our egf is derived from:
f:=add((-log(1-x))^(2i+1)/(2i+1)!, i=0..50) 

Then, for n=100, we run coeff(taylor(f,x=0,101),x,100)*100! to get:
46663107721972076340849619428133350245357984132190810734296481947608799996614957804470731988078259143126848960413611879125592605458432000000000000000000000000 ways

(iii) In this case, the size of the components can be any positive integer except for 2 and 5, which means a(2)=0 and a(5)=0, in our egf.

So, our egf is now: x + x^3/3 + x^4/4 + x^6/6 + ... + x^k/k + ... = -log(1-x) - x^2/2 - x^5/5

For an odd number of components, our egf is given by:
f:=add((-log(1-x) - x^2/2 - x^5/5)^(2k+1)/(2k+1)!, k=0..50)

Then, for n=100, we run coeff(taylor(f,x=0,101),x,100)*100! to get:
23172213523966770724123670280303621010635693971914974901987101498394969134506826670931406322436188692149594499306436597877538608022152025529531964918909222550 ways


QUESTION #3:

(i) The egf of all labeled connected graphs is f:=log(add(2^(n*(n-1))/2 * x^n/n!, n=0..100)), where n is the number of vertices in the labeled connected graph

Then, for n=100 vertices, we can find the number of connected graphs by running coeff(taylor(f,x=0,101),x,100)*100! which gives:
1.254522736*10^1490 graphs

(ii) To find the number of labeled connected graphs with exactly two components, we can find the number of labeled connected graphs with i and 100-i vertices and then multiply for all i=1..50.

Using the f from (i), this is given by add((coeff(taylor(f,x=0,101),x,i)*i!)*(coeff(taylor(f,x=0,101),x,100-i)*(100-i)!, i=1..50)

Running the above gives:
1.979287883*10^1462 graphs

(iii) To find the number of labeled connected graphs with exactly 100 components, we can run coeff(taylor(f,x=0,101),x,1)^100, which gives:
1 way (every vertex is a component)