The Number of Domino Tilings of Rectangles of width up to , 9 By Shalosh B. Ekhad [ShaloshBEkhad@gmail.com ] ------------------------------------------------------------------- Theorem number, 1, : Let A(n) be the number of ways to tile, with dominoes, the 1, by 2n rectangle. Then infinity ----- \ n 1 ) A(n) t = - ------ / -1 + t ----- n = 0 and in Maple input format: -1/(-1+t) Equivalently, A(n) satisfies the linear recurrence A(n) = A(n - 1) subject to the initial conditions A(0) = 1 n A(n) is asymptotic to, 1.000000000 1. For the sake of Sloane here are the first 31 terms, starting at n=0 [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(n) be the number of ways to tile, with dominoes, the 2, by n rectangle. Then infinity ----- \ n 1 ) A(n) t = - ----------- / 2 ----- -1 + t + t n = 0 and in Maple input format: -1/(-1+t+t^2) Equivalently, A(n) satisfies the linear recurrence A(n) = A(n - 1) + A(n - 2) subject to the initial conditions A(0) = 1, A(1) = 1 n A(n) is asymptotic to, 0.7236067865 1.618033989 For the sake of Sloane here are the first 31 terms, starting at n=0 [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] ------------------------------------------------------------------- Theorem number, 3, : Let A(n) be the number of ways to tile, with dominoes, the 3, by 2n rectangle. Then infinity ----- \ n -1 + t ) A(n) t = - ------------ / 2 ----- 1 - 4 t + t n = 0 and in Maple input format: -(-1+t)/(1-4*t+t^2) Equivalently, A(n) satisfies the linear recurrence A(n) = 4 A(n - 1) - A(n - 2) subject to the initial conditions A(0) = 1, A(1) = 3 n A(n) is asymptotic to, 0.7886751255 3.732050808 For the sake of Sloane here are the first 31 terms, starting at n=0 [1, 3, 11, 41, 153, 571, 2131, 7953, 29681, 110771, 413403, 1542841, 5757961, 21489003, 80198051, 299303201, 1117014753, 4168755811, 15558008491, 58063278153, 216695104121, 808717138331, 3018173449203, 11263976658481, 42037733184721, 156886956080403, 585510091136891, 2185153408467161, 8155103542731753, 30435260762459851] ------------------------------------------------------------------- Theorem Number, 4, : Let A(n) be the number of ways to tile, with dominoes, the 4, by n rectangle. Then infinity ----- \ n (-1 + t) (t + 1) ) A(n) t = - ---------------------- / 2 3 4 ----- 1 - t - 5 t - t + t n = 0 and in Maple input format: -(-1+t)*(t+1)/(1-t-5*t^2-t^3+t^4) Equivalently, A(n) satisfies the linear recurrence A(n) = A(n - 1) + 5 A(n - 2) + A(n - 3) - A(n - 4) subject to the initial conditions A(0) = 1, A(1) = 1, A(2) = 5, A(3) = 11 n A(n) is asymptotic to, 0.5274743307 2.840536194 For the sake of Sloane here are the first 31 terms, starting at n=0 [1, 1, 5, 11, 36, 95, 281, 781, 2245, 6336, 18061, 51205, 145601, 413351, 1174500, 3335651, 9475901, 26915305, 76455961, 217172736, 616891945, 1752296281, 4977472781, 14138673395, 40161441636, 114079985111, 324048393905, 920471087701, 2614631600701, 7426955448000] ------------------------------------------------------------------- Theorem number, 5, : Let A(n) be the number of ways to tile, with dominoes, the 5, by 2n rectangle. Then infinity ----- 2 \ n (-1 + t) (t - 6 t + 1) ) A(n) t = - ----------------------------- / 2 3 4 ----- 1 - 15 t + 32 t - 15 t + t n = 0 and in Maple input format: -(-1+t)*(t^2-6*t+1)/(1-15*t+32*t^2-15*t^3+t^4) Equivalently, A(n) satisfies the linear recurrence A(n) = 15 A(n - 1) - 32 A(n - 2) + 15 A(n - 3) - A(n - 4) subject to the initial conditions A(0) = 1, A(1) = 8, A(2) = 95, A(3) = 1183 n A(n) is asymptotic to, 0.5986593440 12.54375443 For the sake of Sloane here are the first 31 terms, starting at n=0 [1, 8, 95, 1183, 14824, 185921, 2332097, 29253160, 366944287, 4602858719, 57737128904, 724240365697, 9084693297025, 113956161827912, 1429438110270431, 17930520634652959, 224916047725262248, 2821291671062267585, 35389589910135145793, 443918325373278904936, 5568402462493067660191, 69848673082432054864223, 876164602727391706265480, 10990393620885072574324993, 137860798719773541769682689, 1729292005296109247705958536, 21691814260119434075868141407, 272096791319491733265402363295, 3413115332749275973727074619752, 42813280590911899543303559833409] ------------------------------------------------------------------- Theorem Number, 6, : Let A(n) be the number of ways to tile, with dominoes, the 6, by n rectangle. Then infinity ----- \ n ) A(n) t = / ----- n = 0 2 4 3 2 (t - 2 t - 1) (t + 2 t - 3 t - 2 t + 1) - ------------------------------------------------------------ 3 2 3 2 (-1 + t) (t + 1) (t + 6 t + 5 t + 1) (t - 5 t + 6 t - 1) and in Maple input format: -(t^2-2*t-1)*(t^4+2*t^3-3*t^2-2*t+1)/(-1+t)/(t+1)/(t^3+6*t^2+5*t+1)/(t^3-5*t^2+ 6*t-1) Equivalently, A(n) satisfies the linear recurrence A(n) = A(n - 1) + 20 A(n - 2) + 10 A(n - 3) - 38 A(n - 4) - 10 A(n - 5) + 20 A(n - 6) - A(n - 7) - A(n - 8) subject to the initial conditions A(0) = 1, A(1) = 1, A(2) = 13, A(3) = 41, A(4) = 281, A(5) = 1183, A(6) = 6728, A(7) = 31529 n A(n) is asymptotic to, 0.3883782531 5.048917340 For the sake of Sloane here are the first 31 terms, starting at n=0 [1, 1, 13, 41, 281, 1183, 6728, 31529, 167089, 817991, 4213133, 21001799, 106912793, 536948224, 2720246633, 13704300553, 69289288909, 349519610713, 1765722581057, 8911652846951, 45005025662792, 227191499132401, 1147185247901449, 5791672851807479, 29242880940226381, 147640981046478543, 745439797095329713, 3763622719883603968, 19002353776441540177, 95940879136187583953] ------------------------------------------------------------------- Theorem number, 7, : Let A(n) be the number of ways to tile, with dominoes, the 7, by 2n rectangle. Then infinity ----- \ n ) A(n) t = / ----- n = 0 6 5 4 3 2 (-1 + t) (t - 34 t + 243 t - 484 t + 243 t - 34 t + 1) - --------------------------------------------------------------------- 2 3 4 5 6 7 8 1 - 56 t + 672 t - 2632 t + 4094 t - 2632 t + 672 t - 56 t + t and in Maple input format: -(-1+t)*(t^6-34*t^5+243*t^4-484*t^3+243*t^2-34*t+1)/(1-56*t+672*t^2-2632*t^3+ 4094*t^4-2632*t^5+672*t^6-56*t^7+t^8) Equivalently, A(n) satisfies the linear recurrence A(n) = 56 A(n - 1) - 672 A(n - 2) + 2632 A(n - 3) - 4094 A(n - 4) + 2632 A(n - 5) - 672 A(n - 6) + 56 A(n - 7) - A(n - 8) subject to the initial conditions A(0) = 1, A(1) = 21, A(2) = 781, A(3) = 31529, A(4) = 1292697, A(5) = 53175517, A(6) = 2188978117, A(7) = 90124167441 n A(n) is asymptotic to, 0.4492571029 41.17371634 For the sake of Sloane here are the first 31 terms, starting at n=0 [1, 21, 781, 31529, 1292697, 53175517, 2188978117, 90124167441, 3710708201969, 152783289861989, 6290652543875133, 259009513044645817, 10664383939345916681, 439092316687230373293, 18079062471131097321077, 744382189686310539093281, 30648981125778378496845537, 1261932455010147392171339189, 51958448944552497866018608237, 2139322438385927464134216597321, 88083855241102209799967552571257, 3626739669963111109417976551206269, 149326350415539894045994373618140197, 6148320794321463286411392502944556081, 253149216361962680754446319092730664657, 10423094026561486012140505452086166938373, 429157516850467885244913251018405305395101, 17670009864625408735461658213818974278099417, 727539973917664938781470418203474744385124073, 29955524513191190437115705736790194001470682189] ------------------------------------------------------------------- Theorem Number, 8, : Let A(n) be the number of ways to tile, with dominoes, the 8, by n rectangle. Then infinity ----- \ n 12 10 9 8 7 ) A(n) t = - (-1 + t) (t + 1) (t - 42 t - 26 t + 318 t + 84 t / ----- n = 0 6 5 4 3 2 / 2 3 - 715 t + 84 t + 318 t - 26 t - 42 t + 1) / (1 - t - 76 t - 69 t / 4 5 6 7 8 9 10 + 921 t + 584 t - 4019 t - 829 t + 7012 t - 829 t - 4019 t 11 12 13 14 15 16 + 584 t + 921 t - 69 t - 76 t - t + t ) and in Maple input format: -(-1+t)*(t+1)*(t^12-42*t^10-26*t^9+318*t^8+84*t^7-715*t^6+84*t^5+318*t^4-26*t^3 -42*t^2+1)/(1-t-76*t^2-69*t^3+921*t^4+584*t^5-4019*t^6-829*t^7+7012*t^8-829*t^9 -4019*t^10+584*t^11+921*t^12-69*t^13-76*t^14-t^15+t^16) Equivalently, A(n) satisfies the linear recurrence A(n) = A(n - 1) + 76 A(n - 2) + 69 A(n - 3) - 921 A(n - 4) - 584 A(n - 5) + 4019 A(n - 6) + 829 A(n - 7) - 7012 A(n - 8) + 829 A(n - 9) + 4019 A(n - 10) - 584 A(n - 11) - 921 A(n - 12) + 69 A(n - 13) + 76 A(n - 14) + A(n - 15) - A(n - 16) subject to the initial conditions A(0) = 1, A(1) = 1, A(2) = 34, A(3) = 153, A(4) = 2245, A(5) = 14824, A(6) = 167089, A(7) = 1292697, A(8) = 12988816, A(9) = 108435745, A(10) = 1031151241, A(11) = 8940739824, A(12) = 82741005829, A(13) = 731164253833, A(14) = 6675498237130, A(15) = 59554200469113 n A(n) is asymptotic to, 0.2869899902 9.007097522 For the sake of Sloane here are the first 31 terms, starting at n=0 [1, 1, 34, 153, 2245, 14824, 167089, 1292697, 12988816, 108435745, 1031151241, 8940739824, 82741005829, 731164253833, 6675498237130, 59554200469113, 540061286536921, 4841110033666048, 43752732573098281, 393139145126822985, 3547073578562247994, 31910388243436817641, 287665106926232833093, 2589464895903294456096, 23333526083922816720025, 210103825878043857266833, 1892830605678515060701072, 17046328120997609883612969, 153554399246902845860302369, 1382974514097522648618420280] ------------------------------------------------------------------- Theorem number, 9, : Let A(n) be the number of ways to tile, with dominoes, the 9, by 2n rectangle. Then infinity ----- \ n 14 13 12 11 ) A(n) t = - (-1 + t) (t - 153 t + 6624 t - 117337 t / ----- n = 0 10 9 8 7 6 + 1015377 t - 4669138 t + 11732530 t - 16025408 t + 11732530 t 5 4 3 2 / - 4669138 t + 1015377 t - 117337 t + 6624 t - 153 t + 1) / (1 / 2 3 4 5 6 - 209 t + 11936 t - 274208 t + 3112032 t - 19456019 t + 70651107 t 7 8 9 10 11 - 152325888 t + 196664896 t - 152325888 t + 70651107 t - 19456019 t 12 13 14 15 16 + 3112032 t - 274208 t + 11936 t - 209 t + t ) and in Maple input format: -(-1+t)*(t^14-153*t^13+6624*t^12-117337*t^11+1015377*t^10-4669138*t^9+11732530* t^8-16025408*t^7+11732530*t^6-4669138*t^5+1015377*t^4-117337*t^3+6624*t^2-153*t +1)/(1-209*t+11936*t^2-274208*t^3+3112032*t^4-19456019*t^5+70651107*t^6-\ 152325888*t^7+196664896*t^8-152325888*t^9+70651107*t^10-19456019*t^11+3112032*t ^12-274208*t^13+11936*t^14-209*t^15+t^16) Equivalently, A(n) satisfies the linear recurrence A(n) = 209 A(n - 1) - 11936 A(n - 2) + 274208 A(n - 3) - 3112032 A(n - 4) + 19456019 A(n - 5) - 70651107 A(n - 6) + 152325888 A(n - 7) - 196664896 A(n - 8) + 152325888 A(n - 9) - 70651107 A(n - 10) + 19456019 A(n - 11) - 3112032 A(n - 12) + 274208 A(n - 13) - 11936 A(n - 14) + 209 A(n - 15) - A(n - 16) subject to the initial conditions A(0) = 1, A(1) = 55, A(2) = 6336, A(3) = 817991, A(4) = 108435745, A(5) = 14479521761, A(6) = 1937528668711, A(7) = 259423766712000, A(8) = 34741645659770711, A(9) = 4652799879944138561, A(10) = 623139489426439754945, A(11) = 83456125990631342400791, A(12) = 11177167872295392172767936, A(13) = 1496943834332592837945956455, A(14) = 200483802581126644843760725601, A(15) = 26850544175719495201771597130401 n A(n) is asymptotic to, 0.3356185536 133.9287476 For the sake of Sloane here are the first 31 terms, starting at n=0 [1, 55, 6336, 817991, 108435745, 14479521761, 1937528668711, 259423766712000, 34741645659770711, 4652799879944138561, 623139489426439754945, 83456125990631342400791, 11177167872295392172767936, 1496943834332592837945956455, 200483802581126644843760725601, 26850544175719495201771597130401, 3596059736380751648485086101179655, 481615775979018877779441876486380736, 64502197653480371739809677084818371191, 8638698545179990410829845123586791932545, 1156970076609668722763939926316608615320961, 154951553315826639275300674074817831341022711, 20752467467022548729335973923276039674252408000, 2779351976504269168195934572852970976092633528711, 372235129223955642528624629697775700054802503571361, 49852984652441724736387211150885974708484780355490145, 6676747796314067405068754817049426350933855508503919591, 894208470092112651915065030665009153876173532706060665536, 119760220451326424674806846906064516463272248174518982248855, 16039336331798443886476769212831318725704128041415046037707201] ------------------------------------------------------------------- I hope, dear reader, that you enjoined reading these, 9, theorems as much as I did discovering them. This ends this fascinating book! It took, 4752.288, seconds to generate it.