#OK to post homework
#William Wang, 11/16/2020, Assignment 20

#1. How many set partitions are there of a 100-element set such that
#i. There are exactly 7 components, and each component has odd size
coeff(taylor(add(x^(2*i + 1)/(2*i + 1)!, i = 0 .. 50)^7/7!, x = 0, 101), x, 100)*100!;
  0
#x+x^3/3!+x^5/5! = sinh(x) so this can also be done as
coeff(taylor(sinh(x)^7/7!, x = 0, 101), x, 100)*100!;
  0
#This makes sense since there is no way to divide a 100-element set into 7 components with each part having an odd size

#ii. There are exactly an odd number of components, but the sizes of the components can be strictly any positive integer
coeff(taylor(add((exp(x) - 1)^(2*i + 1)/(2*i + 1)!, i = 0 .. 50), x = 0, 101), x, 100)*100!;
  23792695638183628316167125166708722722054741318989995555688894753342022292474103758734144789060946967960716668504295

#iii. There are exactly an odd number of components, but the sizes of the components can be strictly any positive integer except that we do not allow components of size 2 and 5
coeff(taylor(add((exp(x) - 1 - x^2/2! - x^5/5!)^(2*i + 1)/(2*i + 1)!, i = 0 .. 50), x = 0, 101), x, 100)*100!;
  537911979212289319210315022167976910293816540852093547715022508541682212897278245024355264789522538287080267265



#2. How many permutations are there of {1,2,...,100} such that
#i. There are exactly 7 cycles, and each cycle has odd size
coeff(taylor(add(x^(2*i + 1)/(2*i + 1), i = 0 .. 50)^7/7!, x = 0, 101), x, 100)*100!;
  0
#This makes sense since there is no way to divide a permutation of length 100 into 7 cycles with each cycle having an odd size

#ii. There are exactly an odd number of cycles, but the length of the cycles can be strictly any positive integer
coeff(taylor(add((-log(1 - x))^(2*i + 1)/(2*i + 1)!, i = 0 .. 50), x = 0, 101), x, 100)*100!;
  46663107721972076340849619428133350245357984132190810734296481947608799996614957804470731988078259143126848960413611879125592605458432000000000000000000000000
#Can also be done as
coeff(taylor(cosh(add(x^i/i, i = 1 .. 100)), x = 0, 101), x, 100)*100!;
  46663107721972076340849619428133350245357984132190810734296481947608799996614957804470731988078259143126848960413611879125592605458432000000000000000000000000

#iii. There are exactly an odd number of cycles, but the length of the cycles can be strictly any positive integer except 2 and 5
coeff(taylor(add((-log(1 - x) - x^2/2 - x^5/5)^(2*i + 1)/(2*i + 1)!, i = 0 .. 50), x = 0, 101), x, 100)*100!;
  23172213523966770724123670280303621010635693971914974901987101498394969134506826670931406322436188692149594499306436597877538608022152025529531964918909222550
#Can also be done as
coeff(taylor(sinh(add(x^i/i, i = 1 .. 100) - x^2/2 - x^5/5), x = 0, 101), x, 100)*100!;
  23172213523966770724123670280303621010635693971914974901987101498394969134506826670931406322436188692149594499306436597877538608022152025529531964918909222550



#3. How many labeled connected graphs are there with 100 vertices? How many are there with exactly 2 components? With exactly 100 components?
#With 2 components
coeff(taylor(log(add(2^(n*(n - 1)/2)*x^n/n!, n = 0 .. 101))^2/2, x = 0, 101), x, 100)*100!;
  1979287883046409743414648506973946386567318737067288793583421412210359299790947746763914501541330277[...1263 digits...]5377871469937328841023216205534951719728974096997883111102605252071058831339598818474925540591534080
#With 100 components
coeff(taylor(log(add(2^(n*(n - 1)/2)*x^n/n!, n = 0 .. 101))^100/100!, x = 0, 101), x, 100)*100!;
  1
#This answer makes sense, since if there are 100 components and 100 vertices, there is only 1 way for this to happen; that is, if every vertex is separate from every other vertex.