A127870 -id:A127870 - 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 *)

A127867 Number of 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

1, 1, 11, 39, 195, 849, 3895, 17511, 79339, 358397, 1620843, 7326991, 33127155, 149766353, 677103839, 3061202815, 13839823275, 62570318397, 282882722979, 1278922980071, 5782057329219, 26140890761969, 118183916056327, 534313772133687, 2415651952691819

Offset: 0

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

nonn

			a(2) = 11 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.

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 (3, 7, -1, 2).

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

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

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

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

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

A165791 Number of tilings of a 4 X n rectangle using dominoes and right trominoes.

Original entry on oeis.org

1, 1, 11, 55, 380, 2319, 15171, 96139, 619773, 3962734, 25445515, 163048957, 1045897075, 6705473761, 43001795070, 275730928993, 1768128097215, 11337760387473, 72702310606249, 466192677008538, 2989403530821497, 19169143325987983, 122919655766448729

Offset: 0

Alois P. Heinz, Sep 26 2009

			a(2) = 11, because there are 11 tilings of a 4 X 2 rectangle using dominoes and right trominoes:
  .___. .___. .___. ._._. ._._. .___. .___. .___. .___. .___. .___.
  |___| |___| |_._| | | | | | | |___| |___| | ._| |_. | | ._| |_. |
  |___| |_._| | | | |_|_| |_|_| | ._| |_. | |_| | | |_| |_| | | |_|
  |___| | | | |_|_| |___| | | | |_| | | |_| |___| |___| | |_| |_| |
  |___| |_|_| |___| |___| |_|_| |___| |___| |___| |___| |___| |___|  .

Alois P. Heinz, Table of n, a(n) for n = 0..400
Index entries for linear recurrences with constant coefficients, signature (4, 21, -25, -65, -17, 24, -11, -15, 9).

Cf. A165716, A127870, A054854, A226322.

Column k=4 of A219987.

a:= n-> (Matrix([[619773, 96139, 15171, 2319, 380, 55, 11, 1, 1]]). Matrix(9, (i,j)-> if i=j-1 then 1 elif j=1 then [4, 21, -25, -65, -17, 24, -11, -15, 9][i] else 0 fi)^n)[1,9]: seq(a(n), n=0..25);

a[n_] := {619773, 96139, 15171, 2319, 380, 55, 11, 1, 1} . MatrixPower[ Table[ Which[i == j-1, 1, j == 1, {4, 21, -25, -65, -17, 24, -11, -15, 9}[[i]], True, 0], {i, 1, 9}, {j, 1, 9}], n] // Last; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Dec 04 2013, translated and adapted from Alois P. Heinz's Maple program *)

G.f.: (2*x^8-5*x^7+2*x^6-x^5-19*x^4-15*x^3+14*x^2+3*x-1) / (9*x^9-15*x^8-11*x^7+24*x^6-17*x^5-65*x^4-25*x^3+21*x^2+4*x-1).

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.

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

Original entry on oeis.org

1, 5, 189, 3633, 83374, 1817897, 40220893, 886130549, 19546906987, 431024540644, 9505433227293, 209617856008535, 4622624792880217, 101940750143038657, 2248057208102711472, 49575464007447758483, 1093267021618939507743, 24109360928450426884813, 531673668551361276666101

Offset: 0

Gerhard Kirchner, May 09 2022

For tiling algorithm see A351322.

			a(2)=189.
The number of tilings (mirroring included) using r trominoes
      ___   ___   ___   ___
r=1: |  _| |  _| | |_| |_2_|    r=0: 71 = A030186(4)
     |_|_| |_| | |___| |_  |
     | 7 | |3|_| | 7 | |3|_|
     |___| |___| |___| |___|
      4*7 + 4*3 + 4*7 + 4*6 = 92
      ___   ___   ___   ___   ___   ___   ___
r=2: |  _| |  _| |  _| |  _| |  _| | |_| | |_|
     |_| | |_|2| |_|_| |_|_| |_|_| |___| |___|
     |___| | |_| |  _|_|_| | |_  | |_  | |  _|
     |_2_| |___| |_|_| |___| |_|_| |_|_| |_|_|
      4*2 + 2*2 + 4*1 + 2*1 + 4*1 + 2*1 + 2*1 = 26
Result: a(2) = 71+92+26 = 189.
Legend:
   ___              ___      ___
  |_2_| stands for |___| or |_|_|
     _                _        _        _
   _|3|             _| |     _|_|     _|_|
  |___| stands for |_|_| or |___| or |_|_|
   ___              ___   ___   ___   ___   ___   ___      ___
  | 7 |            |___| |_|_| |___| | | | |_| | | |_|    |_|_|
  |___| stands for |___|,|___|,|_|_|,|_|_|,|_|_|,|_|_| or |_|_|

Index entries for linear recurrences with constant coefficients, signature (14,183,-37,-1929,2419,-212,-333,25,15).

Cf. A030186, A127870, A165791, A351322, A352589, A353877, A353878.

Maxima
```
See A352589.
```

G.f.: (1 - 9*x - 64*x^2 + 109*x^3 + 39*x^4 + 41*x^5 + 12*x^6 - 7*x^7 - 2*x^8) / (1 - 14*x - 183*x^2 + 37*x^3 + 1929*x^4 - 2419*x^5 + 212*x^6 + 333*x^7 - 25*x^8-15*x^9).

a(n) = 14*a(n-1) + 183*a(n-2) - 37*a(n-3) - 1929*a(n-4) + 2419*a(n-5) - 212*a(n-6) - 333*a(n-7) + 25*a(n-8) + 15*a(n-9).

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

A127867 Number of 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

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

A165791 Number of tilings of a 4 X n rectangle using dominoes and right trominoes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

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).