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 for r from 2 to, 7 By Shalosh B. Ekhad Theorem number, 1 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.0249223594996214535 2.6180339887498948482 Theorem number, 2 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.242884833004184436 4.4194803657875667075 Theorem number, 3 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.82360371065415222 6.2980960562257735737 Theorem number, 4 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.155764403277999 8.2162711147018080782 Theorem number, 5 Let a(n) be the number of spanning trees of the graph, H[n, 6], whose vertice\ s are 1, ...,n, and where every vertex i is connected to i+1,..., min(n, i + 6), Then infinity ----- \ n 121 120 119 118 ) a[n + 6] x = - (16807 x - 133160 x - 497771 x - 306496 x / ----- n = 0 117 116 115 114 + 13828232 x + 20967392 x - 164300205 x + 438163392 x 113 112 111 + 4125521505 x + 11273139496 x - 82044531920 x 110 109 108 - 295068407216 x + 495635957336 x + 160196877704 x 107 106 105 - 2411512386593 x - 43421374003528 x + 107334345783845 x 104 103 102 + 597019418773720 x + 265492722202168 x - 2194160082123392 x 101 100 99 - 4488591968880429 x + 3479724455941742 x + 6142036472775137 x 98 97 96 - 29686082945326574 x - 40423414178207824 x + 117832590845994128 x 95 94 93 + 356431745622523288 x - 15163019081424994 x - 658011506597768737 x 92 91 + 98401089985808362 x + 1115715105041685509 x 90 89 - 2524296687796993192 x - 9618110300163523192 x 88 87 + 164326947024182808 x + 21441859209258459363 x 86 85 + 11080153225625153998 x - 15023358237271529431 x 84 83 + 41470796471858530586 x + 148432420762171130104 x 82 81 - 84535788787541270832 x - 493145454902135406264 x 80 79 - 225321073910392038634 x + 453346053554953510576 x 78 77 - 269194328117186031830 x - 1957242869054038743096 x 76 75 + 1451510672930443137672 x + 7745599445749905384336 x 74 73 + 4010779308881514144200 x - 8992476901330927679032 x 72 71 - 6718882098257836870714 x + 16444240366574834147680 x 70 69 - 943368028429656594518 x - 58922495017054944980744 x 68 67 - 50350067726289682311328 x + 62820381329062499821208 x 66 65 + 112066042289296305724982 x - 36007910375151167551488 x 64 63 - 71828326704535986623382 x + 133275660601249951559976 x 62 61 + 225014802050712366492456 x - 96142741845600933182448 x 60 59 - 445632418088349792496728 x - 144637924631844296721432 x 58 57 + 206554408598588688983498 x + 152989898616337443846848 x 56 55 - 61669575461066518143850 x - 51547664854116416004584 x 54 53 + 104428790878703983432096 x + 76153680143046334495672 x 52 51 - 40181803249470807135222 x - 62186933262854690293728 x 50 49 - 6182444038657425305562 x + 17346431203612052339528 x 48 47 - 4720391933398617561016 x - 10135374142557666224944 x 46 45 + 2443335319987170051976 x + 7860274939700825627656 x 44 43 + 2191123853910133325066 x - 1842119332834047654992 x 42 41 - 458912314560178194314 x + 478392131071376704520 x 40 39 - 123445272857866657648 x - 495660305008719519688 x 38 37 - 136613070563015473926 x + 136589533929388859545 x 36 35 + 53277577259704218286 x - 14158353326251597357 x 34 33 + 7016902293757072408 x + 22104327853580900200 x 32 31 + 2846717254850954840 x - 9252630134157635147 x 30 29 - 3315069373541286710 x + 969814280185360271 x 28 27 26 + 278379051606900094 x - 654023053441686440 x - 113005020302629808 x 25 24 23 + 339059924918273136 x + 149712873127661682 x - 29170246647865135 x 22 21 20 - 34674751936601522 x + 3254626423149763 x + 4746321548403968 x 19 18 17 - 3765447604445160 x - 2559191264588712 x + 21769962443221 x 16 15 14 + 621301937825336 x + 170264231057807 x - 34314672475128 x 13 12 11 - 9197777678952 x - 1526396856240 x + 351034672816 x 10 9 8 7 - 234431191640 x - 95090125103 x + 5758516928 x + 5804756867 x 6 5 4 3 2 + 1233312992 x - 31305560 x + 11833792 x + 12522949 x + 164184 x / - 585705 x - 196608) / (( / 10 9 8 7 6 5 4 3 2 x - 3 x + 6 x - 10 x + 15 x - 21 x + 15 x - 10 x + 6 x - 3 x + 1) 32 31 30 29 28 27 26 25 (x - 7 x - 24 x - 175 x + 769 x + 1176 x + 9192 x - 29575 x 24 23 22 21 20 19 - 2951 x - 82992 x + 270049 x - 44863 x + 304200 x - 1090152 x 18 17 16 15 14 + 314664 x - 551040 x + 1924560 x - 551040 x + 314664 x 13 12 11 10 9 8 - 1090152 x + 304200 x - 44863 x + 270049 x - 82992 x - 2951 x 7 6 5 4 3 2 80 - 29575 x + 9192 x + 1176 x + 769 x - 175 x - 24 x - 7 x + 1) (x 79 78 77 76 75 74 73 + 2 x - 12 x + 13 x + 65 x - 468 x - 5603 x - 22217 x 72 71 70 69 68 + 30004 x + 44759 x - 559689 x + 1135576 x + 12501788 x 67 66 65 64 + 29182575 x + 37645945 x + 64477328 x + 147147182 x 63 62 61 60 + 92682629 x - 486054621 x - 1369782986 x - 1969166251 x 59 58 57 56 - 3420650974 x - 6743555416 x - 5579044705 x + 7658727791 x 55 54 53 52 + 22254594037 x + 31167243252 x + 68146698975 x + 132669882295 x 51 50 49 48 + 103542245144 x - 69649255156 x - 157781384995 x - 142490742901 x 47 46 45 - 568788151789 x - 1259845890563 x - 830727715350 x 44 43 42 + 463211579532 x + 295731832474 x - 254334041065 x 41 40 39 + 2133496643207 x + 4315877516198 x + 2133496643207 x 38 37 36 - 254334041065 x + 295731832474 x + 463211579532 x 35 34 33 - 830727715350 x - 1259845890563 x - 568788151789 x 32 31 30 29 - 142490742901 x - 157781384995 x - 69649255156 x + 103542245144 x 28 27 26 25 + 132669882295 x + 68146698975 x + 31167243252 x + 22254594037 x 24 23 22 21 + 7658727791 x - 5579044705 x - 6743555416 x - 3420650974 x 20 19 18 17 - 1969166251 x - 1369782986 x - 486054621 x + 92682629 x 16 15 14 13 + 147147182 x + 64477328 x + 37645945 x + 29182575 x 12 11 10 9 8 7 + 12501788 x + 1135576 x - 559689 x + 44759 x + 30004 x - 22217 x 6 5 4 3 2 - 5603 x - 468 x + 65 x + 13 x - 12 x + 2 x + 1)) and in Maple notation -(16807*x^121-133160*x^120-497771*x^119-306496*x^118+13828232*x^117+20967392*x^ 116-164300205*x^115+438163392*x^114+4125521505*x^113+11273139496*x^112-\ 82044531920*x^111-295068407216*x^110+495635957336*x^109+160196877704*x^108-\ 2411512386593*x^107-43421374003528*x^106+107334345783845*x^105+597019418773720* x^104+265492722202168*x^103-2194160082123392*x^102-4488591968880429*x^101+ 3479724455941742*x^100+6142036472775137*x^99-29686082945326574*x^98-\ 40423414178207824*x^97+117832590845994128*x^96+356431745622523288*x^95-\ 15163019081424994*x^94-658011506597768737*x^93+98401089985808362*x^92+ 1115715105041685509*x^91-2524296687796993192*x^90-9618110300163523192*x^89+ 164326947024182808*x^88+21441859209258459363*x^87+11080153225625153998*x^86-\ 15023358237271529431*x^85+41470796471858530586*x^84+148432420762171130104*x^83-\ 84535788787541270832*x^82-493145454902135406264*x^81-225321073910392038634*x^80 +453346053554953510576*x^79-269194328117186031830*x^78-1957242869054038743096*x ^77+1451510672930443137672*x^76+7745599445749905384336*x^75+ 4010779308881514144200*x^74-8992476901330927679032*x^73-6718882098257836870714* x^72+16444240366574834147680*x^71-943368028429656594518*x^70-\ 58922495017054944980744*x^69-50350067726289682311328*x^68+ 62820381329062499821208*x^67+112066042289296305724982*x^66-\ 36007910375151167551488*x^65-71828326704535986623382*x^64+ 133275660601249951559976*x^63+225014802050712366492456*x^62-\ 96142741845600933182448*x^61-445632418088349792496728*x^60-\ 144637924631844296721432*x^59+206554408598588688983498*x^58+ 152989898616337443846848*x^57-61669575461066518143850*x^56-\ 51547664854116416004584*x^55+104428790878703983432096*x^54+ 76153680143046334495672*x^53-40181803249470807135222*x^52-\ 62186933262854690293728*x^51-6182444038657425305562*x^50+ 17346431203612052339528*x^49-4720391933398617561016*x^48-\ 10135374142557666224944*x^47+2443335319987170051976*x^46+7860274939700825627656 *x^45+2191123853910133325066*x^44-1842119332834047654992*x^43-\ 458912314560178194314*x^42+478392131071376704520*x^41-123445272857866657648*x^ 40-495660305008719519688*x^39-136613070563015473926*x^38+136589533929388859545* x^37+53277577259704218286*x^36-14158353326251597357*x^35+7016902293757072408*x^ 34+22104327853580900200*x^33+2846717254850954840*x^32-9252630134157635147*x^31-\ 3315069373541286710*x^30+969814280185360271*x^29+278379051606900094*x^28-\ 654023053441686440*x^27-113005020302629808*x^26+339059924918273136*x^25+ 149712873127661682*x^24-29170246647865135*x^23-34674751936601522*x^22+ 3254626423149763*x^21+4746321548403968*x^20-3765447604445160*x^19-\ 2559191264588712*x^18+21769962443221*x^17+621301937825336*x^16+170264231057807* x^15-34314672475128*x^14-9197777678952*x^13-1526396856240*x^12+351034672816*x^ 11-234431191640*x^10-95090125103*x^9+5758516928*x^8+5804756867*x^7+1233312992*x ^6-31305560*x^5+11833792*x^4+12522949*x^3+164184*x^2-585705*x-196608)/(x^10-3*x ^9+6*x^8-10*x^7+15*x^6-21*x^5+15*x^4-10*x^3+6*x^2-3*x+1)/(x^32-7*x^31-24*x^30-\ 175*x^29+769*x^28+1176*x^27+9192*x^26-29575*x^25-2951*x^24-82992*x^23+270049*x^ 22-44863*x^21+304200*x^20-1090152*x^19+314664*x^18-551040*x^17+1924560*x^16-\ 551040*x^15+314664*x^14-1090152*x^13+304200*x^12-44863*x^11+270049*x^10-82992*x ^9-2951*x^8-29575*x^7+9192*x^6+1176*x^5+769*x^4-175*x^3-24*x^2-7*x+1)/(x^80+2*x ^79-12*x^78+13*x^77+65*x^76-468*x^75-5603*x^74-22217*x^73+30004*x^72+44759*x^71 -559689*x^70+1135576*x^69+12501788*x^68+29182575*x^67+37645945*x^66+64477328*x^ 65+147147182*x^64+92682629*x^63-486054621*x^62-1369782986*x^61-1969166251*x^60-\ 3420650974*x^59-6743555416*x^58-5579044705*x^57+7658727791*x^56+22254594037*x^ 55+31167243252*x^54+68146698975*x^53+132669882295*x^52+103542245144*x^51-\ 69649255156*x^50-157781384995*x^49-142490742901*x^48-568788151789*x^47-\ 1259845890563*x^46-830727715350*x^45+463211579532*x^44+295731832474*x^43-\ 254334041065*x^42+2133496643207*x^41+4315877516198*x^40+2133496643207*x^39-\ 254334041065*x^38+295731832474*x^37+463211579532*x^36-830727715350*x^35-\ 1259845890563*x^34-568788151789*x^33-142490742901*x^32-157781384995*x^31-\ 69649255156*x^30+103542245144*x^29+132669882295*x^28+68146698975*x^27+ 31167243252*x^26+22254594037*x^25+7658727791*x^24-5579044705*x^23-6743555416*x^ 22-3420650974*x^21-1969166251*x^20-1369782986*x^19-486054621*x^18+92682629*x^17 +147147182*x^16+64477328*x^15+37645945*x^14+29182575*x^13+12501788*x^12+1135576 *x^11-559689*x^10+44759*x^9+30004*x^8-22217*x^7-5603*x^6-468*x^5+65*x^4+13*x^3-\ 12*x^2+2*x+1)