Generating Functions for Enumerating the Number of Spanning Trees in Friends\ hip graphs where n people live in a one-sided STRAIGHT street, and every\ one is friends with all the neighbors distance at most r for r from 2 to, 6 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 1 ) a[n + 2] x = ------------ / 2 ----- x - 3 x + 1 n = 0 and in Maple notation 1/(x^2-3*x+1) 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 ----- 2 \ n 4 x + x + 3 ) a[n + 3] x = - ---------------------------------- / 4 3 2 ----- (x - 1) (x - 4 x - x - 4 x + 1) n = 0 and in Maple notation -(4*x^2+x+3)/(x-1)/(x^4-4*x^3-x^2-4*x+1) 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 10 9 8 7 6 5 ) a[n + 4] x = (36 x + 20 x - 76 x + 103 x - 49 x - 608 x / ----- n = 0 4 3 2 / - 112 x + 112 x + 5 x + 13 x + 16) / ( / 6 5 4 3 2 (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 (36*x^10+20*x^9-76*x^8+103*x^7-49*x^6-608*x^5-112*x^4+112*x^3+5*x^2+13*x+16)/(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) 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 36 35 34 33 32 ) a[n + 5] x = - (576 x + 1072 x + 880 x + 9397 x + 37352 x / ----- n = 0 31 30 29 28 27 - 38820 x - 162696 x - 409945 x - 940188 x - 6830079 x 26 25 24 23 22 - 10208568 x - 12657852 x - 11172468 x - 10598248 x + 2897948 x 21 20 19 18 17 + 13501001 x + 22499688 x + 26110019 x + 28239293 x + 18386448 x 16 15 14 13 12 + 10158616 x + 2700085 x - 4176485 x - 10893240 x - 8747319 x 11 10 9 8 7 - 7446180 x - 6025584 x - 4322484 x - 802676 x - 189560 x 6 5 4 3 2 / - 61343 x + 7796 x + 19551 x + 5928 x + 1012 x + 296 x + 125) / ( / 8 7 6 5 4 3 2 16 15 (x - 1) (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 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 - 485 x - 94 x - 10 x - 23 x - 5 x + 1)) and in Maple notation -(576*x^36+1072*x^35+880*x^34+9397*x^33+37352*x^32-38820*x^31-162696*x^30-\ 409945*x^29-940188*x^28-6830079*x^27-10208568*x^26-12657852*x^25-11172468*x^24-\ 10598248*x^23+2897948*x^22+13501001*x^21+22499688*x^20+26110019*x^19+28239293*x ^18+18386448*x^17+10158616*x^16+2700085*x^15-4176485*x^14-10893240*x^13-8747319 *x^12-7446180*x^11-6025584*x^10-4322484*x^9-802676*x^8-189560*x^7-61343*x^6+ 7796*x^5+19551*x^4+5928*x^3+1012*x^2+296*x+125)/(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) 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 116 115 114 113 ) a[n + 6] x = (14400 x + 59760 x + 66240 x - 748800 x / ----- n = 0 112 111 110 109 - 620544 x + 12588927 x - 12798264 x - 381841562 x 108 107 106 105 - 1888064264 x - 675729293 x + 8674941728 x - 18742616109 x 104 103 102 - 117719462592 x + 109263556630 x + 4265513291928 x 101 100 99 + 14003902587039 x + 7129660372120 x - 50659542151793 x 98 97 96 - 118027242336848 x - 35098607999179 x + 62155880570696 x 95 94 93 - 396171893375959 x - 757721160016224 x + 1670726907353982 x 92 91 90 + 6644506079115144 x + 4509151672125081 x - 7837665439922586 x 89 88 87 - 8080633857774675 x + 8606110250697164 x - 19694292755409610 x 86 85 84 - 117440711410653154 x - 81115358730677739 x + 194275687728055574 x 83 82 81 + 263728355357194160 x - 42137022534038916 x + 341225962802591012 x 80 79 + 1745896709921539574 x + 564825313416315180 x 78 77 - 4433458888285529162 x - 4434542836005399224 x 76 75 + 4202051701823712434 x + 1076562332826040236 x 74 73 - 27158900967217897878 x - 26937296749595424044 x 72 71 + 46143099651776390588 x + 88657609557096762944 x 70 69 - 16249272147124872926 x - 96077137105072258804 x 68 67 + 151371272785473988682 x + 420007255106531395204 x 66 65 + 30924945217815762740 x - 734849723986948940464 x 64 63 - 659266819325943150862 x + 293693316042542945316 x 62 61 + 157355102719396855272 x - 1374863082067291153428 x 60 59 - 1487832331576960630128 x + 1307297695342976615928 x 58 57 + 3880380757072122278856 x + 2424944883519321130380 x 56 55 - 701758373180199298848 x - 1635229545829989386484 x 54 53 - 551569170844502046792 x - 12296128897771745448 x 52 51 - 540244040514494150400 x - 633540857504485658484 x 50 49 - 10116446364668491800 x + 414516151199304017988 x 48 47 + 270496183271493828402 x + 22109946652766806800 x 46 45 - 7534670542004570380 x + 31928781688073370212 x 44 43 + 6286374251833224362 x - 33620798191274141204 x 42 41 - 28377915386555999934 x - 4346212792719578880 x 40 39 + 3646747451914642364 x + 1112984785955588244 x 38 37 + 478253673530057898 x + 1669843738163497388 x 36 35 34 + 1208210237395999250 x - 10565686867287448 x - 316865495515521866 x 33 32 31 - 92220274673131124 x - 13698815149329098 x - 64567643807311212 x 30 29 28 - 44932884588947748 x + 10268739391006320 x + 20618222345329254 x 27 26 25 + 4804545858786045 x - 2291910693428754 x + 323494630379278 x 24 23 22 + 1601973055537132 x + 283666209746557 x - 477368731796970 x 21 20 19 - 258196106460815 x + 14979860998024 x + 27813727983798 x 18 17 16 - 15835842886640 x - 14217324434039 x - 388226879496 x 15 14 13 + 3442608134573 x + 1459946701856 x + 176146382887 x 12 11 10 9 - 14309795400 x - 10060233249 x - 1192483144 x - 868988978 x 8 7 6 5 4 - 466902464 x - 99754837 x - 4721936 x + 2860483 x + 634808 x 3 2 / + 77566 x + 24568 x + 6439 x + 1296) / (( / 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 (14400*x^116+59760*x^115+66240*x^114-748800*x^113-620544*x^112+12588927*x^111-\ 12798264*x^110-381841562*x^109-1888064264*x^108-675729293*x^107+8674941728*x^ 106-18742616109*x^105-117719462592*x^104+109263556630*x^103+4265513291928*x^102 +14003902587039*x^101+7129660372120*x^100-50659542151793*x^99-118027242336848*x ^98-35098607999179*x^97+62155880570696*x^96-396171893375959*x^95-\ 757721160016224*x^94+1670726907353982*x^93+6644506079115144*x^92+ 4509151672125081*x^91-7837665439922586*x^90-8080633857774675*x^89+ 8606110250697164*x^88-19694292755409610*x^87-117440711410653154*x^86-\ 81115358730677739*x^85+194275687728055574*x^84+263728355357194160*x^83-\ 42137022534038916*x^82+341225962802591012*x^81+1745896709921539574*x^80+ 564825313416315180*x^79-4433458888285529162*x^78-4434542836005399224*x^77+ 4202051701823712434*x^76+1076562332826040236*x^75-27158900967217897878*x^74-\ 26937296749595424044*x^73+46143099651776390588*x^72+88657609557096762944*x^71-\ 16249272147124872926*x^70-96077137105072258804*x^69+151371272785473988682*x^68+ 420007255106531395204*x^67+30924945217815762740*x^66-734849723986948940464*x^65 -659266819325943150862*x^64+293693316042542945316*x^63+157355102719396855272*x^ 62-1374863082067291153428*x^61-1487832331576960630128*x^60+ 1307297695342976615928*x^59+3880380757072122278856*x^58+2424944883519321130380* x^57-701758373180199298848*x^56-1635229545829989386484*x^55-\ 551569170844502046792*x^54-12296128897771745448*x^53-540244040514494150400*x^52 -633540857504485658484*x^51-10116446364668491800*x^50+414516151199304017988*x^ 49+270496183271493828402*x^48+22109946652766806800*x^47-7534670542004570380*x^ 46+31928781688073370212*x^45+6286374251833224362*x^44-33620798191274141204*x^43 -28377915386555999934*x^42-4346212792719578880*x^41+3646747451914642364*x^40+ 1112984785955588244*x^39+478253673530057898*x^38+1669843738163497388*x^37+ 1208210237395999250*x^36-10565686867287448*x^35-316865495515521866*x^34-\ 92220274673131124*x^33-13698815149329098*x^32-64567643807311212*x^31-\ 44932884588947748*x^30+10268739391006320*x^29+20618222345329254*x^28+ 4804545858786045*x^27-2291910693428754*x^26+323494630379278*x^25+ 1601973055537132*x^24+283666209746557*x^23-477368731796970*x^22-258196106460815 *x^21+14979860998024*x^20+27813727983798*x^19-15835842886640*x^18-\ 14217324434039*x^17-388226879496*x^16+3442608134573*x^15+1459946701856*x^14+ 176146382887*x^13-14309795400*x^12-10060233249*x^11-1192483144*x^10-868988978*x ^9-466902464*x^8-99754837*x^7-4721936*x^6+2860483*x^5+634808*x^4+77566*x^3+ 24568*x^2+6439*x+1296)/(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) -------------------------------- This took, 2132.030, seconds. [1/(x^2-3*x+1), -(4*x^2+x+3)/(x-1)/(x^4-4*x^3-x^2-4*x+1), (36*x^10+20*x^9-76*x^ 8+103*x^7-49*x^6-608*x^5-112*x^4+112*x^3+5*x^2+13*x+16)/(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), -(576*x^36+ 1072*x^35+880*x^34+9397*x^33+37352*x^32-38820*x^31-162696*x^30-409945*x^29-\ 940188*x^28-6830079*x^27-10208568*x^26-12657852*x^25-11172468*x^24-10598248*x^ 23+2897948*x^22+13501001*x^21+22499688*x^20+26110019*x^19+28239293*x^18+ 18386448*x^17+10158616*x^16+2700085*x^15-4176485*x^14-10893240*x^13-8747319*x^ 12-7446180*x^11-6025584*x^10-4322484*x^9-802676*x^8-189560*x^7-61343*x^6+7796*x ^5+19551*x^4+5928*x^3+1012*x^2+296*x+125)/(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), (14400*x^116+59760*x^115+66240*x^114-748800*x^113-620544* x^112+12588927*x^111-12798264*x^110-381841562*x^109-1888064264*x^108-675729293* x^107+8674941728*x^106-18742616109*x^105-117719462592*x^104+109263556630*x^103+ 4265513291928*x^102+14003902587039*x^101+7129660372120*x^100-50659542151793*x^ 99-118027242336848*x^98-35098607999179*x^97+62155880570696*x^96-396171893375959 *x^95-757721160016224*x^94+1670726907353982*x^93+6644506079115144*x^92+ 4509151672125081*x^91-7837665439922586*x^90-8080633857774675*x^89+ 8606110250697164*x^88-19694292755409610*x^87-117440711410653154*x^86-\ 81115358730677739*x^85+194275687728055574*x^84+263728355357194160*x^83-\ 42137022534038916*x^82+341225962802591012*x^81+1745896709921539574*x^80+ 564825313416315180*x^79-4433458888285529162*x^78-4434542836005399224*x^77+ 4202051701823712434*x^76+1076562332826040236*x^75-27158900967217897878*x^74-\ 26937296749595424044*x^73+46143099651776390588*x^72+88657609557096762944*x^71-\ 16249272147124872926*x^70-96077137105072258804*x^69+151371272785473988682*x^68+ 420007255106531395204*x^67+30924945217815762740*x^66-734849723986948940464*x^65 -659266819325943150862*x^64+293693316042542945316*x^63+157355102719396855272*x^ 62-1374863082067291153428*x^61-1487832331576960630128*x^60+ 1307297695342976615928*x^59+3880380757072122278856*x^58+2424944883519321130380* x^57-701758373180199298848*x^56-1635229545829989386484*x^55-\ 551569170844502046792*x^54-12296128897771745448*x^53-540244040514494150400*x^52 -633540857504485658484*x^51-10116446364668491800*x^50+414516151199304017988*x^ 49+270496183271493828402*x^48+22109946652766806800*x^47-7534670542004570380*x^ 46+31928781688073370212*x^45+6286374251833224362*x^44-33620798191274141204*x^43 -28377915386555999934*x^42-4346212792719578880*x^41+3646747451914642364*x^40+ 1112984785955588244*x^39+478253673530057898*x^38+1669843738163497388*x^37+ 1208210237395999250*x^36-10565686867287448*x^35-316865495515521866*x^34-\ 92220274673131124*x^33-13698815149329098*x^32-64567643807311212*x^31-\ 44932884588947748*x^30+10268739391006320*x^29+20618222345329254*x^28+ 4804545858786045*x^27-2291910693428754*x^26+323494630379278*x^25+ 1601973055537132*x^24+283666209746557*x^23-477368731796970*x^22-258196106460815 *x^21+14979860998024*x^20+27813727983798*x^19-15835842886640*x^18-\ 14217324434039*x^17-388226879496*x^16+3442608134573*x^15+1459946701856*x^14+ 176146382887*x^13-14309795400*x^12-10060233249*x^11-1192483144*x^10-868988978*x ^9-466902464*x^8-99754837*x^7-4721936*x^6+2860483*x^5+634808*x^4+77566*x^3+ 24568*x^2+6439*x+1296)/(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)]