#OK to post hw
#Michael Yen 11/21/20, Assignment 20

#Lecture 20: Due Nov. 22, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment

#hw20FirstLast.txt

#Indicate whether it is OK to post

#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
#EGF of set partitions
#f=x+x^3/3!+x^5/5!+...
f:=add(x^(2*i+1)/(2*i+1)!,i=0..50)^7/7!;
coeff(taylor(f,x=0,101),x,100)*100!;
#0

#Makes sense because an odd number of components all of odd size gives an odd set. 

#(ii) There are exactly an odd number of components, but the sizes of the components can be any strictly 
#positive integer

#f=x+x^2/2!+x^3/3!+...
f:=exp(x)-1;
coeff(taylor(add(f^(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 any strictly 
#positive integer except that we do not allow componets of size 2 and 5

f:=exp(x)-1-x^2/2-x^5/5;
coeff(taylor(add(f^(2*i+1)/(2*i+1)!,i=0..50),x=0,101),x,100)*100!;

#368583457883488118405596669875478491756636532544305730324214256979001815899833344889542242839334038473430186762330418464885297

###############################################

#2) How many permutations are there of {1,2,..., 100} such that
#(i) There are exactly 7 cycles, and each cycle has odd size
#EGF of all cycles: Sum(x^n/n,n=1..infinity)=-log(1-x)
#EGF of cycles with odd size: sum(x^(2*i+1)/(2*i+1),i=0..infinity)
f:=add(x^(2*i+1)/(2*i+1),i=0..50):
coeff(taylor(f^7/7!,x=0,101),x,100)*100!;
#0

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

#(iii) There are exactly an odd number of cycles, but the lengths of the cycles can be any strictly positive 
#integer except that we do not allow cycles of length 2 and 5
#f=x+x^3/3+x^4/4+x^6/6+x^7/7+x^8/8...
f:=-log(1 - x) - x^2/2 - x^5/5;
coeff(taylor(add(f^(2*i+1)/(2*i+1)!,i=0..50),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?

#EGF of all labelled graphs is
f:=log(add(2^(n*(n-1)/2)*x^n/n!,n=0..101)):

coeff(taylor(f,x=0,101),x,100)*100!;
#125452273648412141401139200773089339811437122262323352216462286700734387627331522885709312904647210371328794107858418293356140610389233010890575674923332327423429917033308833625087865757067009121643735335562957720919464360279849562024268481514680519466433342816295305461792608710076067024418040646132922593872156786882042514851134725907407734998659047116141535192232282791034794601497425933135733739224548153792567839779141913680549722028773475603674523853169051845195421079685934332310882053907313995168923535704556709136009686053259752740308577712484995569783650846269720521608249582420017860918845622644663874987575160515268766971368721963159046529551370104575096202684311358624098672672476994761800126366704378281769378475834662925454186722285874859694872242026068795039642380038691501013387521486053366727435218916045301026547623117868196574350026663672938544838421549439678291079144887169351257353939537143880911795509769485297854345823362270660712007071953958048732807833151699233932553517365602355625760928908188344900652899469143373311896574182769657272933821876553379518700197938172155010185719146936187180903250543579433005278984692348282568379624191843385007057047580846112172322370992146748764340302424100769640802926078370838482052406435490036434092467614465282934547622486501083341846045800849550829377015688082924233744178977266360888077466658752803757886543953371541948150838050857811138739570190403175194723845806878286855221273591078542964296886759202533689916185534005248

coeff(taylor(f^2/2!,x=0,101),x,100)*100!;
#19792878830464097434146485069739463865673187370672887935834214122103592997909477467639145015413302778571558698199938989875722363632867076525500775193313203219625694859620492756307560817786124480904571667305985231399040766859432538780170724152051889531424530851027515639435541861971440089962657458762079240342770560135993633520904674629099681471079341302098763093130534058092714306341148454323169655736417188716167485638876856164406937663195315675056473320830072088996900023615988558834190601024551606490996047256677952803727152702099973371018028710701366236803289614033811563475696670364580819031243080945830466884602280114938472440443402744527681562033913068944126647000531086090506590597863434313244427618995892382119045374120085198882365703112462192132262796290715887651629501613500765319382697459714625232601391113377456170319146465206446792331217136689657731214890373782128820154293953635221308380687242012269185806693761170244502543846560216890121849276503785641853915478872687428718708183133628359872764435735322526121955322100244200579269171473679314961687680638065276652910066401714258899512328773662068014373263170965092624777284239415572512416129024249860116530210873861235283964287841875225918264476127609182676153172047392096718128978027994944226801334642136592881198292406724597930004937454732160477796576767954616879358825917759244042876084345101045377871469937328841023216205534951719728974096997883111102605252071058831339598818474925540591534080

#1