This is ExpSP.txt, a Maple package by Pablo Blanco and Doron Zeilberger Accompanying their article Automatic Generation of Generating Functions for Enumerating Spanning Trees For a list of the MAIN functions, type Help(); for help with a specific func\ tion type: Help(FunctionName); For a list of the HELP functions, type Help1(); for help with a specific fun\ ction type: Help(FunctionName); For a list of the STORY functions, type HelpS(); for help with a specific fu\ nction type: Help(FunctionName); 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 1 ) a[n + 2] x = ------------ / 2 ----- x - 3 x + 1 n = 0 and in Maple notation 1/(x^2-3*x+1) The asympotics is n 1.170820391 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 ----- 2 3 2 \ n 2 (x - x + 1) (x - x - 2 x + 1) ) b[n + 2] x = ---------------------------------- / 2 2 ----- (x - 3 x + 1) n = 0 and in Maple notation 2*(x^2-x+1)*(x^3-x^2-2*x+1)/(x^2-3*x+1)^2 The asympotics is n 0.3055728110 2.618033988 (1. + n) The BZ constant is 0.2609903392 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 ----- 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) The asympotics is n 3.903524442 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 12 11 10 9 8 7 ) b[n + 3] x = 2 (16 x - 136 x + 226 x + 188 x + 408 x + 6 x / ----- n = 0 6 5 4 3 2 / 2 - 4 x - 116 x + 8 x - 20 x + 9 x - 12 x + 3) / ((x - 1) / 4 3 2 2 (x - 4 x - x - 4 x + 1) ) and in Maple notation 2*(16*x^12-136*x^11+226*x^10+188*x^9+408*x^8+6*x^7-4*x^6-116*x^5+8*x^4-20*x^3+9 *x^2-12*x+3)/(x-1)^2/(x^4-4*x^3-x^2-4*x+1)^2 The asympotics is n 1.213643195 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 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) The asympotics is n 22.83626495 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 31 30 29 28 ) b[n + 4] x = 4 (504 x - 6606 x + 19196 x + 44460 x / ----- n = 0 27 26 25 24 23 - 201498 x + 84143 x + 351608 x - 1657023 x + 2336262 x 22 21 20 19 18 + 4287806 x - 8792798 x + 5140399 x + 2388044 x - 35046126 x 17 16 15 14 13 + 19068370 x + 34702300 x - 1722540 x - 6690852 x - 3457670 x 12 11 10 9 8 7 - 2122798 x + 284972 x + 500230 x + 149856 x + 37310 x - 7924 x 6 5 4 3 2 / - 2355 x - 780 x - 661 x + 244 x - 36 x - 46 x + 9) / ( / 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^31-6606*x^30+19196*x^29+44460*x^28-201498*x^27+84143*x^26+351608*x^25-\ 1657023*x^24+2336262*x^23+4287806*x^22-8792798*x^21+5140399*x^20+2388044*x^19-\ 35046126*x^18+19068370*x^17+34702300*x^16-1722540*x^15-6690852*x^14-3457670*x^ 13-2122798*x^12+284972*x^11+500230*x^10+149856*x^9+37310*x^8-7924*x^7-2355*x^6-\ 780*x^5-661*x^4+244*x^3-36*x^2-46*x+9)/(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 7.541839639 6.298096056 (1. + n) The BZ constant is 0.3302571439 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 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) The asympotics is n 194.6780947 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 86 85 84 83 ) b[n + 5] x = 2 (143360 x - 2203600 x + 6276416 x + 25902064 x / ----- n = 0 82 81 80 79 - 70039080 x - 111521056 x + 1696278480 x - 3386287344 x 78 77 76 75 - 16499154024 x + 18937167472 x + 79691968808 x - 524385877291 x 74 73 72 + 607569835616 x + 4119530235723 x - 882640752656 x 71 70 69 - 15653133286077 x + 70226979735896 x - 54669878333577 x 68 67 66 - 378418899276968 x - 363684761907370 x + 1432167041739272 x 65 64 63 - 5238843948377301 x + 5639597057601656 x + 7831982707230972 x 62 61 60 + 25121900473068104 x + 3792575312687676 x + 41834924220950082 x 59 58 57 - 27040053917118400 x - 50767183912378706 x - 159054492728655991 x 56 55 54 - 112348462748654610 x - 214877248538577097 x - 12124661340540994 x 53 52 51 + 98667414484378016 x + 422617297864428812 x + 429581435751763033 x 50 49 48 + 663310680535369590 x + 326700104986085079 x + 92419411001545184 x 47 46 - 494211077506361824 x - 664305712170258496 x 45 44 - 1088869155963439519 x - 798332602163134056 x 43 42 41 - 552714440812185361 x + 92795270593104026 x + 388311749348678600 x 40 39 38 + 894404876631305590 x + 805408097880211153 x + 700922839353846952 x 37 36 35 + 288987418917055943 x + 59879665518936482 x - 305799511003887192 x 34 33 32 - 345296399099581890 x - 354458606642639911 x - 220303001671463336 x 31 30 29 - 138221054216811049 x + 2796865279169512 x + 44008803494274880 x 28 27 26 + 60493305615499544 x + 46529200889345809 x + 35849599767910690 x 25 24 23 + 14372623101593263 x + 3779368066207740 x + 979893349892272 x 22 21 20 + 7660315070082 x - 296190102744271 x - 143319349080870 x 19 18 17 - 44016580835777 x - 14248597185502 x - 3226892493936 x 16 15 14 13 + 308721824206 x + 342130808292 x + 130083152008 x + 43782034876 x 12 11 10 9 + 11029900992 x + 1413335557 x + 118568344 x - 32897150 x 8 7 6 5 4 3 - 17010240 x - 3326727 x - 554640 x - 305331 x - 33216 x + 1557 x 2 / 2 - 1920 x - 685 x + 160) / ((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^86-2203600*x^85+6276416*x^84+25902064*x^83-70039080*x^82-111521056* x^81+1696278480*x^80-3386287344*x^79-16499154024*x^78+18937167472*x^77+ 79691968808*x^76-524385877291*x^75+607569835616*x^74+4119530235723*x^73-\ 882640752656*x^72-15653133286077*x^71+70226979735896*x^70-54669878333577*x^69-\ 378418899276968*x^68-363684761907370*x^67+1432167041739272*x^66-\ 5238843948377301*x^65+5639597057601656*x^64+7831982707230972*x^63+ 25121900473068104*x^62+3792575312687676*x^61+41834924220950082*x^60-\ 27040053917118400*x^59-50767183912378706*x^58-159054492728655991*x^57-\ 112348462748654610*x^56-214877248538577097*x^55-12124661340540994*x^54+ 98667414484378016*x^53+422617297864428812*x^52+429581435751763033*x^51+ 663310680535369590*x^50+326700104986085079*x^49+92419411001545184*x^48-\ 494211077506361824*x^47-664305712170258496*x^46-1088869155963439519*x^45-\ 798332602163134056*x^44-552714440812185361*x^43+92795270593104026*x^42+ 388311749348678600*x^41+894404876631305590*x^40+805408097880211153*x^39+ 700922839353846952*x^38+288987418917055943*x^37+59879665518936482*x^36-\ 305799511003887192*x^35-345296399099581890*x^34-354458606642639911*x^33-\ 220303001671463336*x^32-138221054216811049*x^31+2796865279169512*x^30+ 44008803494274880*x^29+60493305615499544*x^28+46529200889345809*x^27+ 35849599767910690*x^26+14372623101593263*x^25+3779368066207740*x^24+ 979893349892272*x^23+7660315070082*x^22-296190102744271*x^21-143319349080870*x^ 20-44016580835777*x^19-14248597185502*x^18-3226892493936*x^17+308721824206*x^16 +342130808292*x^15+130083152008*x^14+43782034876*x^13+11029900992*x^12+ 1413335557*x^11+118568344*x^10-32897150*x^9-17010240*x^8-3326727*x^7-554640*x^6 -305331*x^5-33216*x^4+1557*x^3-1920*x^2-685*x+160)/(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 66.22556869 8.216271114 (1. + n) The BZ constant is 0.3401798687 -------------------------------- This took, 3144.099, seconds. [[1/(x^2-3*x+1), 2*(x^2-x+1)*(x^3-x^2-2*x+1)/(x^2-3*x+1)^2], [-(4*x^2+x+3)/(x-1 )/(x^4-4*x^3-x^2-4*x+1), 2*(16*x^12-136*x^11+226*x^10+188*x^9+408*x^8+6*x^7-4*x ^6-116*x^5+8*x^4-20*x^3+9*x^2-12*x+3)/(x-1)^2/(x^4-4*x^3-x^2-4*x+1)^2], [(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) , 4*(504*x^31-6606*x^30+19196*x^29+44460*x^28-201498*x^27+84143*x^26+351608*x^ 25-1657023*x^24+2336262*x^23+4287806*x^22-8792798*x^21+5140399*x^20+2388044*x^ 19-35046126*x^18+19068370*x^17+34702300*x^16-1722540*x^15-6690852*x^14-3457670* x^13-2122798*x^12+284972*x^11+500230*x^10+149856*x^9+37310*x^8-7924*x^7-2355*x^ 6-780*x^5-661*x^4+244*x^3-36*x^2-46*x+9)/(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], [-(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), 2*(143360*x^86-2203600*x^85+6276416*x^84+25902064*x^83-70039080*x^82-\ 111521056*x^81+1696278480*x^80-3386287344*x^79-16499154024*x^78+18937167472*x^ 77+79691968808*x^76-524385877291*x^75+607569835616*x^74+4119530235723*x^73-\ 882640752656*x^72-15653133286077*x^71+70226979735896*x^70-54669878333577*x^69-\ 378418899276968*x^68-363684761907370*x^67+1432167041739272*x^66-\ 5238843948377301*x^65+5639597057601656*x^64+7831982707230972*x^63+ 25121900473068104*x^62+3792575312687676*x^61+41834924220950082*x^60-\ 27040053917118400*x^59-50767183912378706*x^58-159054492728655991*x^57-\ 112348462748654610*x^56-214877248538577097*x^55-12124661340540994*x^54+ 98667414484378016*x^53+422617297864428812*x^52+429581435751763033*x^51+ 663310680535369590*x^50+326700104986085079*x^49+92419411001545184*x^48-\ 494211077506361824*x^47-664305712170258496*x^46-1088869155963439519*x^45-\ 798332602163134056*x^44-552714440812185361*x^43+92795270593104026*x^42+ 388311749348678600*x^41+894404876631305590*x^40+805408097880211153*x^39+ 700922839353846952*x^38+288987418917055943*x^37+59879665518936482*x^36-\ 305799511003887192*x^35-345296399099581890*x^34-354458606642639911*x^33-\ 220303001671463336*x^32-138221054216811049*x^31+2796865279169512*x^30+ 44008803494274880*x^29+60493305615499544*x^28+46529200889345809*x^27+ 35849599767910690*x^26+14372623101593263*x^25+3779368066207740*x^24+ 979893349892272*x^23+7660315070082*x^22-296190102744271*x^21-143319349080870*x^ 20-44016580835777*x^19-14248597185502*x^18-3226892493936*x^17+308721824206*x^16 +342130808292*x^15+130083152008*x^14+43782034876*x^13+11029900992*x^12+ 1413335557*x^11+118568344*x^10-32897150*x^9-17010240*x^8-3326727*x^7-554640*x^6 -305331*x^5-33216*x^4+1557*x^3-1920*x^2-685*x+160)/(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]]