Generating Functions for Enumerating the Number of Spanning Trees (and Sum o\ f the Leaves) in Friendship graphs where n people live in a one-sided ST\ RAIGHT street, and every one is friends with all the neighbors distance \ at most r as well as their asymptotics and the BZ constant for r from 2 to, 5 By Shalosh B. Ekhad Theorem number, 1 Part I: Let a(n) be the number of spanning trees of the graph, H[n, 2], whose vertice\ s are 1, ...,n, and where every vertex i is connected to i+1,..., min(n, i + 2), Then infinity ----- \ n -8 + 3 x ) a[n + 2] x = - ------------ / 2 ----- x - 3 x + 1 n = 0 and in Maple notation -(-8+3*x)/(x^2-3*x+1) The asympotics is n 8.024922343 2.618033988 Part II: Let b(n) be the sum of the number of leaves in all spanning trees of the abo\ ve-mentioned graph, H[n, 2], Then infinity ----- 3 2 \ n 2 (2 x - 15 x + 27 x - 9) ) b[n + 2] x = - --------------------------- / 2 2 ----- (x - 3 x + 1) n = 0 and in Maple notation -2*(2*x^3-15*x^2+27*x-9)/(x^2-3*x+1)^2 The asympotics is n 2.094427187 2.618033988 (1. + n) The BZ constant is 0.2609903370 Theorem number, 2 Part I: Let a(n) be the number of spanning trees of the graph, H[n, 3], whose vertice\ s are 1, ...,n, and where every vertex i is connected to i+1,..., min(n, i + 3), Then infinity ----- 4 3 2 \ n 16 x - 77 x + 33 x - 39 x + 75 ) a[n + 3] x = - ---------------------------------- / 4 3 2 ----- (x - 1) (x - 4 x - x - 4 x + 1) n = 0 and in Maple notation -(16*x^4-77*x^3+33*x^2-39*x+75)/(x-1)/(x^4-4*x^3-x^2-4*x+1) The asympotics is n 76.24288486 4.419480366 Part II: Let b(n) be the sum of the number of leaves in all spanning trees of the abo\ ve-mentioned graph, H[n, 3], Then infinity ----- \ n 10 9 8 7 6 5 ) b[n + 3] x = 2 (16 x - 154 x + 403 x - 340 x + 963 x - 768 x / ----- n = 0 4 3 2 / 2 + 1109 x - 788 x + 509 x - 470 x + 96) / ((x - 1) / 4 3 2 2 (x - 4 x - x - 4 x + 1) ) and in Maple notation 2*(16*x^10-154*x^9+403*x^8-340*x^7+963*x^6-768*x^5+1109*x^4-788*x^3+509*x^2-470 *x+96)/(x-1)^2/(x^4-4*x^3-x^2-4*x+1)^2 The asympotics is n 23.70464430 4.419480366 (1. + n) The BZ constant is 0.3109095929 Theorem number, 3 Part I: Let a(n) be the number of spanning trees of the graph, H[n, 4], whose vertice\ s are 1, ...,n, and where every vertex i is connected to i+1,..., min(n, i + 4), Then infinity ----- \ n 13 12 11 10 9 ) a[n + 4] x = - (125 x - 859 x + 13 x + 3141 x - 3475 x / ----- n = 0 8 7 6 5 4 3 2 + 5968 x + 11312 x - 36080 x + 5597 x + 7893 x - 2435 x + 2741 x / 6 5 4 3 2 + 413 x - 864) / ((x - 3 x + 6 x - 10 x + 6 x - 3 x + 1) / 8 7 6 5 4 3 2 (x - 4 x - 17 x + 8 x + 49 x + 8 x - 17 x - 4 x + 1)) and in Maple notation -(125*x^13-859*x^12+13*x^11+3141*x^10-3475*x^9+5968*x^8+11312*x^7-36080*x^6+ 5597*x^5+7893*x^4-2435*x^3+2741*x^2+413*x-864)/(x^6-3*x^5+6*x^4-10*x^3+6*x^2-3* x+1)/(x^8-4*x^7-17*x^6+8*x^5+49*x^4+8*x^3-17*x^2-4*x+1) The asympotics is n 905.8236042 6.298096056 Part II: Let b(n) be the sum of the number of leaves in all spanning trees of the abo\ ve-mentioned graph, H[n, 4], Then infinity ----- \ n 29 28 27 26 ) b[n + 4] x = 4 (504 x - 6606 x + 19116 x + 45571 x / ----- n = 0 25 24 23 22 21 - 205452 x + 80804 x + 384164 x - 1700364 x + 2330730 x 20 19 18 17 16 + 4545539 x - 9411560 x + 5123206 x + 3844388 x - 37452912 x 15 14 13 12 11 + 20952214 x + 38660038 x - 10328316 x - 3992718 x - 866966 x 10 9 8 7 6 5 - 4448260 x + 1445936 x + 719044 x - 491640 x + 222197 x + 20834 x 4 3 2 / - 49422 x + 26808 x + 158 x - 4160 x + 625) / ( / 6 5 4 3 2 2 (x - 3 x + 6 x - 10 x + 6 x - 3 x + 1) 8 7 6 5 4 3 2 2 (x - 4 x - 17 x + 8 x + 49 x + 8 x - 17 x - 4 x + 1) ) and in Maple notation 4*(504*x^29-6606*x^28+19116*x^27+45571*x^26-205452*x^25+80804*x^24+384164*x^23-\ 1700364*x^22+2330730*x^21+4545539*x^20-9411560*x^19+5123206*x^18+3844388*x^17-\ 37452912*x^16+20952214*x^15+38660038*x^14-10328316*x^13-3992718*x^12-866966*x^ 11-4448260*x^10+1445936*x^9+719044*x^8-491640*x^7+222197*x^6+20834*x^5-49422*x^ 4+26808*x^3+158*x^2-4160*x+625)/(x^6-3*x^5+6*x^4-10*x^3+6*x^2-3*x+1)^2/(x^8-4*x ^7-17*x^6+8*x^5+49*x^4+8*x^3-17*x^2-4*x+1)^2 The asympotics is n 299.1547163 6.298096056 (1. + n) The BZ constant is 0.3302571438 Theorem number, 4 Part I: Let a(n) be the number of spanning trees of the graph, H[n, 5], whose vertice\ s are 1, ...,n, and where every vertex i is connected to i+1,..., min(n, i + 5), Then infinity ----- \ n 40 39 38 37 ) a[n + 5] x = - (1296 x - 10243 x - 7480 x + 40847 x / ----- n = 0 36 35 34 33 32 - 47840 x - 476744 x + 2999380 x + 3762793 x - 3284348 x 31 30 29 28 - 9805712 x + 103934464 x - 348087196 x - 137732716 x 27 26 25 24 - 392402436 x + 11368888 x - 508605680 x + 920371413 x 23 22 21 20 + 550565868 x + 1141918527 x + 462760993 x + 968437192 x 19 18 17 16 - 826971368 x - 433721303 x - 1117118601 x - 547373052 x 15 14 13 12 - 1006259283 x + 422208592 x + 2395384 x + 373137756 x 11 10 9 8 7 + 128981780 x + 359346932 x - 77711792 x - 6668600 x + 210244 x 6 5 4 3 2 - 3921647 x - 3568364 x + 116776 x + 105136 x - 16921 x + 8408 x / + 12005) / ((x - 1) / 8 7 6 5 4 3 2 16 15 14 (x + 3 x + 6 x - x + 15 x - x + 6 x + 3 x + 1) (x - 5 x + 10 x 13 12 11 10 9 8 7 6 - 10 x - 28 x + 10 x + 110 x + 110 x + 88 x + 110 x + 110 x 5 4 3 2 16 15 14 13 + 10 x - 28 x - 10 x + 10 x - 5 x + 1) (x - 5 x - 23 x - 10 x 12 11 10 9 8 7 6 5 - 94 x - 485 x + 242 x + 110 x + 649 x + 110 x + 242 x - 485 x 4 3 2 - 94 x - 10 x - 23 x - 5 x + 1)) and in Maple notation -(1296*x^40-10243*x^39-7480*x^38+40847*x^37-47840*x^36-476744*x^35+2999380*x^34 +3762793*x^33-3284348*x^32-9805712*x^31+103934464*x^30-348087196*x^29-137732716 *x^28-392402436*x^27+11368888*x^26-508605680*x^25+920371413*x^24+550565868*x^23 +1141918527*x^22+462760993*x^21+968437192*x^20-826971368*x^19-433721303*x^18-\ 1117118601*x^17-547373052*x^16-1006259283*x^15+422208592*x^14+2395384*x^13+ 373137756*x^12+128981780*x^11+359346932*x^10-77711792*x^9-6668600*x^8+210244*x^ 7-3921647*x^6-3568364*x^5+116776*x^4+105136*x^3-16921*x^2+8408*x+12005)/(x-1)/( x^8+3*x^7+6*x^6-x^5+15*x^4-x^3+6*x^2+3*x+1)/(x^16-5*x^15+10*x^14-10*x^13-28*x^ 12+10*x^11+110*x^10+110*x^9+88*x^8+110*x^7+110*x^6+10*x^5-28*x^4-10*x^3+10*x^2-\ 5*x+1)/(x^16-5*x^15-23*x^14-10*x^13-94*x^12-485*x^11+242*x^10+110*x^9+649*x^8+ 110*x^7+242*x^6-485*x^5-94*x^4-10*x^3-23*x^2-5*x+1) The asympotics is n 13142.15576 8.216271114 Part II: Let b(n) be the sum of the number of leaves in all spanning trees of the abo\ ve-mentioned graph, H[n, 5], Then infinity ----- \ n 84 83 82 81 ) b[n + 5] x = 2 (143360 x - 2203600 x + 6276416 x + 25900189 x / ----- n = 0 80 79 78 77 - 70009240 x - 111619746 x + 1695999840 x - 3385247259 x 76 75 74 73 - 16498298304 x + 18914834002 x + 79748467448 x - 524205415471 x 72 71 70 + 607242104696 x + 4118709032813 x - 875439843136 x 69 68 67 - 15665224872222 x + 70181249053016 x - 54637665204207 x 66 65 64 - 378247906055198 x - 364691767382275 x + 1433482893827132 x 63 62 61 - 5234831728268481 x + 5642578163846146 x + 7813726169901172 x 60 59 58 + 25202943662900324 x + 3670704043078416 x + 41818222238837082 x 57 56 55 - 27382799081841055 x - 50712133572095846 x - 159824416012358401 x 54 53 52 - 111790826123777220 x - 214894050849319232 x - 10309762425946734 x 51 50 49 + 99147162790461161 x + 425686046504419802 x + 429024029409527983 x 48 47 46 + 663953207459951670 x + 322732698025309464 x + 90562680322481744 x 45 44 - 501095575437322399 x - 665222774764728896 x 43 42 - 1091617309862733129 x - 793932577184659206 x 41 40 39 - 550553689851150376 x + 101789331270894566 x + 390831869036335985 x 38 37 36 + 899187585043989880 x + 803084277346604263 x + 700350207703180552 x 35 34 33 + 282202964895059208 x + 57790213366296082 x - 309956804166367767 x 32 31 30 - 344927900852415330 x - 355214740039952401 x - 217331642070192506 x 29 28 27 - 137637182761544224 x + 4645420764664252 x + 44094138860118025 x 26 25 24 + 61111278632610054 x + 45805331482121799 x + 35867542527806830 x 23 22 21 + 14037554275547728 x + 3744461312618100 x + 850485350911492 x 20 19 18 + 79279380279582 x - 307622411931031 x - 142247582799900 x 17 16 15 - 39898040468077 x - 12513431474762 x - 4128503903241 x 14 13 12 11 + 389487205816 x + 392482835262 x + 88511167528 x + 27260417371 x 10 9 8 7 + 17213648112 x + 1241621287 x - 291717136 x + 113336190 x 6 5 4 3 2 + 56373840 x - 20741157 x - 1701000 x + 823074 x - 212496 x / 2 - 122733 x + 19440) / ((x - 1) / 8 7 6 5 4 3 2 2 16 15 (x + 3 x + 6 x - x + 15 x - x + 6 x + 3 x + 1) (x - 5 x 14 13 12 11 10 9 8 7 + 10 x - 10 x - 28 x + 10 x + 110 x + 110 x + 88 x + 110 x 6 5 4 3 2 2 16 15 14 + 110 x + 10 x - 28 x - 10 x + 10 x - 5 x + 1) (x - 5 x - 23 x 13 12 11 10 9 8 7 6 - 10 x - 94 x - 485 x + 242 x + 110 x + 649 x + 110 x + 242 x 5 4 3 2 2 - 485 x - 94 x - 10 x - 23 x - 5 x + 1) ) and in Maple notation 2*(143360*x^84-2203600*x^83+6276416*x^82+25900189*x^81-70009240*x^80-111619746* x^79+1695999840*x^78-3385247259*x^77-16498298304*x^76+18914834002*x^75+ 79748467448*x^74-524205415471*x^73+607242104696*x^72+4118709032813*x^71-\ 875439843136*x^70-15665224872222*x^69+70181249053016*x^68-54637665204207*x^67-\ 378247906055198*x^66-364691767382275*x^65+1433482893827132*x^64-\ 5234831728268481*x^63+5642578163846146*x^62+7813726169901172*x^61+ 25202943662900324*x^60+3670704043078416*x^59+41818222238837082*x^58-\ 27382799081841055*x^57-50712133572095846*x^56-159824416012358401*x^55-\ 111790826123777220*x^54-214894050849319232*x^53-10309762425946734*x^52+ 99147162790461161*x^51+425686046504419802*x^50+429024029409527983*x^49+ 663953207459951670*x^48+322732698025309464*x^47+90562680322481744*x^46-\ 501095575437322399*x^45-665222774764728896*x^44-1091617309862733129*x^43-\ 793932577184659206*x^42-550553689851150376*x^41+101789331270894566*x^40+ 390831869036335985*x^39+899187585043989880*x^38+803084277346604263*x^37+ 700350207703180552*x^36+282202964895059208*x^35+57790213366296082*x^34-\ 309956804166367767*x^33-344927900852415330*x^32-355214740039952401*x^31-\ 217331642070192506*x^30-137637182761544224*x^29+4645420764664252*x^28+ 44094138860118025*x^27+61111278632610054*x^26+45805331482121799*x^25+ 35867542527806830*x^24+14037554275547728*x^23+3744461312618100*x^22+ 850485350911492*x^21+79279380279582*x^20-307622411931031*x^19-142247582799900*x ^18-39898040468077*x^17-12513431474762*x^16-4128503903241*x^15+389487205816*x^ 14+392482835262*x^13+88511167528*x^12+27260417371*x^11+17213648112*x^10+ 1241621287*x^9-291717136*x^8+113336190*x^7+56373840*x^6-20741157*x^5-1701000*x^ 4+823074*x^3-212496*x^2-122733*x+19440)/(x-1)^2/(x^8+3*x^7+6*x^6-x^5+15*x^4-x^3 +6*x^2+3*x+1)^2/(x^16-5*x^15+10*x^14-10*x^13-28*x^12+10*x^11+110*x^10+110*x^9+ 88*x^8+110*x^7+110*x^6+10*x^5-28*x^4-10*x^3+10*x^2-5*x+1)^2/(x^16-5*x^15-23*x^ 14-10*x^13-94*x^12-485*x^11+242*x^10+110*x^9+649*x^8+110*x^7+242*x^6-485*x^5-94 *x^4-10*x^3-23*x^2-5*x+1)^2 The asympotics is n 4470.696816 8.216271114 (1. + n) The BZ constant is 0.3401798684 -------------------------------- This took, 3309.574, seconds. [[-(-8+3*x)/(x^2-3*x+1), -2*(2*x^3-15*x^2+27*x-9)/(x^2-3*x+1)^2], [-(16*x^4-77* x^3+33*x^2-39*x+75)/(x-1)/(x^4-4*x^3-x^2-4*x+1), 2*(16*x^10-154*x^9+403*x^8-340 *x^7+963*x^6-768*x^5+1109*x^4-788*x^3+509*x^2-470*x+96)/(x-1)^2/(x^4-4*x^3-x^2-\ 4*x+1)^2], [-(125*x^13-859*x^12+13*x^11+3141*x^10-3475*x^9+5968*x^8+11312*x^7-\ 36080*x^6+5597*x^5+7893*x^4-2435*x^3+2741*x^2+413*x-864)/(x^6-3*x^5+6*x^4-10*x^ 3+6*x^2-3*x+1)/(x^8-4*x^7-17*x^6+8*x^5+49*x^4+8*x^3-17*x^2-4*x+1), 4*(504*x^29-\ 6606*x^28+19116*x^27+45571*x^26-205452*x^25+80804*x^24+384164*x^23-1700364*x^22 +2330730*x^21+4545539*x^20-9411560*x^19+5123206*x^18+3844388*x^17-37452912*x^16 +20952214*x^15+38660038*x^14-10328316*x^13-3992718*x^12-866966*x^11-4448260*x^ 10+1445936*x^9+719044*x^8-491640*x^7+222197*x^6+20834*x^5-49422*x^4+26808*x^3+ 158*x^2-4160*x+625)/(x^6-3*x^5+6*x^4-10*x^3+6*x^2-3*x+1)^2/(x^8-4*x^7-17*x^6+8* x^5+49*x^4+8*x^3-17*x^2-4*x+1)^2], [-(1296*x^40-10243*x^39-7480*x^38+40847*x^37 -47840*x^36-476744*x^35+2999380*x^34+3762793*x^33-3284348*x^32-9805712*x^31+ 103934464*x^30-348087196*x^29-137732716*x^28-392402436*x^27+11368888*x^26-\ 508605680*x^25+920371413*x^24+550565868*x^23+1141918527*x^22+462760993*x^21+ 968437192*x^20-826971368*x^19-433721303*x^18-1117118601*x^17-547373052*x^16-\ 1006259283*x^15+422208592*x^14+2395384*x^13+373137756*x^12+128981780*x^11+ 359346932*x^10-77711792*x^9-6668600*x^8+210244*x^7-3921647*x^6-3568364*x^5+ 116776*x^4+105136*x^3-16921*x^2+8408*x+12005)/(x-1)/(x^8+3*x^7+6*x^6-x^5+15*x^4 -x^3+6*x^2+3*x+1)/(x^16-5*x^15+10*x^14-10*x^13-28*x^12+10*x^11+110*x^10+110*x^9 +88*x^8+110*x^7+110*x^6+10*x^5-28*x^4-10*x^3+10*x^2-5*x+1)/(x^16-5*x^15-23*x^14 -10*x^13-94*x^12-485*x^11+242*x^10+110*x^9+649*x^8+110*x^7+242*x^6-485*x^5-94*x ^4-10*x^3-23*x^2-5*x+1), 2*(143360*x^84-2203600*x^83+6276416*x^82+25900189*x^81 -70009240*x^80-111619746*x^79+1695999840*x^78-3385247259*x^77-16498298304*x^76+ 18914834002*x^75+79748467448*x^74-524205415471*x^73+607242104696*x^72+ 4118709032813*x^71-875439843136*x^70-15665224872222*x^69+70181249053016*x^68-\ 54637665204207*x^67-378247906055198*x^66-364691767382275*x^65+1433482893827132* x^64-5234831728268481*x^63+5642578163846146*x^62+7813726169901172*x^61+ 25202943662900324*x^60+3670704043078416*x^59+41818222238837082*x^58-\ 27382799081841055*x^57-50712133572095846*x^56-159824416012358401*x^55-\ 111790826123777220*x^54-214894050849319232*x^53-10309762425946734*x^52+ 99147162790461161*x^51+425686046504419802*x^50+429024029409527983*x^49+ 663953207459951670*x^48+322732698025309464*x^47+90562680322481744*x^46-\ 501095575437322399*x^45-665222774764728896*x^44-1091617309862733129*x^43-\ 793932577184659206*x^42-550553689851150376*x^41+101789331270894566*x^40+ 390831869036335985*x^39+899187585043989880*x^38+803084277346604263*x^37+ 700350207703180552*x^36+282202964895059208*x^35+57790213366296082*x^34-\ 309956804166367767*x^33-344927900852415330*x^32-355214740039952401*x^31-\ 217331642070192506*x^30-137637182761544224*x^29+4645420764664252*x^28+ 44094138860118025*x^27+61111278632610054*x^26+45805331482121799*x^25+ 35867542527806830*x^24+14037554275547728*x^23+3744461312618100*x^22+ 850485350911492*x^21+79279380279582*x^20-307622411931031*x^19-142247582799900*x ^18-39898040468077*x^17-12513431474762*x^16-4128503903241*x^15+389487205816*x^ 14+392482835262*x^13+88511167528*x^12+27260417371*x^11+17213648112*x^10+ 1241621287*x^9-291717136*x^8+113336190*x^7+56373840*x^6-20741157*x^5-1701000*x^ 4+823074*x^3-212496*x^2-122733*x+19440)/(x-1)^2/(x^8+3*x^7+6*x^6-x^5+15*x^4-x^3 +6*x^2+3*x+1)^2/(x^16-5*x^15+10*x^14-10*x^13-28*x^12+10*x^11+110*x^10+110*x^9+ 88*x^8+110*x^7+110*x^6+10*x^5-28*x^4-10*x^3+10*x^2-5*x+1)^2/(x^16-5*x^15-23*x^ 14-10*x^13-94*x^12-485*x^11+242*x^10+110*x^9+649*x^8+110*x^7+242*x^6-485*x^5-94 *x^4-10*x^3-23*x^2-5*x+1)^2]]