A006253 -id:A006253 - cp's OEIS frontend

A263816 T(n,k)=Number of (n+1)X(k+1) arrays of permutations of 0..(n+1)*(k+1)-1 with each element having index change (+-,+-) 0,0 0,1 0,2 or 1,0.

9, 82, 32, 572, 948, 121, 3682, 18776, 11305, 450, 25001, 333429, 643905, 134028, 1681, 170946, 6425985, 31916832, 21876416, 1590733, 6272, 1157993, 124854432, 1746531193, 3019386508, 744805993, 18875976, 23409, 7844192, 2392853088

Offset: 1

R. H. Hardin, Oct 27 2015

Table starts
......9.........82..........572...........3682...........25001.........170946
.....32........948........18776.........333429.........6425985......124854432
....121......11305.......643905.......31916832......1746531193....96761217077
....450.....134028.....21876416.....3019386508....469723808009.74221751084228
...1681....1590733....744805993...286407546797.126619013196417
...6272...18875976..25345430544.27150876030959
..23409..223995034.862592912860
..87362.2658056430
.326041

			Some solutions for n=2 k=4
..0..1..3..2..4....0..3..2..8..4....0..6..2..8..4....0..3..2..8..4
..5..6..7..8..9....6..1.12..9..7....7..1..9..3.14....5..1..9..6..7
.12.10.11.14.13....5.10.13.11.14....5.11.10.13.12...12.10.11.14.13

R. H. Hardin, Table of n, a(n) for n = 1..49

Column 1 is A006253(n+1).

Empirical for column k:
k=1: a(n) = 3*a(n-1) +3*a(n-2) -a(n-3)
k=2: a(n) = 10*a(n-1) +23*a(n-2) -10*a(n-3) -a(n-4)
k=3: [order 15]
k=4: [order 82]
Empirical for row n:
n=1: [linear recurrence of order 26]

A233308 Number A(n,k) of tilings of a k X k X n box using k*n bricks of shape k X 1 X 1; square array A(n,k), n>=0, k>=1, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 9, 1, 1, 2, 4, 32, 1, 1, 2, 4, 21, 121, 1, 1, 2, 4, 8, 92, 450, 1, 1, 2, 4, 8, 45, 320, 1681, 1, 1, 2, 4, 8, 16, 248, 1213, 6272, 1, 1, 2, 4, 8, 16, 93, 1032, 4822, 23409, 1, 1, 2, 4, 8, 16, 32, 668, 3524, 18556, 87362, 1, 1, 2, 4, 8, 16, 32, 189, 3440, 13173, 70929, 326041, 1

Offset: 0

Alois P. Heinz, Dec 07 2013

			Square array A(n,k) begins:
  1,     1,     1,     1,     1,     1, ...
  1,     2,     2,     2,     2,     2, ...
  1,     9,     4,     4,     4,     4, ...
  1,    32,    21,     8,     8,     8, ...
  1,   121,    92,    45,    16,    16, ...
  1,   450,   320,   248,    93,    32, ...
  1,  1681,  1213,  1032,   668,   189, ...
  1,  6272,  4822,  3524,  3440,  1832, ...
  1, 23409, 18556, 13173, 13728, 11976, ...

Alois P. Heinz, Antidiagonals n = 0..17, flattened

Columns k=1-6 give: A000012, A006253, A233289, A233291, A233294, A233424.

Diagonals include: A000079, A068156.

b:= proc(n, l) option remember; local d, t, k; d:= isqrt(nops(l));
      if max(l[])>n then 0 elif n=0 then 1
    elif min(l[])>0 then t:=min(l[]); b(n-t, map(x->x-t, l))
    else for k while l[k]>0 do od; b(n, subsop(k=d, l))+
         `if`(irem(k,d)=1 and {seq(l[k+j], j=1..d-1)}={0},
         b(n, [seq(`if`(h-k=0, 1, l[h]), h=1..nops(l))]), 0)+
         `if`(k<=d and {seq(l[k+d*j], j=1..d-1)}={0},
         b(n, [seq(`if`(irem(h-k, d)=0, 1, l[h]), h=1..nops(l))]), 0)
      fi
    end:
A:= (n, k)-> `if`(k>n, 2^n, b(n, [0$k^2])):
seq(seq(A(n, 1+d-n), n=0..d), d=0..11);

b[n_, l_] := b[n, l] = Module[{d, t, k}, d= Sqrt[Length[l]]; Which[ Max[l]>n, 0, n==0, 1, Min[l]>0, t=Min[l]; b[n-t, l-t], True, k=Position[l, 0, 1][[1, 1]]; b[n, ReplacePart[l, k->d]]+ If[Mod[k, d]==1 && Union[ Table[ l[[k+j]], {j, 1, d-1}]] == {0}, b[n, Table[ If [h-k=0, 1, l[[h]] ], {h, 1, Length[l]}]], 0]+ If[k <= d && Union[ Table[ l[[k+d*j]], {j, 1, d-1}]] == {0}, b[n, Table[ If[ Mod[h-k, d] == 0, 1, l[[h]] ], {h, 1, Length[l]}]], 0] ] ]; a[n_, k_]:= If[k>n, 2^n, b[n, Array[0&, k^2]]]; Table[Table[a[n, 1+d-n], {n, 0, d}], {d, 0, 11}] // Flatten (* Jean-François Alcover, Dec 13 2013, translated from Maple *)

A(n,k) = 2^n = A000079(n) for k>n.

A(n,n) = A068156(n) for n>1.

A360064 Number of 3-dimensional tilings of a 2 X 2 X n box using 1 X 1 X 1 cubes and trominos (L-shaped connection of 3 cubes).

Original entry on oeis.org

1, 5, 89, 1177, 16873, 237977, 3366793, 47599097, 673035625, 9516252633, 134553882441, 1902506043833, 26900227288361, 380352114739609, 5377937177440009, 76040613721296249, 1075165950495479017, 15202163218500810073, 214948926180739194569

Offset: 0

Gerhard Kirchner, Jan 30 2023

Recurrence 1 is derived in A359884, "3d-tilings of a 2 X 2 X n box" as a special case of a more general tiling problem: III, example 8.

			4 rotations:
   ___ ___     ___ ___
  |   |   |   |   |   | (cross sections)
  |   |___|   |___|___|
  |       |   |   |   |
  |_______|   |___|___| a(1) = 4 + 1 = 5.

Paolo Xausa, Table of n, a(n) for n = 0..850
Index entries for linear recurrences with constant coefficients, signature (13,20,-64,112,224,-128).

Cf. A006253, A001045, A033516, A335559, A359885, A359886, A360065, A360066.

LinearRecurrence[{13, 20, -64, 112, 224, -128}, {1, 5, 89, 1177, 16873, 237977}, 25] (* Paolo Xausa, Oct 02 2024 *)

G.f.: (1 - 8*x + 4*x^2 - 16*x^3) / (1 - 13*x - 20*x^2 + 64*x^3 - 112*x^4 - 224*x^5 + 128*x^6).
Recurrence 1:
a(n) = 5*a(n-1) + 2*b(n-1) + c(n-1) + d(n-1) + e(n-1) + 8*a(n-2) + 4*b(n-2) + c(n-2) + 2*d(n-2),
b(n) = 8*a(n-1) + 4*b(n-1) + 2*c(n-1),
c(n) = 20*a(n-1) + 6*b(n-1) + 4*c(n-1) + 4*d(n-1) + 2*e(n-1),
d(n) = 4*a(n-1), e(n) = 16*a(n-1) + 4*b(n-1),
with a(n), b(n), c(n), d(n), e(n) = 0 for n <= 0 except for a(0)=1.
Recurrence 2:
a(n) = 13*a(n-1) + 20*a(n-2) - 64*a(n-3) + 112*a(n-4) + 224*a(n-5) - 128*a(n-6) for n >= 6. For n < 6, recurrence 1 can be used.

A360065 Number of 3-dimensional tilings of a 2 X 2 X n box using 2 X 1 X 1 dominos and trominos (L-shaped connection of 3 cubes).

Original entry on oeis.org

1, 2, 45, 412, 4705, 50374, 549109, 5955544, 64683649, 702259786, 7625147293, 82791470836, 898931464993, 9760376329678, 105975828745957, 1150659965697328, 12493588746237697, 135652375422278290, 1472880803124594061, 15992184812239930060, 173639288800074705121

Offset: 0

Gerhard Kirchner, Jan 30 2023

Recurrence 1 is derived in A359884, "3d-tilings of a 2 X 2 X n box" as a special case of a more general tiling problem: III, example 9.

			a(2)=45
1) Two parallel trominos and one domino: There are 3 middle axes of the 2 X 2 cube with 4 rotation images each: 12 images.
       ___             ___         ___ ___
     /__ /|          /   /|      /__ /   /|
   /__ /| |___     /__ /  |    /__ /__ /  |
  |   | |/__ /|   |   |  /    |   |   |  /|
  |   |/__ /| | + |___|/   =  |   |___|/| |
  |       | |/                |       | |/
  |_______|/                  |_______|/
2) Two "linked" trominos and one domino: 12 rotation images and, as there is no symmetry plane, 12 mirror images: 24 images.
       ___                       ___         ___ ___
     /   /|                    /   /|      /   /   /|
   /__ /  |      _______     /__ /  |    /__ /__ /  |
  |   |  /     /__     /|   |   |  /    |   |   |  /|
  |   | |  +  |  /__ /  | + |___|/   =  |   |___|/  |
  |   | |     |_|   |  /                |   |   |  /
  |___|/        |___|/                  |___|___|/
3) Using only dominos: A006253(2)=9 ways, Sum: a(2) = 12 + 24 + 9 = 45.

Paolo Xausa, Table of n, a(n) for n = 0..950
Index entries for linear recurrences with constant coefficients, signature (7,42,6,-81,27).

Cf. A006253, A001045, A033516, A335559, A359884, A359885, A360064, A360066.

LinearRecurrence[{7, 42, 6, -81, 27}, {1, 2, 45, 412, 4705}, 25] (* Paolo Xausa, Oct 02 2024 *)

G.f.: (1 - 5*x - 11*x^2 + 7*x^3) / (1 - 7*x - 42*x^2 - 6*x^3 + 81*x^4 - 27*x^5).
Recurrence 1:
a(n) = 2*a(n-1) + b(n-1) + c(n-1) + 13*a(n-2) + 2*b(n-2) + c(n-2) + 2*d(n-2),
b(n) = 12*a(n-1) + 2*b(n-1) + 2*c(n-1) + e(n-1),
c(n) = 16*a(n-1) + 6*b(n-1) + c(n-1) + 2*e(n-1),
d(n) = 4*a(n-1) + 2*b(n-1) + d(n-1),
e(n) = 16*a(n-1) + 5*b(n-1) + 2*c(n-1) + 2*d(n-1),
with a(n), b(n), c(n), d(n), e(n) = 0 for n <= 0 except for a(0)=1.
Recurrence 2:
a(n) = 7*a(n-1) + 42*a(n-2) + 6*a(n-3) - 81*a(n-4) + 27*a(n-5) for n >= 5.
  For n < 5, recurrence 1 can be used.

A233289 Number of tilings of a 3 X 3 X n box using 3n bricks of shape 3 X 1 X 1.

Original entry on oeis.org

1, 2, 4, 21, 92, 320, 1213, 4822, 18556, 70929, 273808, 1057020, 4069737, 15676666, 60424640, 232846801, 897164316, 3457096532, 13321674833, 51332757274, 197801848744, 762200458321, 2937024077340, 11317358546188, 43609682555721, 168043191679374

Offset: 0

Alois P. Heinz, Dec 06 2013

This is a variant of the Jenga game (see link).

Alois P. Heinz, Table of n, a(n) for n = 0..1000
R. J. Mathar, Tilings of rectangular regions by rectangular tiles: counts derived from transfer matrices, arXiv:1406.7788 [math.CO], 2014; eq. (40).
Wikipedia, Jenga
Index entries for linear recurrences with constant coefficients, signature (3,0,13,2,-11,-7,4,-3,1,-1)

Column k=3 of A233308.

Cf. A006253, A233291, A233294, A273474.

gf:= (x^7-x^6+x^5-x^4+4*x^3+2*x^2+x-1)/(-x^10+x^9
     -3*x^8+4*x^7-7*x^6-11*x^5+2*x^4+13*x^3+3*x-1):
a:= n-> coeff(series(gf, x, n+1), x, n):
seq(a(n), n=0..30);

G.f.: (x^7 -x^6 +x^5 -x^4 +4*x^3 +2*x^2 +x -1) / (-x^10 +x^9 -3*x^8 +4*x^7 -7*x^6 -11*x^5 +2*x^4 +13*x^3 +3*x -1).

A028452 Number of perfect matchings in graph P_{3} X P_{3} X P_{2n}.

Original entry on oeis.org

1, 229, 117805, 64647289, 35669566217, 19690797527709, 10870506600976757, 6001202979497804657, 3313042830624031354513, 1829008840116358153050197, 1009728374600381843221483965, 557433823481589253332775648233, 307738670509229621147710358375321

Offset: 0

Per H. Lundow

nonn

Also the number of tilings of a 3 x 3 x 2n box with 1 x 1 x 2 bricks. - Johan de Ruiter, Jul 15 2012

Alois P. Heinz, Table of n, a(n) for n = 0..300
Per Hakan Lundow, Computation of matching polynomials and the number of 1-factors in polygraphs, Research report, No 12, 1996, Department of Math., Umea University, Sweden.
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
R. J. Mathar, Tilings of rectangular regions by rectangular tiles: Counts derived from transfer matrices, arXiv:1406.7788 [math.CO], (2014), eq (38).
James Propp, A reciprocity theorem for domino tilings, El. J. Combin. 8 (2001) #R18.
J. de Ruiter, Counting Domino Coverings and Chessboard Cycles, 2010. [Broken link]

Cf. A006253, A028454, A049507.

From Johan de Ruiter, Jul 15 2012: (Start)
a(n) = 679a(n-1) -76177a(n-2) +3519127a(n-3) -85911555a(n-4) +1235863045a(n-5) -11123194131a(n-6) +65256474997a(n-7) -257866595482a(n-8) +705239311926a(n-9) -1363115167354a(n-10) +1888426032982a(n-11) -1888426032982a(n-12) +1363115167354a(n-13) -705239311926a(n-14) +257866595482a(n-15) -65256474997a(n-16) +11123194131a(n-17) -1235863045a(n-18) +85911555a(n-19) -3519127a(n-20) +76177a(n-21) -679a(n-22) +a(n-23).
G.f.: (x^18 -446x^17 +36701x^16 -1267416x^15 +22828288x^14 -235207768x^13 +1443564488x^12 -5338083112x^11 +11818867674x^10 -15460884436x^9 +11818867674x^8 -5338083112x^7 +1443564488x^6 -235207768x^5 +22828288x^4 -1267416x^3 +36701x^2 -446x +1)/(-x^19 +675x^18 -73471x^17 +3221189x^16 -72583272x^15 +925908264x^14 -6971103216x^13 +31523058272x^12 -86171526770x^11 +142604534086x^10 -142604534086x^9 +86171526770x^8 -31523058272x^7 +6971103216x^6 -925908264x^5 +72583272x^4 -3221189x^3 +73471x^2 -675x +1).
(End)

A233291 Number of tilings of a 4 X 4 X n box using 4n bricks of shape 4 X 1 X 1.

Original entry on oeis.org

1, 2, 4, 8, 45, 248, 1032, 3524, 13173, 54274, 228712, 917992, 3608665, 14286188, 57438652, 231343468, 926921081, 3700936774, 14793198332, 59241396140, 237333611629, 950127617692, 3801974385964, 15215432779936, 60907523900693, 243826775063490, 976008753961184

Offset: 0

Alois P. Heinz, Dec 06 2013

Alois P. Heinz, Table of n, a(n) for n = 0..1000
R. J. Mathar, Tilings of rectangular regions by rectangular tiles: counts derived from transfer matrices, arXiv:1406.7788 [math.CO], 2014; eq. (52).

Column k=4 of A233308.

Cf. A006253, A233289, A233294.

G.f.: (x^31 -x^30 -x^29 -3*x^28 -5*x^27 +8*x^26 +3*x^25 -39*x^24 +48*x^23 +34*x^22 -11*x^21 +112*x^20 -63*x^19 -34*x^18 +166*x^17 -188*x^16 -174*x^15 +151*x^14 -251*x^13 +57*x^12 +104*x^11 +171*x^10 -69*x^9 -90*x^8 -30*x^7 -61*x^6 +20*x^5 +31*x^4 +4*x^3 +4*x^2 +x -1) / (-x^35 +x^34 +x^33 +5*x^32 +4*x^31 -11*x^30 -10*x^29 +54*x^28 -65*x^27 -48*x^26 -48*x^25 -195*x^24 +231*x^23 -78*x^22 -473*x^21 +794*x^20 +447*x^19 -981*x^18 +1285*x^17 +395*x^16 -720*x^15 -202*x^14 +640*x^13 +567*x^12 -232*x^11 +638*x^10 -169*x^9 -233*x^8 -256*x^7 -97*x^6 +29*x^5 +52*x^4 -4*x^3 +2*x^2 +3*x -1).

A233294 Number of tilings of a 5 X 5 X n box using 5n bricks of shape 5 X 1 X 1.

Original entry on oeis.org

1, 2, 4, 8, 16, 93, 668, 3440, 13728, 46252, 172577, 739002, 3417464, 15550336, 65956764, 271247405, 1119519052, 4726308568, 20348072952, 87598217268, 373660404281, 1581318625634, 6680851858676, 28326586367464, 120536842633616, 513461699313993

Offset: 0

Alois P. Heinz, Dec 06 2013

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Alois P. Heinz, G.f. for A233294

Column k=5 of A233308.

Cf. A006253, A233289, A233291.

G.f.: see link above.

A359886 Number of 3-dimensional tilings of a 2 X 2 X n box using 2 X 2 X 1 plates and trominos (three 1 X 1 X 1 cubes).

Original entry on oeis.org

1, 1, 3, 49, 231, 789, 4771, 27225, 122799, 607469, 3255979, 16253649, 80098519, 409480005, 2079921395, 10411734921, 52523676351, 266059774429, 1341128940795, 6758479842689, 34138205819239, 172324729379509, 869131661400259, 4386075013348025, 22138673661637327

Offset: 0

Gerhard Kirchner, Jan 20 2023

Recurrence 1 is derived in A359884, "3d-tilings of a 2 X 2 X n box" as a special case of a more general tiling problem: III, example 6.

			a(3) = 49.
The number of tilings only using plates is A001045(3) = 5.
The number of tilings only using trominos is A359885(1) = 44.
These terms are to be added as, for n=3, there is no tiling using both tiles.

Paolo Xausa, Table of n, a(n) for n = 0..1000
Gerhard Kirchner, Maxima code
Index entries for linear recurrences with constant coefficients, signature (2,1,58,72,32,-128).

Cf. A006253, A001045, A335559, A359884, A359885.

LinearRecurrence[{2, 1, 58, 72, 32, -128}, {1, 1, 3, 49, 231, 789}, 30] (* Paolo Xausa, Jun 24 2024 *)

Maxima
```
/* See link "Maxima code". */
```

G.f.: (1 - x - 16*x^3) / (1 - 2*x - x^2 - 58*x^3 - 72*x^4 - 32*x^5 + 128*x^6).
Recurrence 1:
a(n) = a(n-1) + 3*c(n-2) + 2*a(n-2) + 4*c(n-3) + 8*a(n-3),
c(n) = 12*a(n-1) + c(n-1) + 16*a(n-2) + 16*c(n-3),
with a(n),c(n) <= 0 for n <= 0 except for a(0)=1.
Recurrence 2:
a(n) = 2*a(n-1) + a(n-2) + 58*a(n-3) + 72*a(n-4) + 32*a(n-5) - 128*a(n-6) for n >= 6.
For n < 6, recurrence 1 can be used.

A028454 Number of perfect matchings in graph P_{4} X P_{4} X P_{n}.

Original entry on oeis.org

1, 36, 32000, 10885344, 5051532105, 2132137503232, 932814464901633, 403325499406267520, 175220727982196365632, 75996591204223021534740, 32983893365927357595999561, 14312021563707748863632803328, 6210770058902782255142931025577

Offset: 0

Per H. Lundow

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..100
Per Hakan Lundow, Computation of matching polynomials and the number of 1-factors in polygraphs, Research report, No 12, 1996, Department of Math., Umea University, Sweden.
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.

Cf. A006253, A028452, A049507.

cp's OEIS Frontend

A263816 T(n,k)=Number of (n+1)X(k+1) arrays of permutations of 0..(n+1)*(k+1)-1 with each element having index change (+-,+-) 0,0 0,1 0,2 or 1,0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A233308 Number A(n,k) of tilings of a k X k X n box using k*n bricks of shape k X 1 X 1; square array A(n,k), n>=0, k>=1, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A360064 Number of 3-dimensional tilings of a 2 X 2 X n box using 1 X 1 X 1 cubes and trominos (L-shaped connection of 3 cubes).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A360065 Number of 3-dimensional tilings of a 2 X 2 X n box using 2 X 1 X 1 dominos and trominos (L-shaped connection of 3 cubes).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A233289 Number of tilings of a 3 X 3 X n box using 3n bricks of shape 3 X 1 X 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A028452 Number of perfect matchings in graph P_{3} X P_{3} X P_{2n}.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A233291 Number of tilings of a 4 X 4 X n box using 4n bricks of shape 4 X 1 X 1.

Views

Author

Keywords

Links

Crossrefs

Formula

A233294 Number of tilings of a 5 X 5 X n box using 5n bricks of shape 5 X 1 X 1.

Views

Author

Keywords

Links

Crossrefs

Formula

A359886 Number of 3-dimensional tilings of a 2 X 2 X n box using 2 X 2 X 1 plates and trominos (three 1 X 1 X 1 cubes).

Views

Author

Keywords

Comments