#OK to post homework
#Kent Mei, 11/22/20, Assignment 20

#---------------------------------
#Part 1

#i) There are no set partitions of a 100 element set such that there are 
#exactly 7 components and each component has odd size. Each component is a 
#nonempty set and if each nonempty set has an odd number of elements, the sum 
#of 7 odd numbers is odd and cannot equal 100. Therefore, no such set partition 
#exists.

#ii) Every nonempty set has a size that is a strictly positive integer.
#So, we are looking for the number of set partitions of a 100-element set such that there are an odd number of components.
#assume(abs(x) < 1):
#sum(x^(2*i-1) / (2*i-1)!, i = 1..infinity);
#sinh(x):
#egf := sinh(exp(x)-1);
#coeff(taylor(egf,x=0,101),x,100) * 100!;

#23792695638183628316167125166708722722054741318989995555688894753342022292474103758734144789060946967960716668504295
#set partitions of 100 elements contain an odd number of components.

#iii) 
#egf := sinh(exp(x) - 1 - x^2/2! - x^5/5!);
#coeff(taylor(egf,x=0,101),x,100) * 100!;

#537911979212289319210315022167976910293816540852093547715022508541682212897278245024355264789522538287080267265
#set partitions match the given description.



#---------------------------------
#Part 2

#i) There are no permutations of {1,2,...,100} such that there are exactly 7 
#cycles and each cycle has odd size. For a cycle to have odd size, it would have 
#to correspond to an odd number of labels. However, the sum of 7 odd numbers is 
#odd and cannot equal 100.

#ii) 
#assume(abs(x) < 1):
#sum(x^(2*i-1) / (2*i-1)!, i = 1..infinity);
#sinh(x):
#egf := sinh(-log(1-x));
#coeff(taylor(egf, x = 0, 101), x, 100) * 100!;

#46663107721972076340849619428133350245357984132190810734296481947608799996614957804470731988078259143126848960413611879125592605458432000000000000000000000000
#permutations contain an odd number of cycles where the length of the cycles is any strictly postive integer.

#iii)
#egf := sinh(-log(1-x) - x^2/2 - x^5/5);
#coeff(taylor(egf, x = 0, 101), x, 100) * 100!;

#23172213523966770724123670280303621010635693971914974901987101498394969134506826670931406322436188692149594499306436597877538608022152025529531964918909222550
#permutations match the description.


#---------------------------------
#Part 3

#For the number of connected graphs with n vertices, the egf is 
#egf := log(1+ sum(2^binomial(n,2)*x^n/n!,n=1..infinity)):

#coeff(taylor(egf, x=0, 101), x, 100) * 100!
#125452273648412141401139200773089339811437122262323352216462286700734387627331522885709312904647210371328794107858418293356140610389233010890575674923332327423429917033308833625087865757067009121643735335562957720919464360279849562024268481514680519466433342816295305461792608710076067024418040646132922593872156786882042514851134725907407734998659047116141535192232282791034794601497425933135733739224548153792567839779141913680549722028773475603674523853169051845195421079685934332310882053907313995168923535704556709136009686053259752740308577712484995569783650846269720521608249582420017860918845622644663874987575160515268766971368721963159046529551370104575096202684311358624098672672476994761800126366704378281769378475834662925454186722285874859694872242026068795039642380038691501013387521486053366727435218916045301026547623117868196574350026663672938544838421549439678291079144887169351257353939537143880911795509769485297854345823362270660712007071953958048732807833151699233932553517365602355625760928908188344900652899469143373311896574182769657272933821876553379518700197938172155010185719146936187180903250543579433005278984692348282568379624191843385007057047580846112172322370992146748764340302424100769640802926078370838482052406435490036434092467614465282934547622486501083341846045800849550829377015688082924233744178977266360888077466658752803757886543953371541948150838050857811138739570190403175194723845806878286855221273591078542964296886759202533689916185534005248
#connected graphs with 100 vertices.

#coeff(taylor(egf^2/2!, x=0, 101), x, 100) * 100!
#19792878830464097434146485069739463865673187370672887935834214122103592997909477467639145015413302778571558698199938989875722363632867076525500775193313203219625694859620492756307560817786124480904571667305985231399040766859432538780170724152051889531424530851027515639435541861971440089962657458762079240342770560135993633520904674629099681471079341302098763093130534058092714306341148454323169655736417188716167485638876856164406937663195315675056473320830072088996900023615988558834190601024551606490996047256677952803727152702099973371018028710701366236803289614033811563475696670364580819031243080945830466884602280114938472440443402744527681562033913068944126647000531086090506590597863434313244427618995892382119045374120085198882365703112462192132262796290715887651629501613500765319382697459714625232601391113377456170319146465206446792331217136689657731214890373782128820154293953635221308380687242012269185806693761170244502543846560216890121849276503785641853915478872687428718708183133628359872764435735322526121955322100244200579269171473679314961687680638065276652910066401714258899512328773662068014373263170965092624777284239415572512416129024249860116530210873861235283964287841875225918264476127609182676153172047392096718128978027994944226801334642136592881198292406724597930004937454732160477796576767954616879358825917759244042876084345101045377871469937328841023216205534951719728974096997883111102605252071058831339598818474925540591534080
#graphs with 100 vertices in exactly 2 connected components.

#coeff(taylor(egf^100/100!, x=0,101),x,100)*100!
#1 graph with 100 vertices in exactly 100 connected components.