#OK to post #Soham Palande, Assignment 22, 12/06/2020 #PART 1 #(i) How many labeled ROOTED trees are there with 67 vertices and 12 leaves? (recall that a leaf is a vertex with no #children) S:=TreeSeqL(67,t): coeff(S[67],t,12) 762668035595791008261768918050546247626868131307789154916300139847357281766830345010754357481701376000000000000000 #(ii) How many labeled connected graphs are there with 40 vertices and 43 edges? #Here we set r=4, since 43 edges is 4 more edges than a tree with 40 vertices would have (a tree with 40 vertices #would have 39 edges) ATreeSeq(40,4)[40] 90324445150366623501655158316607196285055246080819484164096000000000 #PART 2 SeqRTchild:=proc(S,N) local L,z,n: L:=FunEqToSeq((1+add((z^s)/s!,s in S)),z,N): [seq(L[n]*(n-1)!,n=1..N)]: end: 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] #Not in the OEIS 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] #Not in the OEIS 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] #Not in the OEIS 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] #Not in the OEIS 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] #Not in the OEIS # PART 3 # I create a variable sum which adds all the terms z^s/s! for every s in S #Then when using FunEqToSeq, I pass in exp(z)-sum to include all the children not in S SeqRTchildNone:=proc(S,N) local L,z,n,sum: sum:=add((z^s)/s!, s in S): L:=FunEqToSeq(exp(z)-sum,z,N): [seq(L[n]*(n-1)!,n=1..N)]: end: 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] #Not in the OEIS 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] #Not in the OEIS 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] #Not in the OEIS 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] #Not in the OEIS 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] #Not in the OEIS #PART 4 #(i) Estimate the limit of the average number of leaves in a labelled tree with vertex n #divided by n seq(AveAndMoms(TreeSeqL(n,x)[n],x,6)[1]/n,n=3..50) .4444444443, .4218750000, .4096000000, .4018775720, .3965694566, .3926959038, .3897443431, .3874204890, .3855432895, .3839952306, .3826967067, .3815918726, .3806403927, .3798124058, .3790853319, .3784417801, .3778681390, .3773536026, .3768894829, .3764687155, .3760854967, .3757350149, .3754132467, .3751168023, .3748428052, .3745887982, .3743526714, .3741326000, .3739270013, .3737344922, .3735538615, .3733840426, .3732240931, .3730731769, .3729305497, .3727955466, .3726675726, .3725460922, .3724306237, .3723207314, .3722160212, .3721161345, .3720207460, .3719295583, .3718422998, .3717587219, .3716785965, .3716017144 #The limit appears to be approaching 0.371. #(ii) Estimate the limit of the standard-deviation of the number of the random variable ` #number of leaves in a labelled tree with vertex n', divided by n seq(AveAndMoms(TreeSeqL(n,x)[n],x,6)[2]/n,n=3..60) .1571348402, .1457402977, .1335209347, .1233425370, .1149906649, .1080523762, .1021956270, 0.9717699729e-1, 0.9281933018e-1, 0.8899205425e-1, 0.8559723085e-1, 0.8256006771e-1, 0.7982247273e-1, 0.7733861994e-1, 0.7507184788e-1, 0.7299245333e-1, 0.7107609347e-1, 0.6930261150e-1, 0.6765515952e-1, 0.6611953482e-1, 0.6468367113e-1, 0.6333724367e-1, 0.6207136020e-1, 0.6087831585e-1, 0.5975139715e-1, 0.5868472446e-1, 0.5767312338e-1, 0.5671202010e-1, 0.5579735455e-1, 0.5492550884e-1, 0.5409324727e-1, 0.5329766579e-1, 0.5253614997e-1, 0.5180633864e-1, 0.5110609335e-1, 0.5043347208e-1, 0.4978670664e-1, 0.4916418330e-1, 0.4856442563e-1, 0.4798608012e-1, 0.4742790314e-1, 0.4688874991e-1, 0.4636756444e-1, 0.4586337100e-1, 0.4537526651e-1, 0.4490241352e-1, 0.4444403439e-1, 0.4399940582e-1, 0.4356785420e-1, 0.4314875108e-1, 0.4274150949e-1, 0.4234558057e-1, 0.4196045025e-1, 0.4158563666e-1, 0.4122068742e-1, 0.4086517745e-1, 0.4051870693e-1, 0.4018089920e-1 #The first 60 terms indicate that the limit is approaching some value near 0.040 #Limit of the 3rd moment - first 50 terms seq(AveAndMoms(TreeSeqL(n,x)[n],x,6)[3],n=3..50) .7071067810, .1848469888, .1065680358, 0.7825363662e-1, 0.6413735792e-1, 0.5571036561e-1, 0.5006478575e-1, 0.4597233260e-1, 0.4283420832e-1, 0.4032624454e-1, 0.3825826354e-1, 0.3651136348e-1, 0.3500727023e-1, 0.3369221607e-1, 0.3252792996e-1, 0.3148633971e-1, 0.3054631879e-1, 0.2969161273e-1, 0.2890947357e-1, 0.2818973488e-1, 0.2752416892e-1, 0.2690602982e-1, 0.2632972253e-1, 0.2579055842e-1, 0.2528457176e-1, 0.2480838032e-1, 0.2435907755e-1, 0.2393414842e-1, 0.2353140307e-1, 0.2314892374e-1, 0.2278502208e-1, 0.2243820445e-1, 0.2210714353e-1, 0.2179065483e-1, 0.2148767722e-1, 0.2119725668e-1, 0.2091853251e-1, 0.2065072584e-1, 0.2039312965e-1, 0.2014510043e-1, 0.1990605088e-1, 0.1967544371e-1, 0.1945278620e-1, 0.1923762547e-1, 0.1902954451e-1, 0.1882815838e-1, 0.1863311122e-1, 0.1844407338e-1 #Limit of the 4th moment - first 50 terms seq(AveAndMoms(TreeSeqL(n,x)[n],x,6)[4],n=3..50) 1.500000000, 2.377724931, 2.676862891, 2.767842651, 2.814743808, 2.844314898, 2.865059719, 2.880591791, 2.892739701, 2.902543063, 2.910643699, 2.917462756, 2.923289797, 2.928331398, 2.932739401, 2.936628204, 2.940085803, 2.943181100, 2.945968875, 2.948493271, 2.950790283, 2.952889573, 2.954815815, 2.956589710, 2.958228762, 2.959747875, 2.961159820, 2.962475609, 2.963704787, 2.964855671, 2.965935540, 2.966950796, 2.967907089, 2.968809428, 2.969662268, 2.970469586, 2.971234940, 2.971961530, 2.972652233, 2.973309651, 2.973936139, 2.974533834, 2.975104680, 2.975650450, 2.976172764, 2.976673104, 2.977152831, 2.977613196 #Limit of the 5th moment - first 50 terms seq(AveAndMoms(TreeSeqL(n,x)[n],x,6)[5],n=3..50) 1.767766952, 2.785027964, 1.200134758, .8061575308, .6428090587, .5524017292, .4942329591, .4530490436, .4219174574, .3972558490, .3770309388, .3600022320, .3453681411, .3325858865, .3212734193, .3111529453, .3020168320, .2937061876, .2860969199, .2790903887, .2726069640, .2665814825, .2609599738, .2556972573, .2507551459, .2461010859, .2417071083, .2375490145, .2336057329, .2298588072, .2262919853, .2228908844, .2196427189, .2165360743, .2135607202, .2107074550, .2079679728, .2053347540, .2028009688, .2003603983, .1980073633, .1957366662, .1935435380, .1914235929, .1893727906, .1873874000, .1854639696, .1835993013 #Limit of the 6th moment - first 50 terms seq(AveAndMoms(TreeSeqL(n,x)[n],x,6)[6],n=3..50) 2.750000000, 9.162459397, 9.755209727, 11.64269806, 12.35576474, 12.77736403, 13.06841326, 13.28567252, 13.45582050, 13.59351360, 13.70765380, 13.80404000, 13.88664930, 13.95831915, 14.02113820, 14.07668346, 14.12617106, 14.17055571, 14.21059850, 14.24691433, 14.28000584, 14.31028821, 14.33810759, 14.36375502, 14.38747706, 14.40948405, 14.42995656, 14.44905052, 14.46690133, 14.48362710, 14.49933139, 14.51410537, 14.52802961, 14.54117564, 14.55360712, 14.56538094, 14.57654810, 14.58715441, 14.59724121, 14.60684584, 14.61600214, 14.62474085, 14.63308996, 14.64107501, 14.64871933, 14.65604432, 14.66306962, 14.66981327 #Appears to be approaching a value near 14.6