#OK to post homework #Kent Mei, 12/06/20, Assignment 22 #--------------------------------- #Part 1 #i) #coeff(TreeSeqL(67,t)[67],t,12); #762668035595791008261768918050546247626868131307789154916300139847357281766830345010754357481701376000000000000000 #labeled rooted trees with 67 vertices and 12 leaves exist. #ii) #40-1+r = 43 #r = 4 #ATreeSeq(40,4)[40]; #90324445150366623501655158316607196285055246080819484164096000000000 #labeled connected graphs have 40 vertices and 43 edges. #--------------------------------- #Part 2 SeqRTchild:=proc(S,N) local eq, s, L: eq := 1: for s in S do eq := eq + (z^s / s!): od: L := FunEqToSeq(eq, z, N): [seq(L[n]*n!, n = 1..N)]: end: #i) #SeqRTchild({1,2},30); #[1, 2, 9, 60, 540, 6120, 83790, 1345680, 24811920, 516650400, 11992503600, 307069963200, 8598348158400, 261387760233600, 8573572885878000, 301809119163552000, 11349727401396384000, 454104511068656448000, 19261139319649202976000, 863322072620761353600000, 40773827104421643872640000, 2023875495295596087425280000, 105332242685105264094826560000, 5735708550546738271386278400000, 326147227825931039498338368000000, 19331417684656062052163800704000000, 1192397948395996947851508470208000000, 76423144363428788116850162439936000000, 5082319675112720794728326340468480000000, 350237858762665841457922825150517760000000] #A36774 #ii) #SeqRTchild({1,2,3},30); #[1, 2, 9, 64, 620, 7620, 113610, 1992480, 40194000, 916927200, 23341071600, 655922836800, 20169411662400, 673645440468000, 24285190867938000, 939899116892736000, 38870133445791648000, 1710655202853140544000, 79826043011286892320000, 3936948118406837614080000, 204621522793150838094720000, 11178604265076638556566400000, 640388553630453545818380480000, 38387232536896126731768560640000, 2403064339811928039326054976000000, 156818747958686937121259124864000000, 10650385643669848416683879984448000000, 751628530768336472601918781589376000000, 55042291463200564036152308362108416000000, 4177087476268464699702716097295433280000000] #A36775 #iii) #SeqRTchild({1,2,3,4},30); #[1, 2, 9, 64, 625, 7770, 117390, 2088520, 42771960, 991090800, 25635767850, 732235165200, 22890759391500, 777398836414200, 28501053507927000, 1121908690738836000, 47194400446765572000, 2112854517933207048000, 100302903229033765260000, 5032863920347902999360000, 266142789859931099850735000, 14793716799246351968271270000, 862334292493260819652189770000, 52598740360757139570304122840000, 3350601497282429844614781621000000, 222502645937108446633845155034000000, 15377726069589880161099060181555500000, 1104405005369409845057238883356756000000, 82305294967517874944444655399748251000000, 6356500157372156884942344746141640750000000] #A36776 #iv) #SeqRTchild({1,3,4},30); #[1, 2, 6, 28, 205, 2070, 25410, 359800, 5798520, 105663600, 2155645800, 48657886200, 1202586485100, 32282071621800, 935338118715000, 29098128631572000, 967482670702548000, 34237946556613800000, 1284878182355343576000, 50967054449973501840000, 2130726049102025710335000, 93635584072373169516690000, 4315205169032986063745910000, 208100688549145598367481320000, 10480987284242370363188721000000, 550305134278266412524553074000000, 30071585130474224199248414028000000, 1707632930666682627425158334994000000, 100623961896825486602731615774407000000, 6144749285013439594202104990964370000000] #It is not in the OEIS. #v) #SeqRTchild({2,3,4},30); #[1, 0, 3, 4, 65, 300, 4200, 37240, 567000, 7459200, 130873050, 2248785000, 45820074300, 960718558800, 22551581052000, 554522292324000, 14815285064580000, 416528503687296000, 12512460971526516000, 395230114168409520000, 13202761194110062575000, 462497255518711713300000, 17016880547516875585560000, 654449323331533231461960000, 26304817680413388661545000000, 1101639603994780236225840000000, 48032136805779324344283637500000, 2175711882725905740823116510000000, 102281934821615478250848501975000000, 4982410035314032207875141453300000000] #It is not in the OEIS. #--------------------------------- #Part 3 SeqRTchildNone:=proc(S,N) local eq, s, L: eq := exp(z): for s in S do eq := eq - (z^s / s!): od: L := FunEqToSeq(eq, z, N): [seq(L[n]*n!, n = 1..N)]: end: #i) #SeqRTchildNone({1,2},30); #[1, 0, 0, 4, 5, 6, 427, 1968, 6561, 220510, 2129171, 13847736, 337904437, 5156062926, 54298310445, 1192150218496, 24147409593089, 364887230459454, 8145781717395223, 197451127561855320, 3926192043196053981, 94990207383298607710, 2610336306304411857305, 64078852103083131579744, 1726495205831435720085025, 52484675948201890653360126, 1518445334604977900122070187, 45861761590549321813006087288, 1526865236101367578721315510501, 50384530075662682488952867803630] #It is not in the OEIS. #ii) #SeqRTchildNone({1,2,3},30); #[1, 0, 0, 0, 5, 6, 7, 8, 2529, 11350, 36971, 104556, 10182757, 99054970, 632882265, 3303250096, 165364954369, 2689602118254, 28186612549255, 233809699635780, 7892319785766381, 179814939414630850, 2756870670036244125, 33096414795555263400, 912900463740631221025, 25500259308250835585126, 525446228008825720959987, 8542226394636207936384988, 221053236679631262456996629, 6917456518383991775275958250] #It is not in the OEIS. #iii) #SeqRTchildNone({1,2,3,4},30); #[1, 0, 0, 0, 0, 6, 7, 8, 9, 10, 13871, 60996, 195637, 546560, 1411425, 427249696, 4124980929, 26013422934, 134201794555, 614270986500, 72817031988981, 1211924018940580, 12610860108434875, 103535416865167920, 734250836621295625, 45715497965321732626, 1118451164263614198837, 17224976603614475727388, 205357624826971857095129, 2077663816106417272277280] #It is not in the OEIS. #iv) #SeqRTchildNone({1,3,4},30); #[1, 0, 3, 0, 60, 6, 3157, 1184, 319545, 275410, 53033321, 83703456, 13098092449, 33167158220, 4510571784825, 16803854861296, 2066927734933569, 10656494045569638, 1216790715487035979, 8295602009107807560, 895347027336888089481, 7792315471001122039000, 805563125856063419979883, 8701845909614991922610520, 870378180227805997956836425, 11404602278067389636121827626, 1112438746363268367847514778237, 17345790119923612625856930761584, 1660574626556038794681719869586525, 30316620075363168814557434112312780] #It is not in the OEIS. #v) #SeqRTchildNone({2,3,4},30); #[1, 2, 6, 24, 120, 726, 5299, 47776, 546921, 7889140, 136394401, 2665805088, 56527983109, 1272143206894, 30092542593975, 746083879217776, 19400233368172481, 530317219796563464, 15282749263331425861, 465396262003998042440, 14992883794257587989701, 510699344284110989954122, 18354927165740287915555401, 693811746109567482139376664, 27479365035663372539331241225, 1136209816394200462905288576876, 48889737108198130555987699902039, 2183691389126980386553090058226016, 101058267340716742644796216036535641, 4839369087144324614043894777799206870] #It is not in the OEIS. #--------------------------------- #Part 4 #f := TreeSeqL(70,t)[70] #S := AveAndMoms(f,t,6); #L := [seq(S[i] / 70, i = 1..6)] #S = [25.93704765, 2.604705094, 0.1557325301e-1, 2.984041486, .1552233733, 14.76417378] #L = [.3705292521, 0.3721007277e-1, 0.2224750430e-3, 0.4262916409e-1, 0.2217476761e-2, .2109167683] #I basically made N as large as possible such that Maple could compute the above commands in a timely manner and used the output to estimate the limits. #i) #The limit of the average number of leaves / n is approximately 0.370529521 #(approaching the value 1/e). #ii) #The limit of the standard deviation / n is approximately 0.3721007277e-1 #iii) #The third, fourth, fifth, and sixth scaled moments (over n) are approximately 0.2224750430e-3, 0.4262916409e-1, 0.2217476761e-2, .2109167683 #--------------------------------- #Part 5 #Optional challenge #From the attendance quiz, we were able to conjecture that the average number #of leaves of a labelled tree with n vertices is (n-1)^(n-1)/(n^(n-2)). If you #divide that by n, we get ((n-1)/n)^(n-1)) which if we take the limit as n -> #infinity, we get 1/e. #--------------------------------- #Part 6 #Optional challenge, did not have the chance to do it.