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 4.02072594216369017578202073175685109476660612944544406606510814269392185306\ 026670992800388455012333828823049831797448686829826927749877789194693143\ 077676925661610877055268984574597062345126545407714251786440047805387670\ 109245096378040881096643155498693709583851935555831762694316928771225873\ 875767205 3.7320508075688772935274463415058723669428052538103806280558069\ 794519330169088000370811461867572485756756261414154067030299699450949989\ 524788116555120943736485280932319023055820679748201010846749232650153123\ 432669033228866506722546689218379712270471316603678615880190499865373798\ n 5938946765034750657604 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, in decimals, is 1.86602540378443864676372317075293618347140262690519031402790348972596650845440\ 0018540573093378624287837813070707703351514984972547499476239405827756047186824\ 2640466159511527910339874100505423374616325076561716334516614433253361273344609\ 1898561352356583018393079400952499326868992969473382517375328802*3.732050807568\ 8772935274463415058723669428052538103806280558069794519330169088000370811461867\ 5724857567562614141540670302996994509499895247881165551209437364852809323190230\ 5582067974820101084674923265015312343266903322886650672254668921837971227047131\ 66036786158801904998653737985938946765034750657604^n*(1.+n) The BZ constant is .232050807568877293527446341505872366942805253810380628055806979451933016908800\ 0370811461867572485756756261414154067030299699450949989524788116555120943736485\ 2809323190230558206797482010108467492326501531234326690332288665067225466892183\ 7971227047131660367861588019049986537379859389467650347506576050 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 15.3553753608133465924576337045655722196591244574182138461782536823974964591\ 817370540223419532204512691095921937103268927112914433686029810247825581\ 666808104207684273109069706290279620366156024717581417303436551296132933\ 221393146932776941278913303575680694943347867036104456993947865867241276\ 154073926 12.543754434581516721257762151340364658722873547954094314679547\ 774665889472634422807453097087188198302458700650052419708112666423976845\ 994210920672022541705446338962255396576640196173592281548799800592801019\ 170944419208012728907890189392914260184545270221902817614140155078207315\ n 7491181371051678536073 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, in decimals, is 12.2135095077653434734986683386076020453920261571629584280985974782024489052715\ 3800409068777928820947518151922697320871096186598842130545730353844214283992909\ 9463666745997773325318628858051075295503525258024780855650587250801337569428740\ 2862309534158304533353369000827287592720903148755815908287664669*12.54375443458\ 1516721257762151340364658722873547954094314679547774665889472634422807453097087\ 1881983024587006500524197081126664239768459942109206720225417054463389622553965\ 7664019617359228154879980059280101917094441920801272890789018939291426018454527\ 02219028176141401550782073157491181371051678536073^n*(1.+n) The BZ constant is .265129945719942245679046496131473830232534869059220470258063675304984327438064\ 8218837409296008488341468694193425394322788801461466945620903237899764896211722\ 8242058332497889233265318581368964525184284999563391828665301467130026970967085\ 7072310422496261285983480081189642759427028387613953721004661358 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 59.3464925936583436826920555953380088105085154061665924608449752453189162533\ 463388167441884409126037765931982139115971431011247925658171976050424326\ 898782084106630982211414052853296366360903421830340661474485844270745680\ 070386541593776753051623412722582006268928370416196615600690212558433152\ 524469263 41.173716341504048958051598806532925239208191711913957913209814\ 389046097963058150898569303720063225524983512841243174582977652126330480\ 470962512755820795300327852130386444111891554099373219619633533051689281\ 301339251582339185451683964001272477093444555263188398947479833209680848\ n 6002000636173363975308 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, in decimals, is 65.1960980268091379804002476227267353751427528521898160332809448503640971509499\ 1922159956467789933888210626755163892611612162301120538603428559817206322845896\ 9355011629430274722254591504368809232548070006283027384788726508211283702778000\ 6657165348834327297789396512220630645345439353209211994069911704*41.17371634150\ 4048958051598806532925239208191711913957913209814389046097963058150898569303720\ 0632255249835128412431745829776521263304804709625127558207953003278521303864441\ 1189155409937321961963353305168928130133925158233918545168396400127247709344455\ 52631883989474798332096808486002000636173363975308^n*(1.+n) The BZ constant is .274641748726427146528748856745628408676737466358679235400852362064133344410837\ 0823367108887614003497682012786271137961774647862265141004270455534235347357805\ 2865171460086707888960230714496314681503719984658469758470015766694673376905875\ 3320693958846674487031086198517710259157900286074137535434746592 -------------------------------- This took, 5279.525, seconds.