The Number of Ways to Color a square Grid Graph By Shalosh B. Ekhad The number of ways of coloring the , 1, by , 1, grid graph with , c, colors , is given by the polynomial c The number of ways of coloring the , 2, by , 2, grid graph with , c, colors , is given by the polynomial 6*c^2-3*c+c^4-4*c^3 The number of ways of coloring the , 3, by , 3, grid graph with , c, colors , is given by the polynomial -323*c^2+79*c-648*c^4+594*c^3+459*c^5-216*c^6+66*c^7-12*c^8+c^9 The number of ways of coloring the , 4, by , 4, grid graph with , c, colors , is given by the polynomial 112275*c^2+682349*c^4-346274*c^3+1022204*c^6-960627*c^5-848056*c^7+557782*c^8-\ 292883*c^9+122662*c^10-40614*c^11+10437*c^12-2015*c^13+276*c^14-24*c^15+c^16-\ 17493*c The number of ways of coloring the , 5, by , 5, grid graph with , c, colors , is given by the polynomial -290435775*c^2-3767970906*c^4+1292190143*c^3-13560791041*c^6+8082227271*c^5+ 18473119556*c^7-20932275014*c^8+20054961996*c^9-16429209737*c^10+11594826096*c^ 11-7082871652*c^12+3754018486*c^13-1726958903*c^14+688444232*c^15-236955938*c^ 16+69997383*c^17-17590911*c^18+3714180*c^19-647352*c^20-9864*c^22+90798*c^21+ 780*c^23-40*c^24+c^25+32126211*c The number of ways of coloring the , 6, by , 6, grid graph with , c, colors , is given by the polynomial 5825814032243*c^2+136941429389741*c^4-34701118575475*c^3+937366494881708*c^6-\ 402341997408799*c^5-1800744848216564*c^7+2928391022625810*c^8-4106892530565262* c^9+5035286921842561*c^10-5452617664392448*c^11+5255806080178105*c^12-\ 4536473593633301*c^13+3522243070378354*c^14-2468460778341254*c^15+ 1565357403345916*c^16-899710667370661*c^17+469138441850555*c^18-221984387672138 *c^19+95279523237139*c^20+13038370427571*c^22-37057990954938*c^21-4139593962920 *c^23+1182113898251*c^24-13883355652*c^27-302331982014*c^25+68878826042*c^26+ 2454371695*c^28-376347854*c^29+49332660*c^30+c^36-60*c^35+1770*c^34-5421612*c^ 31-34195*c^33+486210*c^32-486300871185*c The number of ways of coloring the , 7, by , 7, grid graph with , c, colors , is given by the polynomial -922154302362866569*c^2-35641918028267568371*c^4+7025664984910421341*c^3-\ 410250705513629800783*c^6+135369215825036731177*c^5+1032451012296991972867*c^7-\ 2216960500804578752422*c^8+4141697227066979584712*c^9-6830530217372810189624*c^ 10+10056541931639164603607*c^11-13334646797326075179058*c^12+ 16036290758482683498688*c^13-17590653016736281101094*c^14+ 17681773699830438464325*c^15-16348665822385814798376*c^16+ 13947697552939503415693*c^17-11007588075825516394630*c^18+ 8052847847428403113202*c^19-5470083215526714490040*c^20-2030267506558332837891* c^22-95248*c^46+42674658178*c^41+3454521587982666078590*c^21+ 1111177466299328848403*c^23-566568113071643821648*c^24+49105932301716479533*c^ 27+269165350824419182148*c^25-119133381750252738955*c^26-18838563798680068882*c ^28+6720264457198789127*c^29-2226581959125468535*c^30-4469520251*c^42-\ 559835789575554*c^36+2636742581430*c^39-356501190440*c^40-17429512454108*c^38+ 2751868417954614*c^35-12377772493912959*c^34-30755376*c^44+684166468013185562*c ^31+51133582658290835*c^33-194611137853887936*c^32+3486*c^47+1926585*c^45+ 403410654*c^43+c^49+103761863635925*c^37+60466776520638151*c-84*c^48 ------------------------------------------------------------ The first, 7, terms of the sequence enumerating the number of ways of legally coloring the n by n grid graph for n from 1 to , 7, with , 1, colors is: [1, 0, 0, 0, 0, 0, 0] The first, 7, terms of the sequence enumerating the number of ways of legally coloring the n by n grid graph for n from 1 to , 7, with , 2, colors is: [2, 2, 2, 2, 2, 2, 2] The first, 7, terms of the sequence enumerating the number of ways of legally coloring the n by n grid graph for n from 1 to , 7, with , 3, colors is: [3, 18, 246, 7812, 580986, 101596896, 41869995708] The first, 7, terms of the sequence enumerating the number of ways of legally coloring the n by n grid graph for n from 1 to , 7, with , 4, colors is: [4, 84, 9612, 6000732, 20442892764, 380053267505964, 38557892676685306572] The first, 7, terms of the sequence enumerating the number of ways of legally coloring the n by n grid graph for n from 1 to , 7, with , 5, colors is: [5, 260, 142820, 828850160, 50820390410180, 32921147633979091400, 225313329780157255086187280] The whole thing took, 4377.806, seconds