----------------------------------------------- The Generating Functions for the Number of Spanning Trees in Grid Graphs By Shalosh B. Ekhad This is the story of the generating functions, in , z of the sequences enumerating the number of spanning trees in grid-graphs P_n x P_m, for general n, and m from 2 to, 6 Theorem: Let, A(2, n), be the number of spanning trees in the , 2, by n grid graph, and let infinity ----- \ n f(z) = ) A(2, n) z / ----- n = 0 Then : z f(z) = ------------ 2 1 - 4 z + z And in Maple-input format, it is: z/(1-4*z+z^2) The first , 30, terms are: [1, 4, 15, 56, 209, 780, 2911, 10864, 40545, 151316, 564719, 2107560, 7865521, 29354524, 109552575, 408855776, 1525870529, 5694626340, 21252634831, 79315912984, 296011017105, 1104728155436, 4122901604639, 15386878263120, 57424611447841, 214311567528244, 799821658665135, 2984975067132296, 11140078609864049, 41575339372323900] Theorem: Let, A(3, n), be the number of spanning trees in the , 3, by n grid graph, and let infinity ----- \ n f(z) = ) A(3, n) z / ----- n = 0 Then : 2 z (-1 + z ) f(z) = - ----------------------------- 2 3 4 1 - 15 z + 32 z - 15 z + z And in Maple-input format, it is: -z*(-1+z^2)/(1-15*z+32*z^2-15*z^3+z^4) The first , 30, terms are: [1, 15, 192, 2415, 30305, 380160, 4768673, 59817135, 750331584, 9411975375, 118061508289, 1480934568960, 18576479568193, 233018797965135, 2922930580320960, 36664523428884015, 459910778352898337, 5769007865476035840, 72365017995700730081, 907729015392142395375, 11386329862223500207296, 142827325702873981372815, 1791590900164844149159297, 22473276298898655194173440, 281899259233885701359889025, 3536075083120298342440801935, 44355657504903447676859022528, 556386475525911555059983837935, 6979175319719333589675520988129, 87545061366451265500023776544000] Theorem: Let, A(4, n), be the number of spanning trees in the , 4, by n grid graph, and let infinity ----- \ n f(z) = ) A(4, n) z / ----- n = 0 Then : 2 3 4 6 z (1 - 49 z + 112 z - 49 z + z ) f(z) = --------------------------------------------------------------------- 2 3 4 5 6 7 8 1 - 56 z + 672 z - 2632 z + 4094 z - 2632 z + 672 z - 56 z + z And in Maple-input format, it is: z*(1-49*z^2+112*z^3-49*z^4+z^6)/(1-56*z+672*z^2-2632*z^3+4094*z^4-2632*z^5+672* z^6-56*z^7+z^8) The first , 30, terms are: [1, 56, 2415, 100352, 4140081, 170537640, 7022359583, 289143013376, 11905151192865, 490179860527896, 20182531537581071, 830989874753525760, 34214941811800329425, 1408756312731277540744, 58003732850974438010175, 2388229243489107516194816, 98332273432993735566334273, 4048705133573796221764525560, 166700236720421701398973625263, 6863668260790646684044452390912, 282602730032000912315954740344945, 11635804643672459612539385026592872, 479089319803727354015166006771993439, 19725887755842805930245125686879764480, 812188107043419732226106284169171254881, 33440802735348892291948093536540743747800, 1376882126057448000490859816205636406470735, 56691354093976384771073887779803938974152704, 2334193732481147942455005866608760491340320529, 96107430627295371442302076835629206411100969800] Theorem: Let, A(5, n), be the number of spanning trees in the , 5, by n grid graph, and let infinity ----- \ n f(z) = ) A(5, n) z / ----- n = 0 Then : 2 3 4 5 6 f(z) = - z (-1 + 1440 z - 26752 z + 185889 z - 574750 z + 708928 z 8 9 10 11 12 14 / - 708928 z + 574750 z - 185889 z + 26752 z - 1440 z + z ) / (1 / 2 3 4 5 6 - 209 z + 11936 z - 274208 z + 3112032 z - 19456019 z + 70651107 z 7 8 9 10 11 - 152325888 z + 196664896 z - 152325888 z + 70651107 z - 19456019 z 12 13 14 15 16 + 3112032 z - 274208 z + 11936 z - 209 z + z ) And in Maple-input format, it is: -z*(-1+1440*z^2-26752*z^3+185889*z^4-574750*z^5+708928*z^6-708928*z^8+574750*z^ 9-185889*z^10+26752*z^11-1440*z^12+z^14)/(1-209*z+11936*z^2-274208*z^3+3112032* z^4-19456019*z^5+70651107*z^6-152325888*z^7+196664896*z^8-152325888*z^9+ 70651107*z^10-19456019*z^11+3112032*z^12-274208*z^13+11936*z^14-209*z^15+z^16) The first , 30, terms are: [1, 209, 30305, 4140081, 557568000, 74795194705, 10021992194369, 1342421467113969, 179796299139278305, 24080189412483072000, 3225041354570508955681, 431926215138756947267505, 57847355494807961811035009, 7747424602888405489208931601, 1037602902862756514154816000000, 138964858389586339640223412108401, 18611389483734199394023624777573409, 2492600085599977923424220468405177105, 333830807688353225138019865387722924481, 44709541971379003103897461691112357888000, 5987892960038182781131697625354150226327105, 801951004627869433685025226859351146717402769, 107404293649401297954327034703922488508540561569, 14384522530358739351890623742584897464468359377905, 1926501086648879747745673025840512108858205299200000, 258013877695694120804712221064093162848578908856571281, 34555475491252459965101163680103428812170683289730088705, 4627971553665255661896001375366896994510897198018850677809, 619818433896435032361580416286522616772627078698025714103201, 83011506562431376380390013640740802987778069424647853056000000] Theorem: Let, A(6, n), be the number of spanning trees in the , 6, by n grid graph, and let infinity ----- \ n f(z) = ) A(6, n) z / ----- n = 0 Then : 2 3 4 9 f(z) = z (1 - 33359 z + 3642600 z - 173371343 z - 1842793012320 z 10 11 12 + 104844096982372 z - 678752492380560 z + 2471590551535210 z 13 14 15 - 5926092273213840 z + 9869538714631398 z - 11674018886109840 z 16 5 6 7 + 9869538714631398 z + 4540320720 z - 70164186331 z + 634164906960 z 8 17 18 - 2844883304348 z - 5926092273213840 z + 2471590551535210 z 19 20 21 - 678752492380560 z + 104844096982372 z - 1842793012320 z 22 23 24 25 - 2844883304348 z + 634164906960 z - 70164186331 z + 4540320720 z 26 27 28 30 / - 173371343 z + 3642600 z - 33359 z + z ) / (1 - 780 z / 2 3 4 9 + 194881 z - 22377420 z + 1419219792 z - 2629946465331120 z 10 11 12 + 16741727755133760 z - 78475174345180080 z + 273689714665707178 z 13 14 - 716370537293731320 z + 1417056251105102122 z 15 16 5 - 2129255507292156360 z + 2437932520099475424 z - 55284715980 z 6 7 8 + 1410775106597 z - 24574215822780 z + 300429297446885 z 17 18 - 2129255507292156360 z + 1417056251105102122 z 19 20 21 - 716370537293731320 z + 273689714665707178 z - 78475174345180080 z 22 23 24 + 16741727755133760 z - 2629946465331120 z + 300429297446885 z 25 26 27 - 24574215822780 z + 1410775106597 z - 55284715980 z 28 29 30 31 32 + 1419219792 z - 22377420 z + 194881 z - 780 z + z ) And in Maple-input format, it is: z*(1-33359*z^2+3642600*z^3-173371343*z^4-1842793012320*z^9+104844096982372*z^10 -678752492380560*z^11+2471590551535210*z^12-5926092273213840*z^13+ 9869538714631398*z^14-11674018886109840*z^15+9869538714631398*z^16+4540320720*z ^5-70164186331*z^6+634164906960*z^7-2844883304348*z^8-5926092273213840*z^17+ 2471590551535210*z^18-678752492380560*z^19+104844096982372*z^20-1842793012320*z ^21-2844883304348*z^22+634164906960*z^23-70164186331*z^24+4540320720*z^25-\ 173371343*z^26+3642600*z^27-33359*z^28+z^30)/(1-780*z+194881*z^2-22377420*z^3+ 1419219792*z^4-2629946465331120*z^9+16741727755133760*z^10-78475174345180080*z^ 11+273689714665707178*z^12-716370537293731320*z^13+1417056251105102122*z^14-\ 2129255507292156360*z^15+2437932520099475424*z^16-55284715980*z^5+1410775106597 *z^6-24574215822780*z^7+300429297446885*z^8-2129255507292156360*z^17+ 1417056251105102122*z^18-716370537293731320*z^19+273689714665707178*z^20-\ 78475174345180080*z^21+16741727755133760*z^22-2629946465331120*z^23+ 300429297446885*z^24-24574215822780*z^25+1410775106597*z^26-55284715980*z^27+ 1419219792*z^28-22377420*z^29+194881*z^30-780*z^31+z^32) The first , 30, terms are: [1, 780, 380160, 170537640, 74795194705, 32565539635200, 14143261515284447, 6136973985625588560, 2662079368040434932480, 1154617875754582889149500, 500769437567956298239402223, 217185579535490113365186969600, 94193702839904633186530210863025, 40851869157273984726590135085017940, 17717469746416280095776019395706656000, 7684070867169415429692559499446691755680, 3332583081296808509759455619848802299528513, 1445341907485491645328460310146924377335398400, 626845049313054375044367343971643549398400207439, 271862811296852944176805652529210910158678393501000, 117906950273496738441417982275113800569185953508401920, 51136265564260810934348514677358578182539093981985579140, 22177807578786871771975685968088359261519721558786693144351, 9618519137859358557484551263002772100493327681623268157030400, 4171553480859669166764609074130946419690927672433431476417301025, 1809203495268378561427549408448430750759030036616841097919332985500, 784651881439272378819594430425368142664597935508249012776181518286080, 340303662167183966505537475986213779843792970000024727053163782358717080, 147589759514663135524738411416132378729266135389120483181714254960506345457 , 64009705258157188975303879517278636748220260668937846227901842986863001\ 600000] The whole thing took, 2419.243, seconds.