Sequences Enumerating Labeled trees where all vertices are restricted to hav\ e degrees in a given set S for all possible subsets of three or more of, {1, 2, 3, 4, 5}, that must include 1 of course By Shalosh B. Ekhad In the list below we give the first, 30, terms , followed by the linear recurrence, followed by the asympotics. ------------------------------------------------- If the set of allowed vertex-degrees is, [1, 2, 3], then the first, 30, terms are [0, 1, 3, 16, 120, 1170, 14070, 201600, 3356640, 63730800, 1359666000, 32212857600, 839350512000, 23860289653200, 734964075846000, 24388126963200000, 867393811956672000, 32919980214689568000, 1328053572854936928000, 56752039046079336960000, 2561025679541636186880000, 121704153816369677192640000, 6075255163076158964224320000, 317833937499587100371619840000, 17390368207022203566036864000000, 993258771718938181397164224000000, 59115387099369331836549347904000000, 3660342897283890088556413320192000000, 235438414892005020971515517781504000000, 15709607781751483290617894230142880000000] The enumerating sequence satisfies the recurrence -(n-1)*(n+2)*(n+1)/(n+4)*a(n)-(n+2)*(2*n+3)/(n+4)*a(n+1)+a(n+2) = 0 The asymptotics is CONST*n!*2.414213562^n/n^(5/2) where the CONST. is roughly, 1.042 ------------------------------------------------------------ Finally, the limiting distribution of the vertices whose degrees are, [1, 2, 3], are (approximately) respectively, [0.2959, 0.41489, 0.2892] and the respective limits of the variances (divided by n) are, respectively, [0.0607576, 0.24303, 0.0607576] ----------------------------------------------------------------- If the set of allowed vertex-degrees is, [1, 2, 4], then the first, 30, terms are [0, 1, 3, 12, 65, 480, 4620, 54320, 745920, 11692800, 206514000, 4064860800, 88259371200, 2095070577600, 53968306392000, 1499410104192000, 44696761261152000, 1423059292182528000, 48195832584227328000, 1730144058671508480000, 65623332286465873920000, 2622397193856944824320000, 110124935079948075006720000, 4848496036747958859264000000, 223326483425789188693248000000, 10740928221971019655494912000000, 538440526872229039428674304000000, 28087628922692777708337779712000000, 1522351971008326954013726976768000000, 85610533117981348799552645775360000000] The enumerating sequence satisfies the recurrence -17/4*n*(n-1)*(n+3)*(n+2)*(n+1)/(n+4)/(2*n+5)*a(n)+3*n*(2*n+3)*(n+3)*(n+2)/(n+4 )/(2*n+5)*a(n+1)-2*(n+3)*(3*n^2+12*n+10)/(n+4)/(2*n+5)*a(n+2)+a(n+3) = 0 The asymptotics is CONST*n!*2.040041912^n/n^(5/2) where the CONST. is roughly, 0.8218 ------------------------------------------------------------ Finally, the limiting distribution of the vertices whose degrees are, [1, 2, 4], are (approximately) respectively, [0.34156, 0.49100, 0.16744] and the respective limits of the variances (divided by n) are, respectively, [0.111251, 0.25032, 0.0278129] ----------------------------------------------------------------- If the set of allowed vertex-degrees is, [1, 2, 5], then the first, 30, terms are [0, 1, 3, 12, 60, 366, 2730, 25200, 287280, 3934350, 62182890, 1096464600, 21129708600, 440671631400, 9908773875000, 239808711542400, 6234049982160000, 173516376645612000, 5149423328301252000, 162213134225622480000, 5401769292906818832000, 189500705036717084010000, 6984018122815983158910000, 269796476408121256754160000, 10903240664178662894094000000, 460135281914408048214766500000, 20243490484357908839863291500000, 926924668738497361069299162000000, 44105004435931095257796573378000000, 2177633700080818413877438885890000000] The enumerating sequence satisfies the recurrence 49/9*n*(n-1)*(n+4)*(n+3)*(n+1)^2/(3*n+10)/(3*n+14)*a(n)-18*n*(2*n+3)*(n+4)*(n+3 )*(n+1)/(3*n+10)/(3*n+14)*a(n+1)+(n+4)*(n+3)*(n+1)*(54*n^2+216*n+203)/(3*n+10)/ (3*n+14)/(n+2)*a(n+2)-(n+4)*(36*n^3+270*n^2+640*n+483)/(3*n+10)/(3*n+14)/(n+2)* a(n+3)+a(n+4) = 0 The asymptotics is CONST*n!*1.792804743^n/n^(5/2) where the CONST. is roughly, 0.9798 ------------------------------------------------------------ Finally, the limiting distribution of the vertices whose degrees are, [1, 2, 5], are (approximately) respectively, [0.33263, 0.55872, 0.10865] and the respective limits of the variances (divided by n) are, respectively, [0.138978, 0.24707, 0.01544201] ----------------------------------------------------------------- If the set of allowed vertex-degrees is, [1, 3, 4], then the first, 30, terms are [0, 1, 0, 4, 5, 90, 420, 5600, 52920, 730800, 10256400, 164656800, 2939937000, 56142886800, 1190377188000, 26706423744000, 651950675376000, 16838032891680000, 465265914841728000, 13582334058733440000, 419602472077108320000, 13648210938612169920000, 466562313357047107200000, 16722953511562989250560000, 626966656458493006656000000, 24547892138945458291008000000, 1001638073959707644460000000000, 42533250612485662567137600000000, 1876441464260951549655854160000000, 85894888327259311897211815200000000] The enumerating sequence satisfies the recurrence -15/4*n*(n-1)*(n+2)*(n+1)/(2*n+7)*a(n)-3/4*n*(n+2)*(6*n^2+33*n+41)/(2*n+7)/(n+4 )*a(n+1)+3/4*(n+5)*(n+3)*n/(2*n+7)/(n+4)*a(n+2)+a(n+3) = 0 The asymptotics is CONST*n!*1.660324085^n/n^(5/2) where the CONST. is roughly, 0.3994 ------------------------------------------------------------ Finally, the limiting distribution of the vertices whose degrees are, [1, 3, 4], are (approximately) respectively, [0.56104, 0.32356, 0.11540] and the respective limits of the variances (divided by n) are, respectively, [0.0155701, 0.14013, 0.062280] ----------------------------------------------------------------- If the set of allowed vertex-degrees is, [1, 3, 5], then the first, 30, terms are [0, 1, 0, 4, 0, 96, 0, 5880, 0, 683550, 0, 129313800, 0, 36223387200, 0, 14094984103200, 0, 7275575535228000, 0, 4811642732136240000, 0, 3967691129991388800000, 0, 3991375137025731054600000, 0, 4811392816343744493762900000, 0, 6846804324864301430743110000000, 0, 11357131848177021686356777200000000] The enumerating sequence satisfies the recurrence -8/9*n*(n-1)*(n+3)*(n+2)*(n+1)^2/(3*n+14)/(3*n+4)*a(n)-4/3*(n+3)*(n+1)*(15*n^2+ 60*n+56)/(3*n+14)/(3*n+4)*a(n+2)+a(n+4) = 0 The asymptotics is CONST*n!*1.505261323^n/n^(5/2) where the CONST. is roughly, 0.9900 ------------------------------------------------------------ ----------------------------------------------------------------- If the set of allowed vertex-degrees is, [1, 4, 5], then the first, 30, terms are [0, 1, 0, 0, 5, 6, 0, 560, 2520, 3150, 277200, 2772000, 9909900, 382582200, 6558552000, 45909864000, 1190713524000, 29010241260000, 332427775680000, 7313411064960000, 218439330236127000, 3655609865197290000, 79288023410275680000, 2621933205677145360000, 58840167700503189000000, 1375163261065433139300000, 47731998302599911300000000, 1340980838219350528200000000, 35272433824747740756135000000, 1264547753437112917923150000000] The enumerating sequence satisfies the recurrence 4/9*n*(n-1)*(n+3)*(n+2)*(100*n^3+1080*n^2+3825*n+4424)*(n+1)^2/(3*n+13)/(3*n+14 )/(100*n^3+780*n^2+1965*n+1579)*a(n)-8/9*n*(n+3)*(n+2)*(n+1)*(1200*n^4+14760*n^ 3+65300*n^2+121653*n+79117)/(3*n+13)/(3*n+14)/(100*n^3+780*n^2+1965*n+1579)*a(n +1)+4/9*n*(n+3)*(n+1)*(300*n^4+4440*n^3+23885*n^2+55577*n+47237)/(3*n+13)/(3*n+ 14)/(100*n^3+780*n^2+1965*n+1579)*a(n+2)-4/9*(n+1)*(800*n^5+13840*n^4+94320*n^3 +315947*n^2+519106*n+333774)/(3*n+13)/(3*n+14)/(100*n^3+780*n^2+1965*n+1579)*a( n+3)+a(n+4) = 0 The asymptotics is CONST*n!*1.141560030^n/n^(5/2) where the CONST. is roughly, 0.4226 ------------------------------------------------------------ Finally, the limiting distribution of the vertices whose degrees are, [1, 4, 5], are (approximately) respectively, [0.69337, 0.23318, 0.073449] and the respective limits of the variances (divided by n) are, respectively, [0.00519354, 0.083097, 0.046742] ----------------------------------------------------------------- If the set of allowed vertex-degrees is, [1, 2, 3, 4], then the first, 30, terms are [0, 1, 3, 16, 125, 1290, 16590, 255920, 4609080, 94978800, 2204848800, 56949631200, 1620257238600, 50353072770000, 1697293852254000, 61682913163872000, 2404329063248112000, 100063862555713056000, 4428789208130038752000, 207722713185360172800000, 10292152416527198337120000, 537184746331461797849280000, 29459678797959895162117440000, 1693611870329614431532976640000, 101851015232620436039345088000000, 6395057909890043467680839232000000, 418486823618120042177079271584000000, 28494974731169644390364306386752000000, 2015805191037831850078647493251984000000, 147950021363423827353837395054090400000000] The enumerating sequence satisfies the recurrence -1/2*n*(n-1)*(n+1)*(n+3)^2/(n+4)/(2*n+7)*a(n)-1/2*n*(n+3)/(n+4)/(2*n+7)*a(n+1)-\ 1/4*(n+3)*(21*n^3+147*n^2+326*n+224)/(n+4)/(n+2)/(2*n+7)*a(n+2)+a(n+3) = 0 The asymptotics is CONST*n!*2.660324085^n/n^(5/2) where the CONST. is roughly, 0.5055 ------------------------------------------------------------ Finally, the limiting distribution of the vertices whose degrees are, [1, 2, 3, 4], are (approximately) respectively, [0.35079, 0.37651, 0.20126, 0.071434] and the respective limits of the variances (divided by n) are, respectively, [0.08293078, 0.23498, 0.11177, 0.041859] ----------------------------------------------------------------- If the set of allowed vertex-degrees is, [1, 2, 3, 5], then the first, 30, terms are [0, 1, 3, 16, 120, 1176, 14280, 207480, 3515400, 68118750, 1486713690, 36103082400, 965761196400, 28221827634000, 894612348630000, 30577827966285600, 1121095370254860000, 43890717759941052000, 1827526484494066356000, 80645297058051485760000, 3759652073792707092000000, 184645454826917409605280000, 9528860462088151731587040000, 515521793821135826058614280000, 29176874556418241422484715000000, 1724155281905078594439967799700000, 106191252387899334923345399821500000, 6805583776568075515719101190792000000, 453157948647777327631264058034564000000, 31306363004174687460742110258238380000000] The enumerating sequence satisfies the recurrence -107/9*n*(n-1)*(n+3)*(n+2)*(n+1)^2/(3*n+14)/(3*n+4)*a(n)+2*n*(2*n+3)*(n+3)*(n+2 )*(n+1)/(3*n+14)/(3*n+4)*a(n+1)+1/3*(n+3)*(n+1)*(102*n^2+408*n+349)/(3*n+14)/(3 *n+4)*a(n+2)-(2*n+5)*(18*n^2+90*n+83)/(3*n+14)/(3*n+4)*a(n+3)+a(n+4) = 0 The asymptotics is CONST*n!*2.505261323^n/n^(5/2) where the CONST. is roughly, 0.6386 ------------------------------------------------------------ Finally, the limiting distribution of the vertices whose degrees are, [1, 2, 3, 5], are (approximately) respectively, [0.33186, 0.39982, 0.23988, 0.028437] and the respective limits of the variances (divided by n) are, respectively, [0.0906936, 0.24023, 0.11194, 0.018860] ----------------------------------------------------------------- If the set of allowed vertex-degrees is, [1, 2, 4, 5], then the first, 30, terms are [0, 1, 3, 12, 65, 486, 4830, 59360, 854280, 14014350, 258717690, 5323764600, 120952131300, 3006595792200, 81139567509000, 2362254517022400, 73800885922764000, 2462955318771948000, 87450030435611844000, 3291627712621968720000, 130922747971074538479000, 5486879912937516663570000, 241667735891134807103850000, 11160348279786344995836480000, 539233408679063159124063000000, 27206285337271941408178971300000, 1430797751630925598118850151500000, 78304811981431283628590212002000000, 4452860038058722414936568309553000000, 262734885740016052535329349602410000000] The enumerating sequence satisfies the recurrence 25*n*(n-1)*(n+3)*(n+1)*(40*n^2+320*n+657)*(n+2)^2/(3*n+13)/(3*n+14)/(40*n^2+240 *n+377)*a(n)-10*n*(n+3)*(n+2)*(240*n^4+2760*n^3+11302*n^2+18962*n+10557)/(3*n+ 13)/(3*n+14)/(40*n^2+240*n+377)*a(n+1)+2*(n+3)*(n+1)*(1320*n^4+17160*n^3+82461* n^2+172810*n+132734)/(3*n+13)/(3*n+14)/(40*n^2+240*n+377)*a(n+2)-2/9*(n+2)*( 7120*n^4+103240*n^3+560186*n^2+1348190*n+1214829)/(3*n+13)/(3*n+14)/(40*n^2+240 *n+377)*a(n+3)+a(n+4) = 0 The asymptotics is CONST*n!*2.141560030^n/n^(5/2) where the CONST. is roughly, 0.5788 ------------------------------------------------------------ Finally, the limiting distribution of the vertices whose degrees are, [1, 2, 4, 5], are (approximately) respectively, [0.36998, 0.46773, 0.12356, 0.038730] and the respective limits of the variances (divided by n) are, respectively, [0.121931, 0.24932, 0.057602, 0.026072] ----------------------------------------------------------------- If the set of allowed vertex-degrees is, [1, 3, 4, 5], then the first, 30, terms are [0, 1, 0, 4, 5, 96, 420, 6440, 55440, 885150, 11503800, 206929800, 3544440900, 73220347200, 1536340806000, 36361268143200, 895996917816000, 24067397878524000, 678318876275040000, 20454364144534320000, 647627848594774047000, 21696796412967836160000, 761682411990993352860000, 28089660942200858920920000, 1082348648359622425782000000, 43586777189058524860338900000, 1828444028146879598885430000000, 79850220942831621547855590000000, 3622255848644666183076291165000000, 170522773104074386765088919600000000] The enumerating sequence satisfies the recurrence -92/9*n*(n-1)*(n+3)*(n+2)*(116*n^3+1280*n^2+4799*n+6162)*(n+1)^2/(3*n+14)/(3*n+ 13)/(116*n^3+932*n^2+2587*n+2527)*a(n)-4/9*n*(n+3)*(n+1)*(n+2)*(7656*n^4+95964* n^3+445294*n^2+905897*n+676968)/(3*n+14)/(3*n+13)/(116*n^3+932*n^2+2587*n+2527) *a(n+1)-4/9*(n+3)*(n+1)*(5220*n^5+78480*n^4+471269*n^3+1425183*n^2+2190976*n+ 1379742)/(3*n+14)/(3*n+13)/(116*n^3+932*n^2+2587*n+2527)*a(n+2)+2/9*(n+1)*(4408 *n^5+77292*n^4+540046*n^3+1882893*n^2+3281635*n+2290470)/(3*n+14)/(3*n+13)/(116 *n^3+932*n^2+2587*n+2527)*a(n+3)+a(n+4) = 0 The asymptotics is CONST*n!*1.707993250^n/n^(5/2) where the CONST. is roughly, 0.3357 ------------------------------------------------------------ Finally, the limiting distribution of the vertices whose degrees are, [1, 3, 4, 5], are (approximately) respectively, [0.57838, 0.29666, 0.099823, 0.025136] and the respective limits of the variances (divided by n) are, respectively, [0.0239009, 0.14933, 0.063123, 0.020710] ----------------------------------------------------------------- If the set of allowed vertex-degrees is, [1, 2, 3, 4, 5], then the first, 30, terms are [0, 1, 3, 16, 125, 1296, 16800, 261800, 4770360, 99568350, 2343123090, 61391484000, 1772641770900, 55931625750000, 1914804950058000, 70694359020885600, 2800031571437100000, 118434095757029052000, 5328242311045658004000, 254063027768147357760000, 12798914705149964598207000, 679272893430871268529000000, 37882701538869908538777960000, 2214894861537348248166668760000, 135475541925970857068362905000000, 8652128840223391250445366148500000, 575926446752465718087490383571500000, 39891608064418517208147503108952000000, 2870840148186465684315784192664169000000, 214358126491547865053337201555964500000000] The enumerating sequence satisfies the recurrence -1/3*n*(n-1)*(n+3)*(n+2)*(232*n^3+2400*n^2+8207*n+9300)*(n+1)^2/(3*n+13)/(3*n+ 14)/(232*n^3+1704*n^2+4103*n+3261)*a(n)-2/3*n*(n+3)*(n+2)*(n+1)*(80*n^2+343*n+ 51)/(3*n+13)/(3*n+14)/(232*n^3+1704*n^2+4103*n+3261)*a(n+1)+2/3*(n+3)*(n+1)*( 3016*n^5+43264*n^4+242671*n^3+663969*n^2+883674*n+455868)/(3*n+13)/(3*n+14)/( 232*n^3+1704*n^2+4103*n+3261)*a(n+2)-2/9*(n+2)*(28768*n^5+455824*n^4+2846852*n^ 3+8746991*n^2+13197471*n+7805826)/(3*n+13)/(3*n+14)/(232*n^3+1704*n^2+4103*n+ 3261)*a(n+3)+a(n+4) = 0 The asymptotics is CONST*n!*2.707993250^n/n^(5/2) where the CONST. is roughly, 0.4227 ------------------------------------------------------------ Finally, the limiting distribution of the vertices whose degrees are, [1, 2, 3, 4, 5], are (approximately) respectively, [0.36532, 0.36989, 0.18660, 0.062534, 0.015662] and the respective limits of the variances (divided by n) are, respectively, [0.0923924, 0.23330, 0.11440, 0.041940, 0.013080] ----------------------------------------------------------------- To sum up, here are all the sets followed by their growth constants [[{1, 2, 3}, 2.414213562], [{1, 2, 4}, 2.040041912], [{1, 2, 5}, 1.792804743], [{1, 3, 4}, 1.660324085], [{1, 3, 5}, 1.505261323], [{1, 4, 5}, 1.141560030], [ {1, 2, 3, 4}, 2.660324085], [{1, 2, 3, 5}, 2.505261323], [{1, 2, 4, 5}, 2.14156\ 0030], [{1, 3, 4, 5}, 1.707993250], [{1, 2, 3, 4, 5}, 2.707993250]] ----------------------------------------------------- This took, 3620.117, to generate