A033516 -id:A033516 - cp's OEIS frontend

A287428 Array read by antidiagonals: T(m,n) is the number of matchings in the stacked prism graph C_m X P_n.

1, 2, 3, 3, 12, 4, 5, 47, 32, 7, 8, 185, 228, 108, 11, 13, 728, 1655, 1511, 342, 18, 21, 2865, 11978, 21497, 9213, 1104, 29, 34, 11275, 86731, 305184, 253880, 57536, 3544, 47, 55, 44372, 627960, 4334009, 6974078, 3079253, 356863, 11396, 76

Offset: 1

Andrew Howroyd, May 25 2017

Row 1 is the number of matchings in P_n and row 2 is the number of matchings in G X P_n where G is a double edge. These choices give the best fit with the column linear recurrences.

			Table starts:
======================================================================
m\n|  1    2      3        4          5            6              7
---|------------------------------------------------------------------
1  |  1    2      3        5          8           13             21 ...
2  |  3   12     47      185        728         2865          11275 ...
3  |  4   32    228     1655      11978        86731         627960 ...
4  |  7  108   1511    21497     305184      4334009       61545775 ...
5  | 11  342   9213   253880    6974078    191668283     5267252351 ...
6  | 18 1104  57536  3079253  164206124   8761336545   467431319920 ...
7  | 29 3544 356863 37071837 3834744194 396924243197 41080815923665 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..435
Eric Weisstein's World of Mathematics, Stacked Prism Graph

Rows 2..13 are A088132, A033515, A033516, A033517, A033518, A033519-A033525.
Columns 2..3 are A102080, A102090.
Cf. A028420 (P_m X P_n), A270246 (C_m X C_n), A270227 (K_m X K_n).

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.

A045310 Number of matchings in n-cube.

Original entry on oeis.org

1, 2, 7, 108, 41025, 13803794944, 7174574164703330195841

Offset: 0

Per H. Lundow

a(4) = A033532(1), a(5) = A033532(2).
a(3) = A033516(2) = A033535(2). - Alois P. Heinz, Dec 09 2013
Equivalently, the number of decompositions of an n-dimensional cube of size 2 into (zero or more) unit cubes (1 X 1 X ... X 1) and "dominoes" (2 X 1 X 1 X ... X 1). - Hugo van der Sanden, Nov 30 2016

			From _Max Alekseyev_, Nov 16 2009: (Start)
E.g., for n=2, we have
1 matching of size 0 (i.e., the empty matching)
4 matchings of size 1 (i.e., an edge)
2 matchings of size 2 (that are the perfect matchings).
So a(2) = 1 + 4 + 2 = 7, whereas A005271(2) = 2. (End)

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.
Per Hakan Lundow, GrafPack (Mathematica package).
Hugo van der Sanden, find2: Proof of concept in perl
Hugo van der Sanden, find2c.c: Fast version in C.
Eric Weisstein's World of Mathematics, Hypercube Graph
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching

For perfect matchings see A005271.
For matching polynomials, see A192437, A302235.
Cf. A033532.

C
```
/* See Links section. */
```
Perl
```
# See Links section.
```

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

Original entry on oeis.org

1, 11, 444, 13311, 422617, 13265660, 417336617, 13123557903, 412719195520, 12979269602143, 408175860119021, 12836425011761592, 403683424226081169, 12695147020245034099, 399240466722076292612, 12555423726269799691295, 394846409914451855949249

Offset: 0

Gerhard Kirchner, Jan 30 2023

nonn

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

Index entries for linear recurrences with constant coefficients, signature (26,176,-146,-14,-140,27).

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

Maxima
```
/* See A359884. */
```

G.f.: (1 - 15*x - 18*x^2 - 23*x^3 + 7*x^4) / (1 - 26*x - 176*x^2 + 146*x^3 + 14*x^4 + 140*x^5 - 27*x^6).
Recurrence 1:
a(n) = 11*a(n-1) + 4*b(n-1) + 2*c(n-1) + d(n-1) + e(n-1) + 29*a(n-2) + 6*b(n-2) + c(n-2) + 2*d(n-2),
b(n) = 32*a(n-1) + 9*b(n-1) + 4*c(n-1) + 2*d(n-1) + e(n-1),
c(n) = 52*a(n-1) + 14*b(n-1) + 5*c(n-1) + 4*d(n-1) + 2*e(n-1),
d(n) = 14*a(n-1) + 3*b(n-1) + d(n-1),
e(n) = 48*a(n-1) + 11*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) = 26*a(n-1) + 176*a(n-2) - 146*a(n-3) - 14*a(n-4) - 140*a(n-5) + 27*a(n-6) for n >= 6. For n < 6, recurrence 1 can be used.

A360575 Number of 3-dimensional tilings of a 2 X 2 X n box using 1 X 1 X 1 cubes, 2 X 1 X 1 dominos and 2 X 2 X 1 plates.

Original entry on oeis.org

1, 8, 153, 2470, 41571, 693850, 11602579, 193942076, 3242104149, 54196828452, 905988148597, 15145052657186, 253174020910071, 4232212575080006, 70748267813548207, 1182671546039152712, 19770264765434877913, 330491902143708738464

Offset: 0

Gerhard Kirchner, Feb 12 2023

nonn

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

Index entries for linear recurrences with constant coefficients, signature (16,21,-157,100,65,-42).

Cf. A006253, A001045, A033516, A335559, A359884, A359885, A360064, A360065, A360576, A360577.

G.f.: (1-8*x+4*x^2+11*x^3-6*x^4) / (1-16*x-21*x^2+157*x^3-100*x^4-65*x^5+42*x^6).
Recurrence 1:
a(n) = 8*a(n-1) + 3*b(n-1) + 2*c(n-1) + d(n-1) + e(n-1) + 7*a(n-2)
b(n) = 12*a(n-1) + 5*b(n-1) + 2*c(n-1) + 2*d(n-1) + e(n-1)
c(n) = 16*a(n-1) + 4*b(n-1) + 2*c(n-1)
d(n) = 2*a(n-1) + b(n-1) + d(n-1)
e(n) = 12*a(n-1) + 3*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)=16*a(n-1) + 21*a(n-2) - 157*a(n-3) + 100*a(n-4) + 65*a(n-5) - 42*a(n-6)
for n>=6. For n<6, recurrence 1 can be used.

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

Original entry on oeis.org

1, 6, 122, 1768, 28844, 457592, 7318760, 116806896, 1865305376, 29782666544, 475549098160, 7593154541264, 121241257906000, 1935879286697296, 30910512661708432, 493553365105565264, 7880649886335326608, 125831666350680625104

Offset: 0

Gerhard Kirchner, Feb 12 2023

nonn

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

Index entries for linear recurrences with constant coefficients, signature (15,28,-214,192,384,-128).

Cf. A006253, A001045, A033516, A335559, A359884, A359885, A360064, A360065, A360575, A360577.

G.f.: (1-9*x+4*x^2-16*x^3) / (1-15*x-28*x^2+214*x^3-192*x^4-384*x^5+128*x^6).
Recurrence 1:
a(n) = 8*a(n-1) + 3*b(n-1) + 2*c(n-1) + d(n-1) + e(n-1) + 7*a(n-2)
b(n) = 12*a(n-1) + 5*b(n-1) + 2*c(n-1) + 2*d(n-1) + e(n-1)
c(n) = 16*a(n-1) + 4*b(n-1) + 2*c(n-1)
d(n) = 2*a(n-1) + b(n-1) + d(n-1)
e(n) = 12*a(n-1) + 3*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)=15*a(n-1) + 28*a(n-2) - 214*a(n-3) + 192*a(n-4) + 384*a(n-5) - 128*a(n-6)
for n>=6. For n<6, recurrence 1 can be used.

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

Original entry on oeis.org

1, 3, 60, 657, 8311, 101284, 1246049, 15292819, 187803572, 2305968393, 28315208039, 347681742812, 4269186204201, 52421329940803, 643681521419708, 7903765218510353, 97050331862075975, 1191681006432895780, 14632650860374551265, 179674317212728197891, 2206220907971874345652

Offset: 0

Gerhard Kirchner, Feb 12 2023

nonn

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

Index entries for linear recurrences with constant coefficients, signature (8,51,27,-96,-43,66).

Cf. A006253, A001045, A033516, A335559, A359884, A359885, A360064, A360065, A360575, A360576.

G.f.: (1-5*x-15*x^2-3*x^3+10*x^4) / (1-8*x-51*x^2-27*x^3+96*x^4+43*x^5-66*x^6).
Recurrence 1:
a(n) = 3*a(n-1) + b(n-1) + c(n-1) + 19*a(n-2) + 4*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) = 20*a(n-1) + 6*b(n-1) + 2*c(n-1) + 2*e(n-1)
d(n) = 4*a(n-1) + 2*b(n-1) + d(n-1)
e(n) = 24*a(n-1) + 7*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)=8*a(n-1) + 51*a(n-2) + 27*a(n-3) - 96*a(n-4) - 43*a(n-5) + 66*a(n-6)
for n>=6. For n<6, recurrence 1 can be used.

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

Original entry on oeis.org

1, 12, 513, 16194, 547543, 18234354, 609298887, 20344385080, 679408772089, 22688284005780, 757662377924917, 25301659203704234, 844933359518672599, 28216027727373068302, 942256839186226313727, 31466085716246304261600, 1050790517091131646143477

Offset: 0

Gerhard Kirchner, Feb 15 2023

nonn

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

Index entries for linear recurrences with constant coefficients, signature (28,195,-497,30,-79,66).

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

G.f.: (1-16*x-18*x^2-13*x^3+10*x^4) / (1-28*x-195*x^2+497*x^3-30*x^4+79*x^5-66*x^6)
Recurrence 1:
a(n) = 12*a(n-1) + 4*b(n-1) + 2*c(n-1) + d(n-1) + e(n-1) + 43*a(n-2) + 8*b(n-2) + c(n-2) + 2*d(n-2)
b(n) = 32*a(n-1) + 9*b(n-1) + 4*c(n-1) + 2*d(n-1) + e(n-1)
c(n) = 60*a(n-1) + 16*b(n-1) + 6*c(n-1) + 4*d(n-1) + 2*e(n-1)
d(n) = 14*a(n-1) + 3*b(n-1) + d(n-1)
e(n) = 64*a(n-1) + 13*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)=28*a(n-1) + 195*a(n-2) - 497*a(n-3) + 30*a(n-4) - 79*a(n-5) + 66*a(n-6)
for n>=6. For n<6, recurrence 1 can be used.

cp's OEIS Frontend

A287428 Array read by antidiagonals: T(m,n) is the number of matchings in the stacked prism graph C_m X P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

A045310 Number of matchings in n-cube.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Perl

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maxima

Formula

A360575 Number of 3-dimensional tilings of a 2 X 2 X n box using 1 X 1 X 1 cubes, 2 X 1 X 1 dominos and 2 X 2 X 1 plates.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

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

Views

Author

Keywords