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 in Grid G\ raphs with dimensions s by r, for fixed dimension r, as well as their asymptotics for r from 2 to 6 By Shalosh B. Ekhad Theorem number, 1 Let a(n) be the number of spanning trees of the grid graph with a fixed dime\ nsion 2 (counted by vertices). Then infinity ----- \ n -4 + x ) a[n + 2] x = - ------------ / 2 ----- x - 4 x + 1 n = 0 and in Maple notation -(-4+x)/(x^2-4*x+1) The asymptotics is n 4.0207259421636901758 3.7320508075688772935 Theorem number, 2 Let a(n) be the number of spanning trees of the grid graph with a fixed dime\ nsion 3 (counted by vertices). Then infinity ----- 3 2 \ n x - 15 x + 33 x - 15 ) a[n + 3] x = - ----------------------------- / 4 3 2 ----- x - 15 x + 32 x - 15 x + 1 n = 0 and in Maple notation -(x^3-15*x^2+33*x-15)/(x^4-15*x^3+32*x^2-15*x+1) The asymptotics is n 15.355375360813346592 12.543754434581516721 Theorem number, 3 Let a(n) be the number of spanning trees of the grid graph with a fixed dime\ nsion 4 (counted by vertices). Then infinity ----- \ n ) a[n + 4] x = / ----- n = 0 7 6 5 4 3 2 x - 56 x + 671 x - 2632 x + 4143 x - 2744 x + 721 x - 56 - --------------------------------------------------------------------- 8 7 6 5 4 3 2 x - 56 x + 672 x - 2632 x + 4094 x - 2632 x + 672 x - 56 x + 1 and in Maple notation -(x^7-56*x^6+671*x^5-2632*x^4+4143*x^3-2744*x^2+721*x-56)/(x^8-56*x^7+672*x^6-\ 2632*x^5+4094*x^4-2632*x^3+672*x^2-56*x+1) The asymptotics is n 59.346492593658343683 41.173716341504048958 Theorem number, 4 Let a(n) be the number of spanning trees of the grid graph with a fixed dime\ nsion 5 (counted by vertices). Then infinity ----- \ n 15 14 13 12 11 ) a[n + 5] x = - (x - 209 x + 11937 x - 274208 x + 3110592 x / ----- n = 0 10 9 8 7 6 - 19429267 x + 70465218 x - 151751138 x + 195955968 x - 152325888 x 5 4 3 2 / + 71360035 x - 20030769 x + 3297921 x - 300960 x + 13376 x - 209) / / 16 15 14 13 12 11 (x - 209 x + 11936 x - 274208 x + 3112032 x - 19456019 x 10 9 8 7 6 + 70651107 x - 152325888 x + 196664896 x - 152325888 x + 70651107 x 5 4 3 2 - 19456019 x + 3112032 x - 274208 x + 11936 x - 209 x + 1) and in Maple notation -(x^15-209*x^14+11937*x^13-274208*x^12+3110592*x^11-19429267*x^10+70465218*x^9-\ 151751138*x^8+195955968*x^7-152325888*x^6+71360035*x^5-20030769*x^4+3297921*x^3 -300960*x^2+13376*x-209)/(x^16-209*x^15+11936*x^14-274208*x^13+3112032*x^12-\ 19456019*x^11+70651107*x^10-152325888*x^9+196664896*x^8-152325888*x^7+70651107* x^6-19456019*x^5+3112032*x^4-274208*x^3+11936*x^2-209*x+1) The asymptotics is n 232.63319510131118084 133.92874755367742976 Theorem number, 5 Let a(n) be the number of spanning trees of the grid graph with a fixed dime\ nsion 6 (counted by vertices). Then infinity ----- \ n 31 30 29 28 ) a[n + 6] x = - (x - 780 x + 194880 x - 22377420 x / ----- n = 0 27 26 25 + 1419253151 x - 55288358580 x + 1410948477940 x 24 23 22 - 24578756143500 x + 300499461633216 x - 2630580630238080 x 21 20 19 + 16744572638438108 x - 78473331552167760 x + 273584870568724806 x 18 17 - 715691784801350760 x + 1414584660553566912 x 16 15 - 2123329415018942520 x + 2428062981384844026 x 14 13 - 2117581488406046520 x + 1407186712390470724 x 12 11 10 - 710444445020517480 x + 271218124114171968 x - 77796421852799520 x 9 8 7 + 16636883658151388 x - 2628103672318800 x + 303274180751233 x 6 5 4 3 - 25208380729740 x + 1480939292928 x - 59825036700 x + 1592591135 x 2 / 32 31 30 - 26020020 x + 228240 x - 780) / (x - 780 x + 194881 x / 29 28 27 26 - 22377420 x + 1419219792 x - 55284715980 x + 1410775106597 x 25 24 23 - 24574215822780 x + 300429297446885 x - 2629946465331120 x 22 21 20 + 16741727755133760 x - 78475174345180080 x + 273689714665707178 x 19 18 - 716370537293731320 x + 1417056251105102122 x 17 16 - 2129255507292156360 x + 2437932520099475424 x 15 14 - 2129255507292156360 x + 1417056251105102122 x 13 12 11 - 716370537293731320 x + 273689714665707178 x - 78475174345180080 x 10 9 8 + 16741727755133760 x - 2629946465331120 x + 300429297446885 x 7 6 5 4 - 24574215822780 x + 1410775106597 x - 55284715980 x + 1419219792 x 3 2 - 22377420 x + 194881 x - 780 x + 1) and in Maple notation -(x^31-780*x^30+194880*x^29-22377420*x^28+1419253151*x^27-55288358580*x^26+ 1410948477940*x^25-24578756143500*x^24+300499461633216*x^23-2630580630238080*x^ 22+16744572638438108*x^21-78473331552167760*x^20+273584870568724806*x^19-\ 715691784801350760*x^18+1414584660553566912*x^17-2123329415018942520*x^16+ 2428062981384844026*x^15-2117581488406046520*x^14+1407186712390470724*x^13-\ 710444445020517480*x^12+271218124114171968*x^11-77796421852799520*x^10+ 16636883658151388*x^9-2628103672318800*x^8+303274180751233*x^7-25208380729740*x ^6+1480939292928*x^5-59825036700*x^4+1592591135*x^3-26020020*x^2+228240*x-780)/ (x^32-780*x^31+194881*x^30-22377420*x^29+1419219792*x^28-55284715980*x^27+ 1410775106597*x^26-24574215822780*x^25+300429297446885*x^24-2629946465331120*x^ 23+16741727755133760*x^22-78475174345180080*x^21+273689714665707178*x^20-\ 716370537293731320*x^19+1417056251105102122*x^18-2129255507292156360*x^17+ 2437932520099475424*x^16-2129255507292156360*x^15+1417056251105102122*x^14-\ 716370537293731320*x^13+273689714665707178*x^12-78475174345180080*x^11+ 16741727755133760*x^10-2629946465331120*x^9+300429297446885*x^8-24574215822780* x^7+1410775106597*x^6-55284715980*x^5+1419219792*x^4-22377420*x^3+194881*x^2-\ 780*x+1) The asymptotics is n 922.43752564751492917 433.70017993553672030 -------------------------------- This took, 1299.180, seconds. 3 2 -4 + x x - 15 x + 33 x - 15 L := [- ------------, - -----------------------------, 2 4 3 2 x - 4 x + 1 x - 15 x + 32 x - 15 x + 1 7 6 5 4 3 2 x - 56 x + 671 x - 2632 x + 4143 x - 2744 x + 721 x - 56 - ---------------------------------------------------------------------, - 8 7 6 5 4 3 2 x - 56 x + 672 x - 2632 x + 4094 x - 2632 x + 672 x - 56 x + 1 15 14 13 12 11 10 (x - 209 x + 11937 x - 274208 x + 3110592 x - 19429267 x 9 8 7 6 5 + 70465218 x - 151751138 x + 195955968 x - 152325888 x + 71360035 x 4 3 2 / 16 15 - 20030769 x + 3297921 x - 300960 x + 13376 x - 209) / (x - 209 x / 14 13 12 11 10 + 11936 x - 274208 x + 3112032 x - 19456019 x + 70651107 x 9 8 7 6 5 - 152325888 x + 196664896 x - 152325888 x + 70651107 x - 19456019 x 4 3 2 31 30 + 3112032 x - 274208 x + 11936 x - 209 x + 1), - (x - 780 x 29 28 27 26 + 194880 x - 22377420 x + 1419253151 x - 55288358580 x 25 24 23 + 1410948477940 x - 24578756143500 x + 300499461633216 x 22 21 20 - 2630580630238080 x + 16744572638438108 x - 78473331552167760 x 19 18 + 273584870568724806 x - 715691784801350760 x 17 16 + 1414584660553566912 x - 2123329415018942520 x 15 14 + 2428062981384844026 x - 2117581488406046520 x 13 12 + 1407186712390470724 x - 710444445020517480 x 11 10 9 + 271218124114171968 x - 77796421852799520 x + 16636883658151388 x 8 7 6 - 2628103672318800 x + 303274180751233 x - 25208380729740 x 5 4 3 2 + 1480939292928 x - 59825036700 x + 1592591135 x - 26020020 x / 32 31 30 29 + 228240 x - 780) / (x - 780 x + 194881 x - 22377420 x / 28 27 26 + 1419219792 x - 55284715980 x + 1410775106597 x 25 24 23 - 24574215822780 x + 300429297446885 x - 2629946465331120 x 22 21 20 + 16741727755133760 x - 78475174345180080 x + 273689714665707178 x 19 18 - 716370537293731320 x + 1417056251105102122 x 17 16 - 2129255507292156360 x + 2437932520099475424 x 15 14 - 2129255507292156360 x + 1417056251105102122 x 13 12 11 - 716370537293731320 x + 273689714665707178 x - 78475174345180080 x 10 9 8 + 16741727755133760 x - 2629946465331120 x + 300429297446885 x 7 6 5 4 - 24574215822780 x + 1410775106597 x - 55284715980 x + 1419219792 x 3 2 - 22377420 x + 194881 x - 780 x + 1)] [-(-4+x)/(x^2-4*x+1), -(x^3-15*x^2+33*x-15)/(x^4-15*x^3+32*x^2-15*x+1), -(x^7-\ 56*x^6+671*x^5-2632*x^4+4143*x^3-2744*x^2+721*x-56)/(x^8-56*x^7+672*x^6-2632*x^ 5+4094*x^4-2632*x^3+672*x^2-56*x+1), -(x^15-209*x^14+11937*x^13-274208*x^12+ 3110592*x^11-19429267*x^10+70465218*x^9-151751138*x^8+195955968*x^7-152325888*x ^6+71360035*x^5-20030769*x^4+3297921*x^3-300960*x^2+13376*x-209)/(x^16-209*x^15 +11936*x^14-274208*x^13+3112032*x^12-19456019*x^11+70651107*x^10-152325888*x^9+ 196664896*x^8-152325888*x^7+70651107*x^6-19456019*x^5+3112032*x^4-274208*x^3+ 11936*x^2-209*x+1), -(x^31-780*x^30+194880*x^29-22377420*x^28+1419253151*x^27-\ 55288358580*x^26+1410948477940*x^25-24578756143500*x^24+300499461633216*x^23-\ 2630580630238080*x^22+16744572638438108*x^21-78473331552167760*x^20+ 273584870568724806*x^19-715691784801350760*x^18+1414584660553566912*x^17-\ 2123329415018942520*x^16+2428062981384844026*x^15-2117581488406046520*x^14+ 1407186712390470724*x^13-710444445020517480*x^12+271218124114171968*x^11-\ 77796421852799520*x^10+16636883658151388*x^9-2628103672318800*x^8+ 303274180751233*x^7-25208380729740*x^6+1480939292928*x^5-59825036700*x^4+ 1592591135*x^3-26020020*x^2+228240*x-780)/(x^32-780*x^31+194881*x^30-22377420*x ^29+1419219792*x^28-55284715980*x^27+1410775106597*x^26-24574215822780*x^25+ 300429297446885*x^24-2629946465331120*x^23+16741727755133760*x^22-\ 78475174345180080*x^21+273689714665707178*x^20-716370537293731320*x^19+ 1417056251105102122*x^18-2129255507292156360*x^17+2437932520099475424*x^16-\ 2129255507292156360*x^15+1417056251105102122*x^14-716370537293731320*x^13+ 273689714665707178*x^12-78475174345180080*x^11+16741727755133760*x^10-\ 2629946465331120*x^9+300429297446885*x^8-24574215822780*x^7+1410775106597*x^6-\ 55284715980*x^5+1419219792*x^4-22377420*x^3+194881*x^2-780*x+1)] 1299.237