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 1 - x ) a[1](n) x = ------- / 1 - 2 x ----- n = 0 and in Maple notation (1-x)/(1-2*x) 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] ---------------------- This ends this article that took, 2069.375, seconds to generate