#OK to post #Sam Minkin, 12/06, Assignment 22 QUESTION #1: (i) First, we run L:=TreeSeqL(67,t) to get the sequence of generating functions of rooted labelled trees with n vertices. We extract the 67th entry, which is the generating function of rooted labelled trees with 67 vertices. The coefficient of t^12 gives us the number of rooted labelled trees with 67 vertices and 12 leaves: f := L[67]; coeff(f, t, 12); = 762668035595791008261768918050546247626868131307789154916300139847357281766830345010754357481701376000000000000000 (ii) To find the number of labelled connected graphs with 40 vertices and 43 edges we can extract the 40th ordinary generating function from the sequence produced by: WtEdConGclever(40,a) Then, to get the number of labelled connected graphs with 43 edges we extract the coefficient of a^43: f := L[40]; coeff(f, a, 43); 90324445150366623501655158316607196285055246080819484164096000000000 QUESTION #2: Given a set S, our functional equation is R(x) = x*(1+add(R(x)^s/s!, s in S). Hence, PHI(z) = 1+add(z^s/s!, s in S). SeqRTchild:=proc(S,N) local PHI,L,z,s: PHI:=1+add((z^s)/s!, s in S): L:=FunEqToSeq(PHI,z,N): [seq(L[n]*(n-1)!,n=1..N)]: end: (i) SeqRTchild({1, 2}, 30): [1, 1, 3, 15, 108, 1020, 11970, 168210, 2756880, 51665040, 1090227600, 25589163600, 661411396800, 18670554302400, 571571525725200, 18863069947722000, 667631023611552000, 25228028392703136000, 1013744174718379104000, 43166103631038067680000, 1941610814496268755840000, 91994340695254367610240000, 4579662725439359308470720000, 238987856272780761307761600000, 13045889113037241579933534720000, 743516064794463925083223104000000, 44162886977629516587092906304000000, 2729398012979599575601791515712000000, 175252402590093820507873322085120000000, 11674595292088861381930760838350592000000] It is not in the OEIS. (ii) SeqRTchild({1, 2, 3}, 30): [1, 1, 3, 16, 124, 1270, 16230, 249060, 4466000, 91692720, 2121915600, 54660236400, 1551493204800, 48117531462000, 1619012724529200, 58743694805796000, 2286478437987744000, 95036400158507808000, 4201370684804573280000, 196847405920341880704000, 9743882037769087528320000, 508118375685301752571200000, 27842980592628415035581760000, 1599468022370671947157023360000, 96122573592477121573042199040000, 6031490306103343735433043264000000, 394458727543327719136439999424000000, 26843876098869159735782813628192000000, 1898010050455191863315596840072704000000, 139236249208948823323423869909847776000000] It is not in the OEIS. (iii) SeqRTchild({1, 2, 3, 4}, 30): [1, 1, 3, 16, 125, 1295, 16770, 261065, 4752440, 99109080, 2330524350, 61019597100, 1760827645500, 55528488315300, 1900070233861800, 70119293171177250, 2776141202750916000, 117380806551844836000, 5279100169949145540000, 251643196017395149968000, 12673466183806242850035000, 672441672693015998557785000, 37492795325793948680529990000, 2191614181698214148762671785000, 134024059891297193784591264840000, 8557794074504171024378659809000000, 569545409984810376337002228946500000, 39443035906050351609187102977027000000, 2838113619569581894636022599991319000000, 211883338579071896164744824871388025000000] It is not in the OEIS. (iv) SeqRTchild({1, 3, 4}, 30): [1, 1, 2, 7, 41, 345, 3630, 44975, 644280, 10566360, 195967800, 4054823850, 92506652700, 2305862258700, 62355874581000, 1818633039473250, 56910745335444000, 1902108142034100000, 67625167492386504000, 2548352722498675092000, 101463145195334557635000, 4256162912380598614395000, 187617616044912437554170000, 8670862022881066598645055000, 419239491369694814527548840000, 21165582087625631250944349000000, 1113762412239786081453644964000000, 60986890380952950979469940535500000, 3469791789545706434576952268083000000, 204824976167114653140070166365479000000] It is not in the OEIS. (v) SeqRTchild({2, 3, 4}, 30): [1, 0, 1, 1, 13, 50, 600, 4655, 63000, 745920, 11897550, 187398750, 3524621100, 68622754200, 1503438736800, 34657643270250, 871487356740000, 23140472427072000, 658550577448764000, 19761505708420476000, 628702914005241075000, 21022602523577805150000, 739864371631168503720000, 27268721805480551310915000, 1052192707216535546461800000, 42370753999799239854840000000, 1778968029843678679417912500000, 77703995811639490743682732500000, 3526963269710878560374086275000000, 166080334510467740262504715110000000] It is not in the OEIS. QUESTION #3: In this case our functional equation is x*(e^R(x) - add(R(x)^s/s!, s in S)). Hence, PHI(z) = e^z - add(z^s/s!, s in S). SeqRTChildNone:=proc(S,N) local s,z,L,PHI: PHI:=exp(z) - add(z^s/s!, s in S): L:=FunEqToSeq(PHI,z,N): [seq(L[n]*(n-1)!,n=1..N)]: end: (i) SeqRTChildNone({1, 2}, 30) [1, 0, 0, 1, 1, 1, 61, 246, 729, 22051, 193561, 1153978, 25992649, 368290209, 3619887363, 74509388656, 1420435858417, 20271512803303, 428725353547117, 9872556378092766, 186961525866478761, 4317736699240845805, 113492882882800515535, 2669952170961797149156, 69059808233257428803401, 2018641382623149640513851, 56238716096480662967484081, 1637920056805332921893074546, 52650525382805778576597086569, 1679484335855422749631762260121] It is not in the OEIS (ii) SeqRTChildNone({1, 2, 3}, 30) [1, 0, 0, 0, 1, 1, 1, 1, 281, 1135, 3361, 8713, 783289, 7075355, 42192151, 206453131, 9727350257, 149422339903, 1483505923645, 11690484981789, 375824751703161, 8173406337028675, 119863942175488875, 1379017283148135975, 36516018549625248841, 980779204163493676351, 19460971407734285961481, 305079514094150283442321, 7622525402745905601965401, 230581883946133059175865275] It is not in the OEIS (iii) SeqRTChildNone({1, 2, 3, 4}, 30) [1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1261, 5083, 15049, 39040, 94095, 26703106, 242645937, 1445190163, 7063252345, 30713549325, 3467477713761, 55087455406390, 548298265584125, 4313975702715330, 29370033464851825, 1758288383281605101, 41424117194948674031, 615177735843374133121, 7081297407826615761901, 69255460536880575742576] It is not in the OEIS (iv) SeqRTChildNone({1, 3, 4}, 30) [1, 0, 1, 0, 12, 1, 451, 148, 35505, 27541, 4821211, 6975288, 1007545573, 2369082730, 300704785655, 1050240928831, 121583984407857, 592027446976091, 64041616604580841, 414780100455390378, 42635572730328004261, 354196157772778274500, 35024483732872322607821, 362576912900624663442105, 34815127209112239918273457, 438638549156438062927762601, 41201435050491421031389436231, 619492504282986165209176098628, 57261194019173751540748961020225, 1010554002512105627151914470410426] It is not in the OEIS. (v) SeqRTChildNone({2, 3, 4}, 30) [1, 1, 2, 6, 24, 121, 757, 5972, 60769, 788914, 12399491, 222150424, 4348306393, 90867371921, 2006169506265, 46630242451111, 1141190198127793, 29462067766475748, 804355224385864519, 23269813100199902122, 713946847345599428081, 23213606558368681361551, 798040311553925561545887, 28908822754565311755807361, 1099174601426534901573249649, 43700377553623094727126483726, 1810731004007338168740285181557, 77988978183106442376896073508072, 3484767839335060091199869518501229, 161312302904810820468129825926640229] It is not in the OEIS. QUESTION #4: L:=TreeSeqL(50,x): (i) Running [seq(AveAndMoms(L[i], x, 2)[1]/i, i = 1 .. 50)], we get: [1., 0.5000000000, 0.4444444443, 0.4218750000, 0.4096000000, 0.4018775720, 0.3965694566, 0.3926959038, 0.3897443431, 0.3874204890, 0.3855432895, 0.3839952306, 0.3826967067, 0.3815918726, 0.3806403927, 0.3798124058, 0.3790853319, 0.3784417801, 0.3778681390, 0.3773536026, 0.3768894829, 0.3764687155, 0.3760854967, 0.3757350149, 0.3754132467, 0.3751168023, 0.3748428052, 0.3745887982, 0.3743526714, 0.3741326000, 0.3739270013, 0.3737344922, 0.3735538615, 0.3733840426, 0.3732240931, 0.3730731769, 0.3729305497, 0.3727955466, 0.3726675726, 0.3725460922, 0.3724306237, 0.3723207314, 0.3722160212, 0.3721161345, 0.3720207460, 0.3719295583, 0.3718422998, 0.3717587219, 0.3716785965, 0.3716017144] We can see that the average is converging to ~0.371 (ii) We can find the limit of the standard deviations divided by n by running: [seq(AveAndMoms(L[i], x, 2)[2]/i, i = 1 .. 50)] [0., 0., 0.1571348402, 0.1457402977, 0.1335209347, 0.1233425370, 0.1149906649, 0.1080523762, 0.1021956270, 0.09717699729, 0.09281933018, 0.08899205425, 0.08559723085, 0.08256006771, 0.07982247273, 0.07733861994, 0.07507184788, 0.07299245333, 0.07107609347, 0.06930261150, 0.06765515952, 0.06611953482, 0.06468367113, 0.06333724367, 0.06207136020, 0.06087831585, 0.05975139715, 0.05868472446, 0.05767312338, 0.05671202010, 0.05579735455, 0.05492550884, 0.05409324727, 0.05329766579, 0.05253614997, 0.05180633864, 0.05110609335, 0.05043347208, 0.04978670664, 0.04916418330, 0.04856442563, 0.04798608012, 0.04742790314, 0.04688874991, 0.04636756444, 0.04586337100, 0.04537526651, 0.04490241352, 0.04444403439, 0.04399940582] As we can see, the standard deviation divided by n is converging to ~0.043 (iii) We can find the limit of the 3rd moments divided by n by running: [seq(AveAndMoms(L[i], x, 3)[3]/i, i = 3 .. 50)] [0.2357022603, 0.04621174720, 0.02131360716, 0.01304227277, 0.009162479703, 0.006963795701, 0.005562753972, 0.004597233260, 0.003894018938, 0.003360520378, 0.002942943349, 0.002607954534, 0.002333818015, 0.002105763504, 0.001913407645, 0.001749241095, 0.001607700989, 0.001484580636, 0.001376641599, 0.001281351585, 0.001196702997, 0.001121084576, 0.001053188901, 0.0009919445546, 0.0009364656207, 0.0008860135829, 0.0008399681914, 0.0007978049473, 0.0007590775184, 0.0007234038669, 0.0006904552145, 0.0006599471897, 0.0006316326723, 0.0006052959675, 0.0005807480330, 0.0005578225442, 0.0005363726285, 0.0005162681460, 0.0004973934061, 0.0004796452483, 0.0004629314158, 0.0004471691752, 0.0004322841378, 0.0004182092493, 0.0004048839257, 0.0003922532996, 0.0003802675759, 0.0003688814676] The limit of the 3rd moments divided by n is approaching 0.0003, close to 0. (iv) We can find the limit of the 4th moments divided by n by running: [seq(AveAndMoms(L[i], x, 4)[4]/i, i = 4 .. 50)] [0.5944312328, 0.5353725782, 0.4613071085, 0.4021062583, 0.3555393622, 0.3183399688, 0.2880591791, 0.2629763365, 0.2418785886, 0.2238956692, 0.2083901969, 0.1948859865, 0.1830207124, 0.1725140824, 0.1631460113, 0.1547413581, 0.1471590550, 0.1402842321, 0.1340224214, 0.1282952297, 0.1230370655, 0.1181926326, 0.1137149888, 0.1095640282, 0.1057052812, 0.1021089593, 0.09874918697, 0.09560338023, 0.09265173972, 0.08987683455, 0.08726325871, 0.08479734540, 0.08246692856, 0.08026114238, 0.07817025226, 0.07618551128, 0.07429903825, 0.07250371300, 0.07079308693, 0.06916130556, 0.06760304168, 0.06611343733, 0.06468805326, 0.06332282477, 0.06201402300, 0.06075822104, 0.05955226392] The limit of the 4th moments divided by n is approaching ~0.05, close to 0. (v) We can find the limit of the 5th moments divided by n by running: [seq(AveAndMoms(L[i], x, 5)[5]/i, i = 5 .. 50)] [0.2400269516, 0.1343595885, 0.09182986553, 0.06905021615, 0.05491477323, 0.04530490436, 0.03835613249, 0.03310465408, 0.02900237991, 0.02571444514, 0.02302454274, 0.02078661791, 0.01889843643, 0.01728627474, 0.01589562274, 0.01468530938, 0.01362366285, 0.01268592676, 0.01185247670, 0.01110756177, 0.01043839895, 0.009834509896, 0.009287227626, 0.008789324496, 0.008334727872, 0.007918300483, 0.007535668803, 0.007183087725, 0.006857332888, 0.006555614247, 0.006275506254, 0.006014890953, 0.005771911357, 0.005544933026, 0.005332512123, 0.005133368850, 0.004946365093, 0.004770485674, 0.004604822402, 0.004448560595, 0.004300967511, 0.004161382454, 0.004029208311, 0.003903904167, 0.003784978971, 0.003671986026] The limit of the 5th moments divided by n is approaching ~0.003, close to 0. (v) We can find the limit of the 6th moments divided by n by running: [seq(AveAndMoms(L[i], x, 6)[6]/i, i = 6 .. 50)] [1.940449677, 1.765109249, 1.597170504, 1.452045918, 1.328567252, 1.223256409, 1.132792800, 1.054434908, 0.9860028571, 0.9257766200, 0.8723949469, 0.8247728353, 0.7820379700, 0.7434826874, 0.7085277855, 0.6766951667, 0.6475870150, 0.6208698191, 0.5962620088, 0.5735243036, 0.5524521162, 0.5328695207, 0.5146244304, 0.4975847090, 0.4816350173, 0.4666742365, 0.4526133469, 0.4393736785, 0.4268854521, 0.4150865603, 0.4039215456, 0.3933407330, 0.3832994984, 0.3737576436, 0.3646788602, 0.3560302734, 0.3477820438, 0.3399070265, 0.3323804739, 0.3251797769, 0.3182842393, 0.3116748794, 0.3053342567, 0.2992463188, 0.2933962654] The limit of the 6th moments divided by n is approaching ~0.29.