Generating functions for the number of ways to tile an m by n rectangle with Rectangular 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 RECTANGULAR tiles , then infinity ----- \ n x - 1 ) a[1](n) x = ------- / 2 x - 1 ----- n = 0 and in Maple notation (x-1)/(2*x-1) The first 31 terms of the sequence, starting at n=0 are [1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768 , 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912] Theorem number, 2 Let , a[2](n), be the number of ways to tile an, 2, by n rectangle with RECTANGULAR tiles , then infinity ----- 2 \ n 3 x - 4 x + 1 ) a[2](n) x = -------------- / 2 ----- 7 x - 6 x + 1 n = 0 and in Maple notation (3*x^2-4*x+1)/(7*x^2-6*x+1) The first 31 terms of the sequence, starting at n=0 are [1, 2, 8, 34, 148, 650, 2864, 12634, 55756, 246098, 1086296, 4795090, 21166468, 93433178, 412433792, 1820570506, 8036386492, 35474325410, 156591247016, 691227204226, 3051224496244, 13468756547882, 59453967813584, 262442511046330, 1158477291582892, 5113766172173042, 22573255991958008, 99643172746536754, 439846244535514468, 1941575257987329530, 8570527836175375904] Theorem number, 3 Let , a[3](n), be the number of ways to tile an, 3, by n rectangle with RECTANGULAR tiles , then infinity ----- 3 2 \ n 19 x - 29 x + 11 x - 1 ) a[3](n) x = ------------------------ / 3 2 ----- 51 x - 55 x + 15 x - 1 n = 0 and in Maple notation (19*x^3-29*x^2+11*x-1)/(51*x^3-55*x^2+15*x-1) The first 31 terms of the sequence, starting at n=0 are [1, 4, 34, 322, 3164, 31484, 314662, 3149674, 31544384, 315981452, 3165414034, 31710994234, 317682195692, 3182564368244, 31883205466534, 319408833724882, 3199866987994304, 32056562443839284, 321145602837871522, 3217266324544621714, 32230871396722195484, 322891848845610185612, 3234760388416207739974, 32406128580967387860634, 324647591642745511677152, 3252349582497202937561084, 32582338754736377702065234, 326412881457479525060653642, 3270034419059049452111832044, 32759507082215923166146857284, 328187770139322583404145432582] Theorem number, 4 Let , a[4](n), be the number of ways to tile an, 4, by n rectangle with RECTANGULAR tiles , then infinity ----- \ n ) a[4](n) x = / ----- n = 0 6 5 4 3 2 3832 x - 8492 x + 6722 x - 2468 x + 441 x - 36 x + 1 ------------------------------------------------------------ 6 5 4 3 2 11680 x - 20980 x + 13840 x - 4280 x + 645 x - 44 x + 1 and in Maple notation (3832*x^6-8492*x^5+6722*x^4-2468*x^3+441*x^2-36*x+1)/(11680*x^6-20980*x^5+13840 *x^4-4280*x^3+645*x^2-44*x+1) The first 31 terms of the sequence, starting at n=0 are [1, 8, 148, 3164, 70878, 1613060, 36911922, 846280548, 19415751782, 445550465628, 10225294476962, 234675373081668, 5385967300825942, 123612245431357148, 2837003283963428562, 65111601723938370628, 1494366038587416919782, 34296959750113321113308, 787144140855580816678402, 18065621773988215662683588, 414621254165878560765855222, 9515907434978003509250184668, 218398100505495483693822328242, 5012420584744221116311442260548, 115039279468004317454443709795462, 2640248478145672399462107480267228, 60595929134993190753741331851302882, 1390727675115704906133736344013152708, 31918372965700735521620229378295332502, 732553576812246366990043194939094624988, 16812722361416086890850311260279531186322] Theorem number, 5 Let , a[5](n), be the number of ways to tile an, 5, by n rectangle with RECTANGULAR tiles , then infinity ----- \ n 10 9 8 7 ) a[5](n) x = (39672144 x - 110891556 x + 124284414 x - 74544838 x / ----- n = 0 6 5 4 3 2 + 26669637 x - 5961522 x + 841659 x - 73608 x + 3769 x - 100 x + 1) / 10 9 8 7 / (135762480 x - 326041524 x + 320708934 x - 170972730 x / 6 5 4 3 2 + 54776249 x - 11002298 x + 1395665 x - 109292 x + 4975 x - 116 x + 1 ) and in Maple notation (39672144*x^10-110891556*x^9+124284414*x^8-74544838*x^7+26669637*x^6-5961522*x^ 5+841659*x^4-73608*x^3+3769*x^2-100*x+1)/(135762480*x^10-326041524*x^9+ 320708934*x^8-170972730*x^7+54776249*x^6-11002298*x^5+1395665*x^4-109292*x^3+ 4975*x^2-116*x+1) The first 31 terms of the sequence, starting at n=0 are [1, 16, 650, 31484, 1613060, 84231996, 4427635270, 233276449488, 12300505521832 , 648782777031100, 34223109012944482, 1805323555104984956, 95234889270955121716 , 5023877415526067785580, 265022449692240368203598, 13980623266954069411358904, 737514369447195695172127928, 38905810707327993880952077676, 2052383256625484696428623422202, 108268584856985900227733020022276, 5711451048124508087979916987180068, 301293982486699828945184410620193804, 15894045690283994103805036267874746230, 838452485354206121181698693282450169024 , 44230561804613114729228520982531686037416, 2333277832383616609121389637446481335383324, 123086508988375918534295500794944858301013298, 6493135315779978977464818748214319515921020748, 342529872490260322040055499466837786359722465140, 18069346755039904033120792939754486446536079682604, 953205306679301253351436814875051010944729251059134] Theorem number, 6 Let , a[6](n), be the number of ways to tile an, 6, by n rectangle with RECTANGULAR tiles , then infinity ----- \ n 20 19 ) a[6](n) x = (916798938728006656 x - 3962057190907156288 x / ----- n = 0 18 17 + 7644699117821849592 x - 8795707489604640136 x 16 15 + 6787540243858479914 x - 3741365942249935792 x 14 13 + 1530293206620422033 x - 475918767335413756 x 12 11 10 + 114321113226304761 x - 21415445169034874 x + 3143712388922139 x 9 8 7 - 361909626897452 x + 32569667881308 x - 2274379347082 x 6 5 4 3 2 + 121717789540 x - 4898404600 x + 144102468 x - 2968032 x + 39908 x / 20 19 - 308 x + 1) / (3488260147244630016 x - 13785403213649739264 x / 18 17 + 24571927550599277952 x - 26305901575283773400 x 16 15 + 18988035581731414180 x - 9828185761768234778 x 14 13 + 3785664669818771697 x - 1111033817019987980 x 12 11 10 + 252212834590208135 x - 44688005447169948 x + 6207093806210985 x 9 8 7 - 676048684437666 x + 57526055007906 x - 3794064844276 x 6 5 4 3 2 + 191447789306 x - 7247125678 x + 199881354 x - 3842502 x + 47924 x - 340 x + 1) and in Maple notation (916798938728006656*x^20-3962057190907156288*x^19+7644699117821849592*x^18-\ 8795707489604640136*x^17+6787540243858479914*x^16-3741365942249935792*x^15+ 1530293206620422033*x^14-475918767335413756*x^13+114321113226304761*x^12-\ 21415445169034874*x^11+3143712388922139*x^10-361909626897452*x^9+32569667881308 *x^8-2274379347082*x^7+121717789540*x^6-4898404600*x^5+144102468*x^4-2968032*x^ 3+39908*x^2-308*x+1)/(3488260147244630016*x^20-13785403213649739264*x^19+ 24571927550599277952*x^18-26305901575283773400*x^17+18988035581731414180*x^16-\ 9828185761768234778*x^15+3785664669818771697*x^14-1111033817019987980*x^13+ 252212834590208135*x^12-44688005447169948*x^11+6207093806210985*x^10-\ 676048684437666*x^9+57526055007906*x^8-3794064844276*x^7+191447789306*x^6-\ 7247125678*x^5+199881354*x^4-3842502*x^3+47924*x^2-340*x+1) The first 31 terms of the sequence, starting at n=0 are [1, 32, 2864, 314662, 36911922, 4427635270, 535236230270, 64878517290010, 7871769490695758, 955411617212520670, 115973945786899746170, 14078248409306427591814, 1709004742525016740261850, 207462778992946779638832746 , 25184765957310295151583128422, 3057285045647115846906741050066, 371136822520175340428639512398530, 45053879581625921702326004016485422, 5469282487853734617019976164284400378, 663939521194712445448979649262390964426, 80598449682203313904504827062157366370778, 9784189511373700185494942156709375649930514, 1187744489070059821416709137849020460490078710, 144185368640002135364860108836728074475885860314, 17503276775715478688713472961415133466984272394070, 2124797410327544242654221499181471727113789867029510, 257938218815708172820307260954311339152631516107816166, 31312220356918388729126804975748767742737107781068237150, 3801123959771127551514143082028534610199316072832189623822, 461434647331173425742591222430803225089819363133906560440902, 56015519622908638338759025186188562060168556471218507971669178] ---------------------- This ends this article that took, 122016.065, seconds to generate