A068920 -id:A068920 - cp's OEIS frontend

A068921 Number of ways to tile a 2 X n room with 1 X 2 Tatami mats. At most 3 Tatami mats may meet at a point.

1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872, 1278, 1873, 2745, 4023, 5896, 8641, 12664, 18560, 27201, 39865, 58425, 85626, 125491, 183916, 269542, 395033, 578949, 848491, 1243524, 1822473, 2670964, 3914488, 5736961

Offset: 0

Dean Hickerson, Mar 11 2002

G. C. Greubel, Table of n, a(n) for n = 0..1000
Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).
Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 10.
Richard J. Mathar, Paving rectangular regions with rectangular tiles: Tatami and Non-Tatami Tilings, arXiv:1311.6135 [math.CO], 2013, Table 1.
Richard J. Mathar, Bivariate Generating Functions Enumerating Non-Bonding Dominoes on Rectangular Boards, arXiv:2404.18806 [math.CO], 2024. See p. 7.
Index entries for linear recurrences with constant coefficients, signature (1,0,1).

Cf. A068927 for incongruent tilings, A068920 for more info.

Cf. A000930, A078012, first column of A272471.

LinearRecurrence[{1, 0, 1}, {1, 1, 2}, 42] (* Robert G. Wilson v, Jul 12 2014 *)

my(x='x+O('x^50)); Vec((1+x^2)/(1-x-x^3)) \\ G. C. Greubel, Apr 26 2017

For n >= 3, a(n) = a(n-1) + a(n-3).
a(n) = A000930(n+1).
From Frank Ruskey, Jun 07 2009: (Start)
G.f.: (1+x^2)/(1-x-x^3).
a(n) = Sum_{j=0..floor(n/2)} binomial(n-2j+1, j). (End)
G.f.: Q(0)*( 1+x^2 )/2, where Q(k) = 1 + 1/(1 - x*(4*k+1 + x^2)/( x*(4*k+3 + x^2) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Sep 08 2013

A068922 Number of ways to tile a 3 X 2n room with 1 X 2 Tatami mats. At most 3 Tatami mats may meet at a point.

Original entry on oeis.org

3, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974, 3194, 5168, 8362, 13530, 21892, 35422, 57314, 92736, 150050, 242786, 392836, 635622, 1028458, 1664080, 2692538, 4356618, 7049156, 11405774, 18454930, 29860704, 48315634, 78176338, 126491972

Offset: 1

Dean Hickerson, Mar 11 2002

Colin Barker, Table of n, a(n) for n = 1..1000
R. J. Mathar, Paving Rectangular Regions with Rectangular Tiles: Tatami and Non-Tatami Tilings, arXiv:1311.6135 [math.CO], 2013, Table 2.
F. Ruskey and J. Woodcock, Counting Fixed-Height Tatami Tilings, Electronic Journal of Combinatorics, Paper R126 (2009) 20 pages.
Index entries for linear recurrences with constant coefficients, signature (1,1).

Cf. A068928 for incongruent tilings, A068920 for more info. First column of A272472.
Essentially the same as A006355.
Essentially the same as A078642. - Georg Fischer, Oct 06 2018

Concatenation([3],List([2..40],n->2*Fibonacci(n+1))); # Muniru A Asiru, Oct 07 2018

[3] cat [2*Fibonacci(n+1): n in [2..50]]; // Vincenzo Librandi, Oct 07 2018

with(combinat): 3,seq(2*fibonacci(n+1),n=2..40); # Muniru A Asiru, Oct 07 2018

Join[{3}, Table[2 Fibonacci[n + 1], {n, 2, 50}]] (* Vincenzo Librandi, Oct 07 2018 *)
CoefficientList[Series[(x^2-x-3) / (x^2+x-1), {x, 0, 50}], x] (* Stefano Spezia, Oct 07 2018 *)

Vec(x*(3+x-x^2) / (1-x-x^2) + O(x^50)) \\ Colin Barker, Jan 29 2017

For n >= 2, a(n) = 2*F(n+1), where F(n)=A000045(n) is the n-th Fibonacci number.
G.f.: x*(x^2-x-3) / (x^2+x-1). - Maksym Voznyy (voznyy(AT)mail.ru), Aug 11 2009; checked and corrected by R. J. Mathar, Sep 16 2009
From Colin Barker, Jan 29 2017: (Start)
a(n) = (2^(-n)*(-(1-sqrt(5))^(1+n) + (1+sqrt(5))^(1+n))) / sqrt(5) for n>1.
a(n) = a(n-1) + a(n-2) for n>3. (End)
E.g.f.: 2*exp(x/2)*(5*cosh(sqrt(5)*x/2) + sqrt(5)*sinh(sqrt(5)*x/2))/5 - 2 + x. - Stefano Spezia, Apr 18 2022

A068926 Table read by antidiagonals: ti(r,s) is the number of incongruent ways to tile an r X s room with 1 X 2 Tatami mats. At most 3 Tatami mats may meet at a point.

Original entry on oeis.org

0, 1, 1, 0, 1, 0, 1, 2, 2, 1, 0, 3, 0, 3, 0, 1, 4, 2, 2, 4, 1, 0, 6, 0, 1, 0, 6, 0, 1, 8, 2, 2, 2, 2, 8, 1, 0, 12, 0, 2, 0, 2, 0, 12, 0, 1, 16, 4, 2, 1, 1, 2, 4, 16, 1, 0, 24, 0, 3, 0, 1, 0, 3, 0, 24, 0, 1, 33, 5, 3, 1, 1, 1, 1, 3, 5, 33, 1, 0, 49, 0, 4, 0, 1, 0, 1, 0, 4, 0, 49, 0

Offset: 0

Dean Hickerson, Mar 11 2002

			Table begins:
  0, 1, 0, 1, 0, 1, 0, ...
  1, 1, 2, 3, 4, 6, 8, ...
  0, 2, 0, 2, 0, 2, 0, ...
  1, 3, 2, 1, 2, 2, 2, ...
  0, 4, 0, 2, 0, 1, 0, ...
  1, 6, 2, 2, 1, 1, 1, ...
  0, 8, 0, 2, 0, 1, 0, ...
  ...

Michael De Vlieger, Table of n, a(n) for n = 0..11325 (antidiagonals 1..150, flattened)
Dean Hickerson, Filling rectangular rooms with Tatami mats

Cf. A068920 (total number of tilings), A052270 (count by area).

Cf. A068927 (row 2), A068928 (row 3), A068929 (row 4), A068930 (row 5), A068931 (row 6).

(* See link above for Mathematica programs. *)
c[r_, s_] := Which[s<0, 0, r==1, 1 - Mod[s, 2], r == 2, c1[2, s] + c2[2, s] + Boole[s == 0], OddQ[r], c[r, s] = c[r, s - r + 1] + c[r, s - r - 1] + Boole[s == 0], EvenQ[r], c[r, s] = c1[r, s] + c2[r, s] + Boole[s == 0]];
c1[r_, s_] := Which[s <= 0, 0, r == 2, c[2, s - 1], EvenQ[r], c2[r, s - 1] + Boole[s == 1]];
c2[r_, s_] := Which[s <= 0, 0, r == 2, c2[2, s] = c1[2, s - 2] + Boole[s == 2], EvenQ[r], c2[r, s] = c1[r, s - r + 2] + c1[r, s - r] + Boole[s == r - 2] + Boole[s == r]];
cs[r_, s_] := Which[s < 0, 0, r == 1, c[r, s], r == 2, cs[2, s] = c1s[r, s] + c2s[r, s] + Boole[s == 0], OddQ[r], cs[r, s] = cs[r, s - 2 r + 2] + cs[r, s - 2 r - 2] + Boole[s == 0] + Boole[s == r - 1] + Boole[s == r + 1], EvenQ[r], cs[r, s] = c1s[r, s] + c2s[r, s] + Boole[s == 0]];
c1s[r_, s_] := Which[s <= 0, 0, r == 2, cs[r, s - 2] + Boole[s == 1], EvenQ[r], c2s[r, s - 2] + Boole[s == 1]];
c2s[r_, s_] := Which[s <= 0, 0, r == 2, c2s[2, s] = c1s[2, s - 4] + Boole[s == 2], EvenQ[r], c2s[r, s] = c1s[r, s - 2 r + 4] + c1s[r, s - 2 r] + Boole[s == r - 2] + Boole[s == r]];
ti[r_, s_] := Which[r > s, ti[s, r], r == s, 1 - Mod[r, 2], True, (c[r, s] + cs[r, s])/2];
A068926[n_] := Module[{x}, x = Floor[(Sqrt[8 n + 1] - 1)/2]; ti[n + 1 - x (x + 1)/2, (x + 1) (x + 2)/2 - n]];
Table[A068926[n], {n, 0, 100}] (* Jean-François Alcover, May 12 2017, copied and adapted from Dean Hickerson's programs *)

A165633 Number of tatami-free rooms of given size A165632(n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 4, 2, 1, 1, 1, 1, 3, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 4, 2, 1, 1, 1

Offset: 1

M. F. Hasler, Sep 26 2009

nonn

Number of rectangles of size A165632(n) which cannot be tiled with tatamis of size 1x2 such that not more than 3 tatamis meet at any point.

			a(1)=1 because the rectangle of size 7x10 is the only one of size 70 that cannot be filled with 2x1 tiles without having 4 tiles meet in some point.
a(237)=5 because there are 5 different rectangles of size A165632(237)=1320 which cannot be tiled in the given way.

Project Euler, Problem 256: Tatami-Free Rooms, Sept. 2009.

Cf. A068920.

A165633 = #{ {r,c} | rc = A165632(n) }.

A165632 Sizes of tatami-free rooms.

Original entry on oeis.org

70, 88, 96, 108, 126, 130, 140, 150, 154, 160, 176, 180, 192, 198, 204, 208, 216, 228, 234, 238, 240, 250, 252, 260, 266, 270, 280, 286, 294, 300, 304, 308, 320, 322, 330, 336, 340, 348, 352, 360, 368, 372, 374, 378, 384, 390, 396, 400, 408, 414, 416, 418

Offset: 1

M. F. Hasler, Sep 26 2009

nonn

Even numbers s such that some rectangle of size s=r*c (r,c positive integers) cannot be tiled with tatamis of size 1x2 such that not more than 3 tatamis meet at any point.

The number of different rectangles of size a(n) which have this property is given in A165633(n).

			a(1)=70 because the rectangle of size 7x10 is the smallest that cannot be filled with 2x1 tiles without having 4 tiles meet in some point.

Project Euler, Problem 256: Tatami-Free Rooms

Cf. A068920.

A165632 = { r*c in 2Z | A068920(r,c)=0 }

A068924 Number of ways to tile a 5 X 2n room with 1x2 Tatami mats. At most 3 Tatami mats may meet at a point.

Original entry on oeis.org

6, 3, 2, 2, 4, 4, 6, 8, 10, 14, 18, 24, 32, 42, 56, 74, 98, 130, 172, 228, 302, 400, 530, 702, 930, 1232, 1632, 2162, 2864, 3794, 5026, 6658, 8820, 11684, 15478, 20504, 27162, 35982, 47666, 63144, 83648, 110810, 146792, 194458, 257602, 341250

Offset: 1

Dean Hickerson, Mar 11 2002

R. J. Mathar, Paving rectangular regions with rectangular tiles,...., arXiv:1311.6135 [math.CO], Table 4.
F. Ruskey and J. Woodcock, Counting Fixed-Height Tatami Tilings, Electronic Journal of Combinatorics, Paper R126 (2009) 20 pages.
Index entries for linear recurrences with constant coefficients, signature (0,1,1).

Cf. A068930 for incongruent tilings, A068920 for more info. First column of A272474.

For n >= 6, a(n) = a(n-2) + a(n-3).
G.f.: x*(-6+x^4+7*x^3+4*x^2-3*x)/(-1+x^3+x^2). [Maksym Voznyy (voznyy(AT)mail.ru), Aug 11 2009; checked and corrected by R. J. Mathar, Sep 16 2009]
a(n) = 2*A000931(n+3) for n>=3. - R. J. Mathar, Dec 06 2013

A052270 Consider a room of size r X s where rs = 2n and 1 <= r <= s; count ways to arrange n Tatami mats in room; a(n) = total number of ways for all choices of r and s. Two arrangements are considered the same if one is a rotation or reflection of the other.

Original entry on oeis.org

1, 2, 3, 4, 5, 9, 9, 14, 19, 27, 34, 56, 70, 105, 152, 218, 308, 466, 654, 966, 1407, 2052, 2979, 4399, 6378, 9361, 13697, 20051, 29308, 43035, 62885, 92204, 135053, 197871, 289775, 424891, 622199, 911988, 1336319, 1958344, 2869418, 4205888

Offset: 1

Yasutoshi Kohmoto

Tatami mats are of size 1 X 2; at most 3 may meet at a point.

			For n = 3 there are 2 ways to cover a 2 X 3 room and 1 way to cover a 1 X 6 room, so a(3)=3:
._____. ._____.
|___| | | | | | .___________.
|___|_| |_|_|_| |___|___|___|

Dean Hickerson, Illustration of first few cases
Dean Hickerson, Filling rectangular rooms with Tatami mats (Includes Mathematica program)
Yasutoshi Kohmoto, Illustration of a(6) = 9

Cf. A067925 for total number of tilings, A068926 for table of number of incongruent tilings of an r X s room.

c[r_, s_] := Which[s<0, 0, r==1, 1 - Mod[s, 2], r == 2, c1[2, s] + c2[2, s] + Boole[s == 0], OddQ[r], c[r, s] = c[r, s - r + 1] + c[r, s - r - 1] + Boole[s == 0], EvenQ[r], c[r, s] = c1[r, s] + c2[r, s] + Boole[s == 0]];
c1[r_, s_] := Which[s <= 0, 0, r == 2, c[2, s - 1], EvenQ[r], c2[r, s - 1] + Boole[s == 1]];
c2[r_, s_] := Which[s <= 0, 0, r == 2, c2[2, s] = c1[2, s - 2] + Boole[s == 2], EvenQ[r], c2[r, s] = c1[r, s - r + 2] + c1[r, s - r] + Boole[s == r - 2] + Boole[s == r]];
cs[r_, s_] := Which[s < 0, 0, r == 1, c[r, s], r == 2, cs[2, s] = c1s[r, s] + c2s[r, s] + Boole[s == 0], OddQ[r], cs[r, s] = cs[r, s - 2 r + 2] + cs[r, s - 2 r - 2] + Boole[s == 0] + Boole[s == r - 1] + Boole[s == r + 1], EvenQ[r], cs[r, s] = c1s[r, s] + c2s[r, s] + Boole[s == 0]];
c1s[r_, s_] := Which[s <= 0, 0, r == 2, cs[r, s - 2] + Boole[s == 1], EvenQ[r], c2s[r, s - 2] + Boole[s == 1]];
c2s[r_, s_] := Which[s <= 0, 0, r == 2, c2s[2, s] = c1s[2, s - 4] + Boole[s == 2], EvenQ[r], c2s[r, s] = c1s[r, s - 2 r + 4] + c1s[r, s - 2 r] + Boole[s == r - 2] + Boole[s == r]];
ti[r_, s_] := Which[r > s, ti[s, r], r == s, 1 - Mod[r, 2], True, (c[r, s] + cs[r, s])/2];
A052270[n_] := Module[{i, divs}, divs = Divisors[2 n]; Sum[ti[divs[[i]], 2 n/divs[[i]]], {i, 1, Ceiling[Length[divs]/2]}]];
Table[A052270[n], {n, 1, 50}] (* Jean-François Alcover, May 12 2017, copied and adapted from Dean Hickerson's programs *)

Extended by Dean Hickerson, Mar 01 2002

A067925 Consider a room of size r X s where rs = 2n and 1 <= r, 1 <= s; count ways to arrange n Tatami mats in room; a(n) = total number of ways for all choices of r and s. Two arrangements are distinguished if one is a rotation or reflection of the other.

Original entry on oeis.org

2, 4, 8, 10, 14, 28, 28, 42, 70, 90, 122, 204, 260, 386, 592, 824, 1192, 1810, 2558, 3764, 5580, 8064, 11794, 17438, 25338, 37144, 54626, 79762, 116852, 171650, 250984, 367874, 539668, 790110, 1157912, 1697978, 2487050, 3645012, 5343444

Offset: 1

Yasutoshi Kohmoto Mar 05 2002

Tatami mats are of size 1 X 2; at most 3 may meet at a point.

			For n=3 there are 3 incongruent tilings, shown below. These can be rotated to produce 8 tilings, so a(3)=8.
._____. ._____.
|___| | | | | | .___________.
|___|_| |_|_|_| |___|___|___|

Dean Hickerson, Filling rectangular rooms with Tatami mats

Cf. A052270 for number of incongruent tilings, A068920 for table of number of tilings of an r X s room.

(* See link for Mathematica programs. *)
c[r_, s_] := Which[s<0, 0, r==1, 1 - Mod[s, 2], r == 2, c1[2, s] + c2[2, s] + Boole[s == 0], OddQ[r], c[r, s] = c[r, s - r + 1] + c[r, s - r - 1] + Boole[s == 0], EvenQ[r], c[r, s] = c1[r, s] + c2[r, s] + Boole[s == 0]];
c1[r_, s_] := Which[s <= 0, 0, r == 2, c[2, s - 1], EvenQ[r], c2[r, s - 1] + Boole[s == 1]];
c2[r_, s_] := Which[s <= 0, 0, r == 2, c2[2, s] = c1[2, s - 2] + Boole[s == 2], EvenQ[r], c2[r, s] = c1[r, s - r + 2] + c1[r, s - r] + Boole[s == r - 2] + Boole[s == r]];
t[r_, s_] := Which[r>s, t[s, r], OddQ[r] && r>1, 2 c[r, s], True, c[r, s]];
A067925[n_] := Module[{i, divs}, divs = Divisors[2 n]; Sum[t[divs[[i]], 2 n/divs[[i]]], {i, 1, Length[divs]}]];
Table[A067925[n], {n, 1, 50}] (* Jean-François Alcover, May 12 2017, copied and adapted from Dean Hickerson's programs *)

Edited by Dean Hickerson, Mar 11 2002

A068923 Number of ways to tile a 4 X n room with 1x2 Tatami mats. At most 3 Tatami mats may meet at a point.

Original entry on oeis.org

1, 4, 4, 2, 3, 3, 3, 5, 5, 6, 8, 8, 11, 13, 14, 19, 21, 25, 32, 35, 44, 53, 60, 76, 88, 104, 129, 148, 180, 217, 252, 309, 365, 432, 526, 617, 741, 891, 1049, 1267, 1508, 1790, 2158, 2557, 3057, 3666, 4347, 5215, 6223, 7404, 8881, 10570, 12619, 15104, 17974

Offset: 1

Dean Hickerson, Mar 11 2002

R. J. Mathar, Paving rectangular regions with rectangular tiles,...., arXiv:1311.6135 [math.CO], Table 3.
Index entries for linear recurrences with constant coefficients, signature (0,0,1,0,1).

Cf. A068929 for incongruent tilings, A068920 for more info. First column of A272473.

For n >= 9, a(n) = a(n-3) + a(n-5).

G.f.: x*(x+1)*(2*x^6+x^5+x^4-x^2-3*x-1)/(-1+x^5+x^3) [From Maksym Voznyy (voznyy(AT)mail.ru), Jul 28 2009]

G.f. proposed by Maksym Voznyy checked and corrected by R. J. Mathar, Sep 16 2009.

A068925 Number of ways to tile a 6 X n room with 1x2 Tatami mats. At most 3 Tatami mats may meet at a point.

Original entry on oeis.org

1, 9, 6, 3, 2, 2, 2, 1, 1, 2, 3, 4, 3, 3, 3, 4, 6, 6, 7, 6, 7, 9, 10, 13, 12, 14, 15, 17, 22, 22, 27, 27, 31, 37, 39, 49, 49, 58, 64, 70, 86, 88, 107, 113, 128, 150, 158, 193, 201, 235, 263, 286, 343, 359, 428, 464, 521, 606, 645, 771, 823, 949, 1070, 1166, 1377, 1468

Offset: 1

Dean Hickerson, Mar 11 2002

For n >= 12, a(n) = a(n-5) + a(n-7).

R. J. Mathar, Paving rectangular regions with rectangular tiles,...., arXiv:1311.6135 [math.CO], Table 5.
Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,1,0,1).

Cf. A068931 for incongruent tilings, A068920 for more info.

G.f.: x*(1-2*x^10-6*x^9-11*x^8-6*x^7-7*x^6+x^5+2*x^4+3*x^3+6*x^2+9*x)/(1-x^7-x^5) [From Maksym Voznyy (voznyy(AT)mail.ru), Aug 11 2009]

G.f. proposed by Maksym Voznyy checked and corrected by R. J. Mathar, Sep 16 2009.

cp's OEIS Frontend

A068921 Number of ways to tile a 2 X n room with 1 X 2 Tatami mats. At most 3 Tatami mats may meet at a point.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A068922 Number of ways to tile a 3 X 2n room with 1 X 2 Tatami mats. At most 3 Tatami mats may meet at a point.

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Formula

A068926 Table read by antidiagonals: ti(r,s) is the number of incongruent ways to tile an r X s room with 1 X 2 Tatami mats. At most 3 Tatami mats may meet at a point.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A165633 Number of tatami-free rooms of given size A165632(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A165632 Sizes of tatami-free rooms.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A068924 Number of ways to tile a 5 X 2n room with 1x2 Tatami mats. At most 3 Tatami mats may meet at a point.

Views

Author

Keywords

Links

Crossrefs

Formula

A052270 Consider a room of size r X s where rs = 2n and 1 <= r <= s; count ways to arrange n Tatami mats in room; a(n) = total number of ways for all choices of r and s. Two arrangements are considered the same if one is a rotation or reflection of the other.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A067925 Consider a room of size r X s where rs = 2n and 1 <= r, 1 <= s; count ways to arrange n Tatami mats in room; a(n) = total number of ways for all choices of r and s. Two arrangements are distinguished if one is a rotation or reflection of the other.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions