Generating Functions for Enumerating the Number of Spanning Trees (and Sum o\ f the Leaves) in Grid Graphs with dimensions s by r, for fixed dimension\ 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 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 Part II: Let b(n) be the sum of the number of leaves in all spanning trees of the abo\ ve-mentioned graph. Then infinity ----- 2 \ n 8 x - 26 x + 8 ) b[n + 2] x = --------------- / 2 2 ----- (x - 4 x + 1) n = 0 and in Maple notation (8*x^2-26*x+8)/(x^2-4*x+1)^2 The asymptotic behavior is n 1.8660254037844386468 3.7320508075688772935 (1. + n) The BZ constant is 0.23205080756887729353 Theorem number, 2 Part I: 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 Part II: Let b(n) be the sum of the number of leaves in all spanning trees of the abo\ ve-mentioned graph. Then infinity ----- \ n ) b[n + 3] x = / ----- n = 0 5 4 3 2 2 (x - 1) (3 x - 15 x - 218 x + 488 x - 221 x + 19) - ------------------------------------------------------- 4 3 2 2 (x - 15 x + 32 x - 15 x + 1) and in Maple notation -2*(x-1)*(3*x^5-15*x^4-218*x^3+488*x^2-221*x+19)/(x^4-15*x^3+32*x^2-15*x+1)^2 The asymptotic behavior is n 12.213509507765343473 12.543754434581516721 (1. + n) The BZ constant is 0.26512994571994224568 Theorem number, 3 Part I: 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 Part II: Let b(n) be the sum of the number of leaves in all spanning trees of the abo\ ve-mentioned graph. Then infinity ----- \ n 13 12 11 10 ) b[n + 4] x = (250 x - 14152 x + 229310 x - 1616896 x / ----- n = 0 9 8 7 6 5 + 5472552 x - 8784168 x + 4578084 x + 4377760 x - 7292958 x 4 3 2 / + 4031944 x - 1077346 x + 142688 x - 8580 x + 168) / / 8 7 6 5 4 3 2 2 (x - 56 x + 672 x - 2632 x + 4094 x - 2632 x + 672 x - 56 x + 1) and in Maple notation (250*x^13-14152*x^12+229310*x^11-1616896*x^10+5472552*x^9-8784168*x^8+4578084*x ^7+4377760*x^6-7292958*x^5+4031944*x^4-1077346*x^3+142688*x^2-8580*x+168)/(x^8-\ 56*x^7+672*x^6-2632*x^5+4094*x^4-2632*x^3+672*x^2-56*x+1)^2 The asymptotic behavior is n 65.196098026809137980 41.173716341504048958 (1. + n) The BZ constant is 0.27464174872642714653 -------------------------------- This took, 5032.844, seconds. 2 3 2 -4 + x 8 x - 26 x + 8 x - 15 x + 33 x - 15 L := [[- ------------, ---------------], [- -----------------------------, 2 2 2 4 3 2 x - 4 x + 1 (x - 4 x + 1) x - 15 x + 32 x - 15 x + 1 5 4 3 2 2 (x - 1) (3 x - 15 x - 218 x + 488 x - 221 x + 19) - -------------------------------------------------------], [ 4 3 2 2 (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 13 12 11 10 9 8 250 x - 14152 x + 229310 x - 1616896 x + 5472552 x - 8784168 x 7 6 5 4 3 + 4578084 x + 4377760 x - 7292958 x + 4031944 x - 1077346 x 2 / + 142688 x - 8580 x + 168) / / 8 7 6 5 4 3 2 2 (x - 56 x + 672 x - 2632 x + 4094 x - 2632 x + 672 x - 56 x + 1) ]] [[-(-4+x)/(x^2-4*x+1), (8*x^2-26*x+8)/(x^2-4*x+1)^2], [-(x^3-15*x^2+33*x-15)/(x ^4-15*x^3+32*x^2-15*x+1), -2*(x-1)*(3*x^5-15*x^4-218*x^3+488*x^2-221*x+19)/(x^4 -15*x^3+32*x^2-15*x+1)^2], [-(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), (250*x^ 13-14152*x^12+229310*x^11-1616896*x^10+5472552*x^9-8784168*x^8+4578084*x^7+ 4377760*x^6-7292958*x^5+4031944*x^4-1077346*x^3+142688*x^2-8580*x+168)/(x^8-56* x^7+672*x^6-2632*x^5+4094*x^4-2632*x^3+672*x^2-56*x+1)^2]] 5032.983