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, 4 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.213643208 4.419480366 (1. + n) The BZ constant is 0.3109095962 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.83626496 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.541839700 6.298096056 (1. + n) The BZ constant is 0.3302571464 -------------------------------- This took, 138.293, 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]]