Generating functions for the number of ways to tile an m by n rectangle with\ Square Tiles of any Size By Shalosh B. Ekhad Theorem number, 1 Let , a[1](n), be the number of ways to tile an, 1, by n rectangle with SQUARE tiles , then infinity ----- \ n 1 ) a[1](n) x = ----- / 1 - x ----- n = 0 and in Maple notation 1/(1-x) The first 31 terms of the sequence, starting at n=0 are [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] Theorem number, 2 Let , a[2](n), be the number of ways to tile an, 2, by n rectangle with SQUARE tiles , then infinity ----- \ n 1 ) a[2](n) x = ----------- / 2 ----- -x - x + 1 n = 0 and in Maple notation 1/(-x^2-x+1) The first 31 terms of the sequence, starting at n=0 are [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269] Theorem number, 3 Let , a[3](n), be the number of ways to tile an, 3, by n rectangle with SQUARE tiles , then infinity ----- \ n 1 ) a[3](n) x = ------------------ / 3 2 ----- -x - 2 x - x + 1 n = 0 and in Maple notation 1/(-x^3-2*x^2-x+1) The first 31 terms of the sequence, starting at n=0 are [1, 1, 3, 6, 13, 28, 60, 129, 277, 595, 1278, 2745, 5896, 12664, 27201, 58425, 125491, 269542, 578949, 1243524, 2670964, 5736961, 12322413, 26467299, 56849086 , 122106097, 262271568, 563332848, 1209982081, 2598919345, 5582216355] Theorem number, 4 Let , a[4](n), be the number of ways to tile an, 4, by n rectangle with SQUARE tiles , then infinity ----- \ n 1 - x ) a[4](n) x = ------------------------ / 5 4 2 ----- x + x - 3 x - 2 x + 1 n = 0 and in Maple notation (1-x)/(x^5+x^4-3*x^2-2*x+1) The first 31 terms of the sequence, starting at n=0 are [1, 1, 5, 13, 40, 117, 348, 1029, 3049, 9028, 26738, 79183, 234502, 694476, 2056692, 6090891, 18038173, 53420041, 158203433, 468519406, 1387520047, 4109140098, 12169216863, 36039131181, 106729873498, 316080480394, 936072224321, 2772177541780, 8209802751844, 24313327775136, 72003911101089] Theorem number, 5 Let , a[5](n), be the number of ways to tile an, 5, by n rectangle with SQUARE tiles , then infinity ----- 3 2 \ n -x - x - x + 1 ) a[5](n) x = ---------------------------------------------------- / 8 7 6 5 4 3 2 ----- x + 3 x + 2 x + 5 x + x - 6 x - 7 x - 2 x + 1 n = 0 and in Maple notation (-x^3-x^2-x+1)/(x^8+3*x^7+2*x^6+5*x^5+x^4-6*x^3-7*x^2-2*x+1) The first 31 terms of the sequence, starting at n=0 are [1, 1, 8, 28, 117, 472, 1916, 7765, 31497, 127707, 517881, 2100025, 8515772, 34532063, 140030059, 567832091, 2302600696, 9337214060, 37863085664, 153537580071, 622606110920, 2524713292359, 10237896957896, 41515420557135, 168348065148217, 682663710465602, 2768251248844125, 11225461173992602, 45520065644850010, 184587193719225980, 748514563906259772] Theorem number, 6 Let , a[6](n), be the number of ways to tile an, 6, by n rectangle with SQUARE tiles , then infinity ----- \ n ) a[6](n) x = ( / ----- n = 0 9 8 7 6 5 4 3 2 / -2 x - 3 x - 2 x + 3 x + 7 x + 4 x + 3 x - 5 x - 2 x + 1) / ( / 15 14 13 12 11 10 9 8 7 2 x + 7 x + 12 x + 6 x - 18 x - 13 x - 8 x - 27 x - 32 x 6 5 4 3 2 + x + 40 x + 34 x - 3 x - 15 x - 3 x + 1) and in Maple notation (-2*x^9-3*x^8-2*x^7+3*x^6+7*x^5+4*x^4+3*x^3-5*x^2-2*x+1)/(2*x^15+7*x^14+12*x^13 +6*x^12-18*x^11-13*x^10-8*x^9-27*x^8-32*x^7+x^6+40*x^5+34*x^4-3*x^3-15*x^2-3*x+ 1) The first 31 terms of the sequence, starting at n=0 are [1, 1, 13, 60, 348, 1916, 10668, 59257, 329350, 1830234, 10171315, 56525022, 314128014, 1745708992, 9701463927, 53914132251, 299618062228, 1665073290365, 9253344266757, 51423790446062, 285778433090830, 1588162056821687, 8825923956549044, 49048479247236561, 272578069823107677, 1514803420791637906, 8418246578430363967, 46782885807192556538, 259987443235126753783, 1444833286225895208367, 8029400185678994995187] Theorem number, 7 Let , a[7](n), be the number of ways to tile an, 7, by n rectangle with SQUARE tiles , then infinity ----- \ n 18 17 16 15 14 13 12 ) a[7](n) x = (6 x - x - 9 x + 13 x + 20 x - 35 x - 47 x / ----- n = 0 11 10 9 8 7 6 5 4 3 - 76 x - 145 x - 127 x - 8 x + 64 x + 96 x + 68 x + 7 x - 10 x 2 / 25 24 23 22 21 20 - 13 x - 2 x + 1) / (-6 x - 11 x + 9 x + 10 x - 39 x - 12 x / 19 18 17 16 15 14 13 + 70 x + 281 x + 403 x + 110 x + 118 x + 790 x + 179 x 12 11 10 9 8 7 6 5 - 466 x - 327 x - 669 x - 1028 x - 231 x + 45 x + 284 x + 273 x 4 3 2 + 61 x - 45 x - 31 x - 3 x + 1) and in Maple notation (6*x^18-x^17-9*x^16+13*x^15+20*x^14-35*x^13-47*x^12-76*x^11-145*x^10-127*x^9-8* x^8+64*x^7+96*x^6+68*x^5+7*x^4-10*x^3-13*x^2-2*x+1)/(-6*x^25-11*x^24+9*x^23+10* x^22-39*x^21-12*x^20+70*x^19+281*x^18+403*x^17+110*x^16+118*x^15+790*x^14+179*x ^13-466*x^12-327*x^11-669*x^10-1028*x^9-231*x^8+45*x^7+284*x^6+273*x^5+61*x^4-\ 45*x^3-31*x^2-3*x+1) The first 31 terms of the sequence, starting at n=0 are [1, 1, 21, 129, 1029, 7765, 59257, 450924, 3435392, 26160354, 199243634, 1517411733, 11556549312, 88013947545, 670309228276, 5105035683160, 38879655193542, 296105186372225, 2255119850966932, 17174861374796123, 130802743517191075, 996186073044886758, 7586895087246751067, 57781350915568861480, 440059401804582069666, 3351466763025616855290, 25524575585956016278328, 194393680412010373408483, 1480490943203794981727022, 11275332759083931276557602, 85872277308873365972578993] Theorem number, 8 Let , a[8](n), be the number of ways to tile an, 8, by n rectangle with SQUARE tiles , then infinity ----- \ n 40 39 38 37 36 ) a[8](n) x = (-60 x - 136 x + 321 x + 1038 x + 2045 x / ----- n = 0 35 34 33 32 31 30 - 2501 x - 4393 x - 7347 x - 4372 x + 4825 x + 13838 x 29 28 27 26 25 24 + 19585 x + 9331 x + 40213 x - 19891 x - 57417 x - 68058 x 23 22 21 20 19 18 - 10427 x + 8789 x - 6040 x + 76684 x + 81024 x + 16484 x 17 16 15 14 13 12 - 11908 x - 42083 x - 63711 x - 19938 x + 2290 x + 18240 x 11 10 9 8 7 6 5 + 18560 x + 7633 x - 291 x - 4194 x - 2502 x - 378 x + 361 x 4 3 2 / 48 47 46 + 240 x + 33 x - 27 x - 5 x + 1) / (60 x + 256 x + 35 x / 45 44 43 42 41 40 - 1488 x - 4435 x - 2543 x + 7032 x + 16610 x + 23043 x 39 38 37 36 35 34 + 18924 x + 3186 x - 57091 x - 115830 x - 141242 x + 18849 x 33 32 31 30 29 + 39846 x + 240064 x + 433164 x + 162501 x - 692061 x 28 27 26 25 24 - 641988 x + 446013 x + 530385 x + 657974 x - 654746 x 23 22 21 20 19 - 708014 x - 43614 x - 370550 x + 356235 x + 824516 x 18 17 16 15 14 + 224413 x - 94736 x - 143852 x - 344353 x - 110166 x 13 12 11 10 9 8 + 15107 x + 55317 x + 51581 x + 29259 x + 6818 x - 5977 x 7 6 5 4 3 2 - 8807 x - 2453 x + 1175 x + 708 x + 15 x - 55 x - 6 x + 1) and in Maple notation (-60*x^40-136*x^39+321*x^38+1038*x^37+2045*x^36-2501*x^35-4393*x^34-7347*x^33-\ 4372*x^32+4825*x^31+13838*x^30+19585*x^29+9331*x^28+40213*x^27-19891*x^26-57417 *x^25-68058*x^24-10427*x^23+8789*x^22-6040*x^21+76684*x^20+81024*x^19+16484*x^ 18-11908*x^17-42083*x^16-63711*x^15-19938*x^14+2290*x^13+18240*x^12+18560*x^11+ 7633*x^10-291*x^9-4194*x^8-2502*x^7-378*x^6+361*x^5+240*x^4+33*x^3-27*x^2-5*x+1 )/(60*x^48+256*x^47+35*x^46-1488*x^45-4435*x^44-2543*x^43+7032*x^42+16610*x^41+ 23043*x^40+18924*x^39+3186*x^38-57091*x^37-115830*x^36-141242*x^35+18849*x^34+ 39846*x^33+240064*x^32+433164*x^31+162501*x^30-692061*x^29-641988*x^28+446013*x ^27+530385*x^26+657974*x^25-654746*x^24-708014*x^23-43614*x^22-370550*x^21+ 356235*x^20+824516*x^19+224413*x^18-94736*x^17-143852*x^16-344353*x^15-110166*x ^14+15107*x^13+55317*x^12+51581*x^11+29259*x^10+6818*x^9-5977*x^8-8807*x^7-2453 *x^6+1175*x^5+708*x^4+15*x^3-55*x^2-6*x+1) The first 31 terms of the sequence, starting at n=0 are [1, 1, 34, 277, 3049, 31497, 329350, 3435392, 35863972, 374285478, 3906605183, 40773605243, 425562898029, 4441677458152, 46358636450427, 483853831650209, 5050074056261222, 52708577944998395, 550129399697072615, 5741804607960538038, 59928300863912394900, 625483012552208622473, 6528284522945871575958, 68136940502696849426210, 711158137298852433894377, 7422492006747078786325544, 77469953166130531822106158, 808568555965564841183200071, 8439182973226629266752955551, 88081349107805515752393227672, 919321702736448626843755828790] Theorem number, 9 Let , a[9](n), be the number of ways to tile an, 9, by n rectangle with SQUARE tiles , then infinity ----- \ n 76 75 74 73 72 ) a[9](n) x = (1344 x - 1208 x - 7784 x - 4332 x + 31416 x / ----- n = 0 71 70 69 68 67 + 205907 x + 555531 x - 963988 x + 854224 x - 641347 x 66 65 64 63 62 - 2471216 x - 12730821 x - 53945794 x + 4727016 x + 68293294 x 61 60 59 58 + 192230828 x + 192901559 x - 47364667 x - 1281015679 x 57 56 55 54 - 1598494430 x + 768586614 x + 1669971460 x - 2236486173 x 53 52 51 50 - 3717732365 x + 2035791536 x + 4120774136 x + 7673397585 x 49 48 47 46 - 6653883790 x - 6864344483 x + 2908919975 x + 13777504447 x 45 44 43 42 + 1570955828 x - 8036777962 x + 3151899698 x - 14536232477 x 41 40 39 38 + 14281053656 x + 14371826537 x - 2365781095 x - 11567675791 x 37 36 35 34 - 23104618907 x + 11633930326 x + 13043785407 x - 1502914758 x 33 32 31 30 - 10855910303 x + 60106578 x + 7862845442 x + 963295670 x 29 28 27 26 + 1211636597 x + 2681146722 x - 2222667038 x - 3070897145 x 25 24 23 22 - 723881702 x - 595333490 x + 127612880 x + 853485165 x 21 20 19 18 + 467861541 x + 63169548 x + 34519341 x - 63012275 x 17 16 15 14 13 - 91575663 x - 34846004 x - 1946783 x + 6107184 x + 3982133 x 12 11 10 9 8 7 + 2766497 x + 885225 x - 72919 x - 192643 x - 114987 x - 22709 x 6 5 4 3 2 / 85 + 5235 x + 4362 x + 881 x - 73 x - 68 x - 5 x + 1) / (-1344 x / 84 83 82 81 80 79 - 1480 x + 9192 x + 21156 x - 27344 x - 250687 x - 914175 x 78 77 76 75 74 + 113465 x + 1463061 x - 129404 x + 4746414 x + 24099485 x 73 72 71 70 + 105828361 x + 132103744 x - 8940786 x - 434760503 x 69 68 67 66 - 855621125 x - 512312745 x + 803833497 x + 4560787023 x 65 64 63 62 + 2894580550 x + 607099255 x + 1428625240 x + 13837934656 x 61 60 59 58 + 11739287279 x - 21282864400 x - 29408369869 x - 17367889983 x 57 56 55 54 + 74988057187 x + 45666219083 x - 59686512289 x - 128467527431 x 53 52 51 50 - 3459660263 x + 57485100257 x - 7396320345 x + 34208286148 x 49 48 47 46 - 73595319243 x + 72899875958 x - 1708441232 x - 225285354930 x 45 44 43 42 - 93909802253 x + 516975124397 x + 333783711142 x - 613235605178 x 41 40 39 - 434388951683 x + 154255331078 x + 635981470539 x 38 37 36 35 + 124426980998 x - 382470934863 x - 69507580549 x - 51896043191 x 34 33 32 31 + 5660042607 x + 16311776995 x + 4000053721 x + 63896076481 x 30 29 28 27 + 27254715423 x - 22612865924 x + 3282620755 x - 849087597 x 26 25 24 23 - 14657967751 x - 1210945664 x - 982504819 x - 2965151776 x 22 21 20 19 + 2654213462 x + 2870930507 x - 95455596 x + 49802271 x 18 17 16 15 + 74409991 x - 229205633 x - 158298533 x - 27554436 x 14 13 12 11 10 + 17295264 x + 6534527 x + 6230275 x + 2883306 x + 437530 x 9 8 7 6 5 4 3 - 266038 x - 247101 x - 84182 x + 4155 x + 10514 x + 2079 x - 221 x 2 - 117 x - 6 x + 1) and in Maple notation (1344*x^76-1208*x^75-7784*x^74-4332*x^73+31416*x^72+205907*x^71+555531*x^70-\ 963988*x^69+854224*x^68-641347*x^67-2471216*x^66-12730821*x^65-53945794*x^64+ 4727016*x^63+68293294*x^62+192230828*x^61+192901559*x^60-47364667*x^59-\ 1281015679*x^58-1598494430*x^57+768586614*x^56+1669971460*x^55-2236486173*x^54-\ 3717732365*x^53+2035791536*x^52+4120774136*x^51+7673397585*x^50-6653883790*x^49 -6864344483*x^48+2908919975*x^47+13777504447*x^46+1570955828*x^45-8036777962*x^ 44+3151899698*x^43-14536232477*x^42+14281053656*x^41+14371826537*x^40-\ 2365781095*x^39-11567675791*x^38-23104618907*x^37+11633930326*x^36+13043785407* x^35-1502914758*x^34-10855910303*x^33+60106578*x^32+7862845442*x^31+963295670*x ^30+1211636597*x^29+2681146722*x^28-2222667038*x^27-3070897145*x^26-723881702*x ^25-595333490*x^24+127612880*x^23+853485165*x^22+467861541*x^21+63169548*x^20+ 34519341*x^19-63012275*x^18-91575663*x^17-34846004*x^16-1946783*x^15+6107184*x^ 14+3982133*x^13+2766497*x^12+885225*x^11-72919*x^10-192643*x^9-114987*x^8-22709 *x^7+5235*x^6+4362*x^5+881*x^4-73*x^3-68*x^2-5*x+1)/(-1344*x^85-1480*x^84+9192* x^83+21156*x^82-27344*x^81-250687*x^80-914175*x^79+113465*x^78+1463061*x^77-\ 129404*x^76+4746414*x^75+24099485*x^74+105828361*x^73+132103744*x^72-8940786*x^ 71-434760503*x^70-855621125*x^69-512312745*x^68+803833497*x^67+4560787023*x^66+ 2894580550*x^65+607099255*x^64+1428625240*x^63+13837934656*x^62+11739287279*x^ 61-21282864400*x^60-29408369869*x^59-17367889983*x^58+74988057187*x^57+ 45666219083*x^56-59686512289*x^55-128467527431*x^54-3459660263*x^53+57485100257 *x^52-7396320345*x^51+34208286148*x^50-73595319243*x^49+72899875958*x^48-\ 1708441232*x^47-225285354930*x^46-93909802253*x^45+516975124397*x^44+ 333783711142*x^43-613235605178*x^42-434388951683*x^41+154255331078*x^40+ 635981470539*x^39+124426980998*x^38-382470934863*x^37-69507580549*x^36-\ 51896043191*x^35+5660042607*x^34+16311776995*x^33+4000053721*x^32+63896076481*x ^31+27254715423*x^30-22612865924*x^29+3282620755*x^28-849087597*x^27-\ 14657967751*x^26-1210945664*x^25-982504819*x^24-2965151776*x^23+2654213462*x^22 +2870930507*x^21-95455596*x^20+49802271*x^19+74409991*x^18-229205633*x^17-\ 158298533*x^16-27554436*x^15+17295264*x^14+6534527*x^13+6230275*x^12+2883306*x^ 11+437530*x^10-266038*x^9-247101*x^8-84182*x^7+4155*x^6+10514*x^5+2079*x^4-221* x^3-117*x^2-6*x+1) The first 31 terms of the sequence, starting at n=0 are [1, 1, 55, 595, 9028, 127707, 1830234, 26160354, 374285478, 5353011036, 76569060586, 1095191883209, 15665062073662, 224064344818735, 3204894379079451, 45841053844805851, 655685372871482854, 9378564896063570084, 134145862914757375163, 1918749051397966520006, 27444736979761618753259, 392554506904724506456566, 5614884960041153462597417, 80312243419490343288435197 , 1148742403274258258820967069, 16430983034373375968287181018, 235019794434757524149621509021, 3361594596050494837692290168530, 48082410485357882461949873740121, 687744501017067808352621602955705, 9837121182251335674920414952436583] ---------------------- This ends this article that took, 70.787, seconds to generate