A127867 -id:A127867 - cp's OEIS frontend

A127864 Number of tilings of a 2 X n board with 1 X 1 and L-shaped tiles (where the L-shaped tiles cover 3 squares).

1, 1, 5, 11, 33, 87, 241, 655, 1793, 4895, 13377, 36543, 99841, 272767, 745217, 2035967, 5562369, 15196671, 41518081, 113429503, 309895169, 846649343, 2313089025, 6319476735, 17265131521, 47169216511, 128868696065, 352075825151, 961889042433, 2627929735167

Offset: 0

Silvia Heubach (sheubac(AT)calstatela.edu), Feb 03 2007

The signed version of this sequence appears as A077917.

			a(2) = 5 because the 2 X 2 board can be tiled either with 4 squares or with a single L-shaped tile (in four orientations) together with a single square tile.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
P. Z. Chinn, R. Grimaldi and S. Heubach, Tiling with Ls and Squares, J. Int. Sequences 10 (2007) #07.2.8.
S. Heubach, Tiling with Ls and Squares, 2005.
Index entries for linear recurrences with constant coefficients, signature (1,4,2).

Cf. A077917, A127865, A127866, A127867, A127868, A127869, A127870, A127871, A127872.

Column k=2 of A220054. - Alois P. Heinz, Dec 03 2012

I:=[1,1,5]; [n le 3 select I[n] else Self(n-1) + 4*Self(n-2) + 2*Self(n-3): n in [1..41]]; // G. C. Greubel, Dec 08 2022

CoefficientList[Series[1/(1-x-4*x^2-2*x^3), {x,0,30}], x]

A028860 = BinaryRecurrenceSequence(2,2,-1,1)
def A127864(n): return A028860(n+2) + (-1)^n
[A127864(n) for n in range(51)] # G. C. Greubel, Dec 08 2022

a(n) = a(n-1) + 4*a(n-2) + 2*a(n-3).
a(n) = (-1)^n + (1/sqrt(3)) * ((1+sqrt(3))^n - (1-sqrt(3))^n).
G.f.: 1/(1 - x - 4*x^2 - 2*x^3).
a(n) = A028860(n+2) + (-1)^n. - R. J. Mathar, Oct 29 2010
E.g.f.: exp(-x) + (2/sqrt(3))*exp(x)*sinh(sqrt(3)*x). - G. C. Greubel, Dec 08 2022
From Greg Dresden, Nov 10 2024: (Start)
a(n) = 1 + 4*a(n-2) + 6*Sum_{i=0..n-3} a(i) for n>1.
a(2*n) = a(n)^2 + 4*a(n-1)^2 + 4*a(n-1)*a(n-2) for n>1. (End)

A220054 Number A(n,k) of tilings of a k X n rectangle using right trominoes and 1 X 1 tiles; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 11, 11, 1, 1, 1, 1, 33, 39, 33, 1, 1, 1, 1, 87, 195, 195, 87, 1, 1, 1, 1, 241, 849, 2023, 849, 241, 1, 1, 1, 1, 655, 3895, 16839, 16839, 3895, 655, 1, 1, 1, 1, 1793, 17511, 151817, 249651, 151817, 17511, 1793, 1, 1

Offset: 0

Alois P. Heinz, Dec 03 2012

			A(2,2) = 5, because there are 5 tilings of a 2 X 2 rectangle using right trominoes and 1 X 1 tiles:
  ._._.   ._._.   .___.   .___.   ._._.
  |_|_|   | |_|   | ._|   |_. |   |_| |
  |_|_|   |___|   |_|_|   |_|_|   |___|
Square array A(n,k) begins:
  1,  1,   1,     1,       1,        1,          1,            1, ...
  1,  1,   1,     1,       1,        1,          1,            1, ...
  1,  1,   5,    11,      33,       87,        241,          655, ...
  1,  1,  11,    39,     195,      849,       3895,        17511, ...
  1,  1,  33,   195,    2023,    16839,     151817,      1328849, ...
  1,  1,  87,   849,   16839,   249651,    4134881,     65564239, ...
  1,  1, 241,  3895,  151817,  4134881,  128938297,   3814023955, ...
  1,  1, 655, 17511, 1328849, 65564239, 3814023955, 207866584389, ...

Liang Kai, Antidiagonals n = 0..35, flattened (antidiagonals n = 0..29 from Alois P. Heinz)
Kai Liang, Solving tiling enumeration problems by tensor network contractions, arXiv:2503.17698 [math.CO], 2025. See p. 25, Table 4.
Wikipedia, Tromino

Columns (or rows) k=0+1, 2-10 give: A000012, A127864, A127867, A127870, A220055, A220056, A220057, A220058, A220059, A220060.

Main diagonal gives: A220061.

b:= proc(n, l) option remember; local k, t;
      if max(l[])>n then 0 elif n=0 or l=[] then 1
    elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l))
    else for k do if l[k]=0 then break fi od; b(n, subsop(k=1, l))+
         `if`(k>1 and l[k-1]=1, b(n, subsop(k=2, k-1=2, l)), 0)+
         `if`(k `if`(n>=k, b(n, [0$k]), b(k, [0$n])):
seq(seq(A(n, d-n), n=0..d), d=0..14);

b[n_, l_] := b[n, l] = Module[{k, t}, Which[ Max[l] > n , 0, n == 0 || l == {} , 1 , Min[l] > 0 , t := Min[l]; b[n - t, l - t] , True, For[k = 1, True, k++, If[ l[[k]] == 0 , Break[] ] ]; b[n, ReplacePart[l, k -> 1]] + If[k > 1 && l[[k - 1]] == 1, b[n, ReplacePart[l, {k -> 2, k - 1 -> 2}]], 0] + If[k < Length[l] && l[[k + 1]] == 1, b[n, ReplacePart[l, {k -> 2, k + 1 -> 2}]], 0] + If[k < Length[l] && l[[k + 1]] == 0, b[n, ReplacePart[l, {k -> 1, k + 1 -> 2}]] + b[n, ReplacePart[l, {k -> 2, k + 1 -> 1}]] + b[n, ReplacePart[l, {k -> 2, k + 1 -> 2}]], 0] + If[k + 1 < Length[l] && l[[k + 1]] == 0 && l[[k + 2]] == 0, b[n, ReplacePart[l, {k -> 2, k + 1 -> 2, k + 2 -> 2}]], 0] ] ]; a[n_, k_] := If[n >= k, b[n, Array[0 &, k]], b[k, Array[0 &, n]]]; Table [Table [a[n, d - n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 09 2013, translated from Maple *)

A127870 Number of tilings of a 4 X n board with 1 X 1 and L-shaped tiles (where the L-shaped tiles cover 3 squares).

Original entry on oeis.org

1, 1, 33, 195, 2023, 16839, 151817, 1328849, 11758369, 103628653, 914646205, 8068452381, 71189251649, 628067760289, 5541284098945, 48888866203241, 431331449340441, 3805499681885145, 33574725778806817, 296219181642118401, 2613448287490035073

Offset: 0

Silvia Heubach (sheubac(AT)calstatela.edu), Feb 03 2007

nonn

			a(2) = 33 because the 4x2 board can be tiled in one way with only square tiles, in 12 ways using one L-tile and 5 square tiles and in 20 ways with 2 L-tiles and 2 square tiles.

Alois P. Heinz, Table of n, a(n) for n = 0..500
P. Chinn, R. Grimaldi and S. Heubach, Tiling with L's and Squares, Journal of Integer Sequences, Vol. 10 (2007), Article 07.2.8
Index entries for linear recurrences with constant coefficients, signature (5, 34, 6, -72, -28, 74, -10, -4, -4).

Cf. A127864, A127865, A127866, A127867, A127868, A127869.

Column k=4 of A220054. - Alois P. Heinz, Dec 03 2012

Table[Coefficient[Normal[Series[(1 - 4 z - 6 z^2 - 10 z^3 - 8 z^4 - 4 z^5)/(1 - 5z - 34 z^2 - 6 z^3 + 72 z^4 + 28 z^5 - 74 z^6 + 10 z^7 + 4 z^8 + 4 z^9), {x, 0, 30}]], x, n], {n, 0, 30}]

G.f.: (1 - 4 z - 6 z^2 - 10 z^3 - 8 z^4 - 4 z^5) / (1 - 5z - 34 z^2 - 6 z^3 + 72 z^4 + 28 z^5 - 74 z^6 + 10 z^7 + 4 z^8 + 4 z^9).

A127865 Number of square tiles in all tilings of a 2 X n board with 1 X 1 and L-shaped tiles (where the L-shaped tiles cover 3 squares).

Original entry on oeis.org

2, 8, 30, 108, 354, 1152, 3614, 11204, 34170, 103176, 308598, 916236, 2702834, 7929872, 23155182, 67333140, 195082218, 563367960, 1622185958, 4658753564, 13347741666, 38160007200, 108881256414, 310108078116, 881761288154

Offset: 1

Silvia Heubach (sheubac(AT)calstatela.edu), Feb 03 2007

			a(2) = 8 because the 2 X 2 board can be tiled either with 4 squares or with a single L-shaped tile (in four orientations) together with a single square tile and thus all the tilings of the 2 X 2 board contain 8 square tiles.

P. Z. Chinn, R. Grimaldi and S. Heubach, Tiling with Ls and Squares, J. Int. Sequences 10 (2007) #07.2.8.
S. Heubach, Tiling with Ls and Squares, 2005.
Index entries for linear recurrences with constant coefficients, signature (2, 7, -4, -20, -16, -4).

Cf. A127864, A127866, A127867, A127868, A127869, A127870, A127871, A127872.

Table[(2n - 12)(-1)^n + (2/3)((9 - 5Sqrt[3])(1 + Sqrt[3])^n + (9 + 5Sqrt[3])(1 - Sqrt[3])^n) + (n/Sqrt[3])((Sqrt[3] - 1)( 1 + Sqrt[3])^n + (Sqrt[3] + 1)(1 - Sqrt[3])^n), {n, 1, 30}]

a(n) = (2*n - 12)*(-1)^n + (2/3)*((9-5*sqrt(3))*(1+sqrt(3))^n + (9+5*sqrt(3))*(1-sqrt(3))^n) + (n/sqrt(3))*((sqrt(3)-1)*(1+sqrt(3))^n+ (sqrt(3)+1)*(1-sqrt(3))^n).

G.f.: 2*x*(1+2*x)/((1+x)^2*(1-2*x-2*x^2)^2). - Colin Barker, Apr 30 2012

A127866 Number of L-shaped tiles in all tilings of a 2 X n board with 1 X 1 and L-shaped tiles (where the L-shaped tiles cover 3 squares).

Original entry on oeis.org

4, 12, 52, 172, 580, 1852, 5828, 17980, 54788, 165116, 493316, 1463036, 4312068, 12641276, 36887556, 107201532, 310427652, 896045052, 2579017732, 7403843580, 21205303300, 60604891132, 172872744964, 492233179132, 1399272374276

Offset: 2

Silvia Heubach (sheubac(AT)calstatela.edu), Feb 03 2007

			a(2) = 4 because the 2 X 2 board can be tiled either with 4 squares or with a single L-shaped tile (in four orientations) together with a single square tile and thus all the tilings of the 2 X 2 board contain 4 L-shaped tiles.

P. Chinn, R. Grimaldi and S. Heubach, Tiling with L's and Squares, Journal of Integer Sequences, Vol. 10 (2007), Article 07.2.8
Index entries for linear recurrences with constant coefficients, signature (3, 4, -8, -12, -4).

Cf. A127864, A127865, A127867, A127868, A127869, A127870, A127871, A127872.

Table[Coefficient[Normal[Series[4x^2/((1 + x)(1 - 2x - 2x^2)^2), {x, 0, 20}]], x, n], {n, 0, 20}]

a(n) = 4 (-1)^n - (2/9)[(9-5*Sqrt(3))(1+Sqrt(3))^n + (9+5*Sqrt(3))(1-Sqrt(3))^n] - (n/3)[(1-Sqrt(3))(1+Sqrt(3))^n+ (1+Sqrt(3))(1-Sqrt(3))^n].

G.f.: 4x^2/((1+x)(1-2x-2x^2)^2).

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

A127868 Number of square tiles in all tilings of a 3 X n board with 1 X 1 and L-shaped tiles (where the L-shaped tiles cover 3 squares).

Original entry on oeis.org

3, 30, 171, 1044, 5691, 30678, 159891, 821100, 4151511, 20764590, 102880755, 505866804, 2471159019, 12004723878, 58037429739, 279405305676, 1340130574407, 6406579480446, 30536794325547, 145166910196116, 688444702671291, 3257788855054518, 15385512460164963

Offset: 1

Silvia Heubach (sheubac(AT)calstatela.edu), Feb 03 2007

nonn

			a(2) = 30 because the 3 X 2 board can be tiled in one way with only square tiles, in 8 ways using one L-tile and 3 square tiles and in 2 ways with 2 L-tiles, so there are altogether 6 + 8*3 = 30 square tiles in all of the 3x2 tilings.

Robert Israel, Table of n, a(n) for n = 1..1510
P. Z. Chinn, R. Grimaldi and S. Heubach, Tiling with Ls and Squares, J. Int. Sequences 10 (2007) #07.2.8.
S. Heubach, Tiling with Ls and Squares, 2005.
Index entries for linear recurrences with constant coefficients, signature (6,5,-44,-39,2,-29,4,-4).

Cf. A127864, A127865, A127866, A127867, A127869, A127870.

I:=[3,30,171,1044,5691,30678,159891,821100]; [n le 8 select I[n] else 6*Self(n-1)+5*Self(n-2)-44*Self(n-3)-39*Self(n-4)+2*Self(n-5)-29*Self(n-6)+4*Self(n-7)-4*Self(n-8): n in [1..30]]; // Vincenzo Librandi, Dec 23 2015

f:= gfun:-rectoproc({a(n) - 6*a(n-1)-5*a(n-2)+44*a(n-3)+39*a(n-4)-2*a(n-5)+29*a(n-6)-4*a(n-7)+4*a(n-8), a(0) = 0, a(1) = 3, a(2) = 30, a(3) = 171, a(4) = 1044, a(5) = 5691, a(6) = 30678, a(7) = 159891},a(n), remember):
seq(f(n), n=1..40); # Robert Israel, Dec 22 2015

Table[Coefficient[Normal[Series[3x(1-x)^2(1+6x+3x^2)/(1-3x-7x^2+x^3-2x^4)^2, {x, 0, 30}]], x, n], {n, 0, 30}]
LinearRecurrence[{6, 5, -44, -39, 2, -29, 4, -4}, {3, 30, 171, 1044, 5691, 30678, 159891, 821100}, 25] (* Vincenzo Librandi, Dec 23 2015 *)

my(x='x+O('x^100)); Vec(3*x*(1-x)^2*(1+6*x+3*x^2)/(1-3*x-7*x^2+x^3-2*x^4)^2) \\ Altug Alkan, Dec 22 2015

G.f.: 3x(1-x)^2(1+6x+3x^2)/(1-3x-7x^2+x^3-2x^4)^2.

A127869 Number of L-shaped tiles in all tilings of a 3 X n board with 1 X 1 and L-shaped tiles (where the L-shaped tiles cover 3 squares).

Original entry on oeis.org

12, 60, 432, 2348, 13144, 69280, 361012, 1841736, 9286900, 46303316, 228903592, 1123242916, 5477879120, 26572232312, 128302070508, 616985221280, 2956362520140, 14120605179500, 67252176519008, 319477138444252, 1514116534887688, 7160712605686480, 33799490762646948

Offset: 2

Silvia Heubach (sheubac(AT)calstatela.edu), Feb 03 2007

nonn

			a(2) = 12 because the 3 X 2 board can be tiled in one way with only square tiles, in 8 ways using one L-tile and 3 square tiles and in 2 ways with 2 L-tiles, so there are altogether 8 + 2*2 = 12 L-tiles in all of the 3 X 2 tilings.

P. Z. Chinn, R. Grimaldi and S. Heubach, Tiling with Ls and Squares, J. Int. Sequences 10 (2007) #07.2.8.
S. Heubach, Tiling with Ls and Squares, 2005.
Index entries for linear recurrences with constant coefficients, signature (6,5,-44,-39,2,-29,4,-4).

Cf. A127864, A127865, A127866, A127867, A127868, A127870.

Table[Coefficient[Normal[Series[4x^2(3-3x+3x^2-4x^3+x^4)/(1-3x-7x^2+x^3-2x^4)^2, {x, 0, 30}]], x, n], {n, 0, 30}]

G.f.: 4*x^2*(x-1)*(x^3-3*x^2-3)/(1-3*x-7*x^2+x^3-2*x^4)^2.

A353878 Number of tilings of a 3 X n rectangle using right trominoes, dominoes and 1 X 1 tiles.

Original entry on oeis.org

1, 3, 44, 369, 3633, 34002, 323293, 3058623, 28982628, 274494621, 2600148629, 24628666626, 233286962601, 2209723174731, 20930806288252, 198259418947833, 1877940242218857, 17788105074906162, 168491350295593637, 1595972975308532199, 15117273008425964916

Offset: 0

Gerhard Kirchner, May 09 2022

Tiling algorithm see A351322.

			a(2)=44
The number of tilings (mirroring included) using r trominoes
      ___   ___        ___
r=1: |  _| | |_| r=2: |  _| r=0: 22 = A030186(3)
     |_|3| |___|      |_| |
     |___| |_2_|      |___|
      4*3 + 4*2   +    2*1   +   22 = 44
Legend:
   ___              ___      ___
  |_2_| stands for |___| or |_|_|
     _                _        _        _
   _|3|             _| |     _|_|     _|_|
  |___| stands for |_|_| or |___| or |_|_|

Index entries for linear recurrences with constant coefficients, signature (6,33,3,-40,15).

Cf. A030186, A127867, A165716, A351322, A352589, A353877, A353879.

Maxima
```
See A352589.
```

G.f.: (1-3*x-7*x^2+3*x^3-2*x^4) / (1-6*x-33*x^2-3*x^3+40*x^4-15*x^5).

a(n) = 6*a(n-1) + 33*a(n-2) + 3*a(n-3) - 40*a(n-4) + 15*a(n-5).

A337492 a(n) = a(n-1) + 4a(n-3) + 2a(n-4) + 2*a(n-5); a(0) = a(1) = a(2) = 1, a(3) = 5, a(4) = 11.

Original entry on oeis.org

1, 1, 1, 5, 11, 19, 43, 99, 207, 439, 959, 2071, 4439, 9567, 20647, 44463, 95751, 206351, 444631, 957855, 2063687, 4446415, 9579799, 20639519, 44468263, 95807663, 206418167, 444729855, 958176071

Offset: 0

Sujay Champati and Greg Dresden, Aug 29 2020

Number of tilings of a 3 X n rectangle with 1 X 1 squares and L-shaped tiles (where the L-shaped tile covers 5 squares).

			Here is one of the 11 ways to tile a 3 X 4 rectangle:
._______
| |_|_|_|
| |_|_|_|
|_ _ _|_|

Index entries for linear recurrences with constant coefficients, signature (1,0,4,2,2).

Cf. A127864, A127867.

LinearRecurrence[{1, 0, 4, 2, 2}, {1, 1, 1, 5, 11}, 50]

G.f.: 1/(1-x-4*x^3-2*x^4-2*x^5). - R. J. Mathar, Sep 03 2020

Sum_{k=0..n} a(k) = (a(n+3)+4*a(n)+2*a(n-1)-1)/8. - Sujay Champati, Sep 05 2020

cp's OEIS Frontend

A127864 Number of tilings of a 2 X n board with 1 X 1 and L-shaped tiles (where the L-shaped tiles cover 3 squares).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A220054 Number A(n,k) of tilings of a k X n rectangle using right trominoes and 1 X 1 tiles; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A127870 Number of tilings of a 4 X n board with 1 X 1 and L-shaped tiles (where the L-shaped tiles cover 3 squares).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A127865 Number of square tiles in all tilings of a 2 X n board with 1 X 1 and L-shaped tiles (where the L-shaped tiles cover 3 squares).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A127866 Number of L-shaped tiles in all tilings of a 2 X n board with 1 X 1 and L-shaped tiles (where the L-shaped tiles cover 3 squares).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A127868 Number of square tiles in all tilings of a 3 X n board with 1 X 1 and L-shaped tiles (where the L-shaped tiles cover 3 squares).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A127869 Number of L-shaped tiles in all tilings of a 3 X n board with 1 X 1 and L-shaped tiles (where the L-shaped tiles cover 3 squares).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A353878 Number of tilings of a 3 X n rectangle using right trominoes, dominoes and 1 X 1 tiles.

Views

A337492 a(n) = a(n-1) + 4a(n-3) + 2a(n-4) + 2*a(n-5); a(0) = a(1) = a(2) = 1, a(3) = 5, a(4) = 11.