A181206 -id:A181206 - cp's OEIS frontend

A006253 Number of perfect matchings (or domino tilings) in C_4 X P_n.

1, 2, 9, 32, 121, 450, 1681, 6272, 23409, 87362, 326041, 1216800, 4541161, 16947842, 63250209, 236052992, 880961761, 3287794050, 12270214441, 45793063712, 170902040409, 637815097922, 2380358351281, 8883618307200, 33154114877521, 123732841202882

Offset: 0

N. J. A. Sloane

Number of tilings of a box with sides 2 X 2 X n in R^3 by boxes of sides 2 X 1 X 1 (3-dimensional dominoes). - Frans J. Faase
The number of domino tilings in A006253, A004003, A006125 is the number of perfect matchings in the relevant graphs. There are results of Jockusch and Ciucu that if a planar graph has a rotational symmetry then the number of perfect matchings is a square or twice a square - this applies to these 3 sequences. - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 12 2001
Also stacking bricks.
a(n)*(-1)^n = (1-T(n+1,-2))/3, n>=0, with Chebyshev's polynomials T(n,x) of the first kind, is the r=-2 member of the r-family of sequences S_r(n) defined in A092184 where more information can be found. - Wolfdieter Lang, Oct 18 2004
Partial sums of A217233. - Bruno Berselli, Oct 01 2012
The sequence is the case P1 = 2, P2 = -8, Q = 1 of the 3 parameter family of 4th-order linear divisibility sequences found by Williams and Guy. - Peter Bala, Apr 03 2014

			G.f. = 1 + 2*x + 9*x^2 + 32*x^3 + 121*x^4 + 450*x^5 + ... - _Michael Somos_, Mar 17 2022

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 360.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
S. Butler and S. Osborne, Counting tilings by taking walks, preprint, 2012; J. Combin. Math. Combin. Comput. 88 2014 17-25. - From _N. J. A. Sloane_, Dec 27 2012
M. Ciucu, Enumeration of perfect matchings in graphs with reflective symmetry, J. Combin. Theory Ser. A 77 (1997), no. 1, 67-97
D. Deford, Seating rearrangements on arbitrary graphs, preprint 2013; involve, Vol. 7 (2014), No. 6, 787-805.
F. Faase, Counting Hamiltonian cycles in product graphs
F. Faase, Results from the counting program
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
Charles H. Jepsen, Packing a box with bricks, Math. Mag. 64 (2) (1991) 92-97, Table 1
W. Jockusch, Perfect matchings and perfect squares J. Combin. Theory Ser. A 67 (1994), no. 1, 100-115.
R. J. Mathar, Tilings of rectangular regions by rectangular tiles: Counts derived from transfer matrices, arXiv:1406.7788 (2014), eq. (36).
Valcho Milchev and Tsvetelina Karamfilova, Domino tiling in grid - new dependence, arXiv:1707.09741 [math.HO], 2017.
László Németh, Tilings of (2 X 2 X n)-board with colored cubes and bricks, arXiv:1909.11729 [math.CO], 2019.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Radovan Potůček, The number of fillings a 2 X 2 X n prism with 1 X 1 X 2 prisms, Equations (2024) Vol. 3, 104-114.
H. C. Williams and R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory 7 (5) (2011) 1255-1277.
H. C. Williams and R. K. Guy, Some Monoapparitic Fourth Order Linear Divisibility Sequences Integers, Volume 12A (2012) The John Selfridge Memorial Volume
Index entries for sequences related to dominoes
Index entries for sequences related to bricks
Index entries for linear recurrences with constant coefficients, signature (3,3,-1).

Cf. A002530, A004003, A006125, A217233 (first differences), A109437 (partial sums).
Column k=2 of A181206, A189650, A233308.
Cf. A100047.

a:=[1,2,9];; for n in [4..30] do a[n]:=3*a[n-1]+3*a[n-2]-a[n-3]; od; a; # G. C. Greubel, Nov 16 2018

m:=30; R:=PowerSeriesRing(Integers(), m); Coefficients(R!((1-x)/(1-3*x-3*x^2+x^3))); // G. C. Greubel, Nov 16 2018

CoefficientList[Series[(1 - x)/(1 - 3 x - 3 x^2 + x^3), {x, 0, 30}], x] (* Vincenzo Librandi, Oct 15 2012 *)
RecurrenceTable[{a[1] == 1, a[2] == 2, a[n] == BitXor[1, a[n - 1]]^2/a[n - 2]}, a, {n, 30}] (* Jon Maiga, Nov 16 2018 *)
LinearRecurrence[{3,3,-1}, {1,2,9}, 30] (* G. C. Greubel, Nov 16 2018 *)
a[ n_] := (-1)^n * ChebyshevU[n, Sqrt[-1/2]]^2; (* Michael Somos, Mar 17 2022 *)

a(n)=(sqrt(3)+2)^(n+1) \/ 6 \\ Charles R Greathouse IV, Aug 18 2016

a(n)=([0,1,0; 0,0,1; -1,3,3]^n*[1;2;9])[1,1] \\ Charles R Greathouse IV, Aug 18 2016

Vec((1 - x) / ((1 + x)*(1 - 4*x + x^2)) + O(x^40)) \\ Colin Barker, Dec 16 2017

{a(n) = simplify((-1)^n * polchebyshev(n, 2, quadgen(-8)/2)^2)}; /* Michael Somos, Mar 17 2022 */

s=((1-x)/(1-3*x-3*x^2+x^3)).series(x,30); s.coefficients(x, sparse=False) # G. C. Greubel, Nov 16 2018

G.f.: (1-x)/((1+x)*(1-4*x+x^2)) = (1-x)/(1-3*x-3*x^2+x^3). - Simon Plouffe in his 1992 dissertation; typo corrected by Vincenzo Librandi, Oct 15 2012
Nearest integer to (1/6)*(2+sqrt(3))^(n+1). - Don Knuth, Jul 15 1995
For n >= 4, a(n) = 3a(n-1) + 3a(n-2) - a(n-3). - Avi Peretz (njk(AT)netvision.net.il), Mar 30 2001
For n >= 3, a(n) = 4a(n-1) - a(n-2) + 2*(-1)^n. - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 14 2001
From Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 11 2001: The values are a(1) = 2 * 1^2, a(2) = 3^2, a(3) = 2 * 4^2, a(4) = 11^2, a(5) = 2 * 15^2, ... and in general for odd n a(n) is twice a square, for even n a(n) is a square. If we define b(n) by b(n) = sqrt(a(n)) for even n, b(n) = sqrt(a(n)/2) for odd n then apart from the first 2 elements b(n) is A002530(n+1).
a(n) + a(n+1) = A001835(n+2). - R. J. Mathar, Dec 06 2013
From Peter Bala, Apr 03 2014: (Start)
a(n) = |U(n,i/sqrt(2))|^2 where U(n,x) denotes the Chebyshev polynomial of the second kind.
a(n-1) = the bottom left entry of the 2 X 2 matrix T(n, M), where M is the 2 X 2 matrix [0, 2; 1, 1] and T(n,x) denotes the Chebyshev polynomial of the first kind.
See the remarks in A100047 for the general connection between Chebyshev polynomials of the first kind and 4th-order linear divisibility sequences. (End)
a(n) = (2*(-1)^n + (2-sqrt(3))^(1+n) + (2+sqrt(3))^(1+n)) / 6. - Colin Barker, Dec 16 2017
a(n) = (1 XOR a(n-1))^2/a(n-2). - Jon Maiga, Nov 16 2018
a(n) = a(-2-n) for all n in Z. - Michael Somos, Mar 17 2022
INVERT transform of sequence p(n), n > 0, where p is the number of nonreducible tilings by height of 2 X 2 X n using dicubes; p is (2, 5, 4, 4, 4, 4...). - Nicolas Bělohoubek, Jun 04 2024

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

Original entry on oeis.org

1, 3, 32, 229, 1845, 14320, 112485, 880163, 6895792, 54003765, 422983905, 3312866080, 25947198337, 203223953179, 1591695681488, 12466511517581, 97640484615909, 764741896529104, 5989627994067061, 46912093390144139, 367425909133064576, 2877761124002870925

Offset: 0

Per H. Lundow

nonn

lim(a(n)^(1/n), n -> infinity) = 7.832221... - Emeric Deutsch, Oct 14 2006

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 (2014), eq. (37).
H. Narumi and H. Hosoya, Generalized expression of the perfect matching number of 2 X 3 X n lattices, J. Math. Phys. 34 (3), 1993, 1043-1051.

Column k=3 of A181206.

a[0]:=1: a[1]:=3: a[2]:=32: a[3]:=229: a[4]:=1845: a[5]:=14320: a[6]:=112485: a[7]:=880163: a[8]:=6895792: a[9]:=54003765: a[10]:=422983905: for n from 11 to 20 do a[n]:=6*a[n-1]+21*a[n-2]-42*a[n-3]-89*a[n-4]+68*a[n-5]+89*a[n-6]-42*a[n-7]-21*a[n-8]+6*a[n-9]+a[n-10] od: seq(a[n], n=0..30); # Emeric Deutsch, Oct 14 2006

a(n) = 6a(n - 1) + 21a(n - 2) - 42a(n - 3) - 89a(n - 4) + 68a(n - 5) + 89a(n - 6) - 42a(n - 7) - 21a(n - 8) + 6a(n - 9) + a(n - 10). - Emeric Deutsch, Oct 14 2006

G.f.: ( -1 +3*x +7*x^2 -16*x^3 -14*x^4 +16*x^5 +7*x^6 -3*x^7 -x^8 ) / ( (x^2-x-1) *(x^8 +7*x^7 -13*x^6 -48*x^5 +28*x^4 +48*x^3 -13*x^2 -7*x+1) ). - R. J. Mathar, Dec 06 2013

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

Original entry on oeis.org

1, 5, 121, 1845, 32000, 535229, 9049169, 152526845, 2573281769, 43402320448, 732106008249, 12348802743437, 208295014563521, 3513435627771565, 59263242055245056, 999628735946792581, 16861339891166667849, 284410369641222811445, 4797320930581855672689

Offset: 0

Per H. Lundow

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..800
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.

Column k=4 of A181206.

G.f.: (-x^19 +17*x^18 -53*x^17 -383*x^16 +2051*x^15 +1155*x^14 -16891*x^13 +9523*x^12 +45157*x^11 -41065*x^10 -41065*x^9 +45157*x^8 +9523*x^7 -16891*x^6 +1155*x^5 +2051*x^4 -383*x^3 -53*x^2 +17*x -1) / (x^21 -22*x^20 +42*x^19 +990*x^18 -3493*x^17 -12199*x^16 +55858*x^15 +27106*x^14 -289337*x^13 +146481*x^12 +488514*x^11 -488514*x^10 -146481*x^9 +289337*x^8 -27106*x^7 -55858*x^6 +12199*x^5 +3493*x^4 -990*x^3 -42*x^2 +22*x -1). - Alois P. Heinz, Dec 08 2013

A028449 Number of perfect matchings in graph P_{2} X P_{5} X P_{n}.

Original entry on oeis.org

1, 8, 450, 14320, 535229, 19114420, 692276437, 24972353440, 901990734650, 32567565264292, 1176040842289105, 42466317504553328, 1533458728878759825, 55373015618048484484, 1999515562849410856778, 72202339448101503740768, 2607220750517054436937621

Offset: 0

Per H. Lundow

nonn

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.

Alois P. Heinz, Table of n, a(n) for n = 0..600
Alois P. Heinz, G.f. for A028449
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.

Column k=5 of A181206.

G.f.: see link above.

A028450 Number of perfect matchings in graph P_{2} X P_{6} X P_{n}.

Original entry on oeis.org

1, 13, 1681, 112485, 9049169, 692276437, 53786626921, 4161756233501, 322462050747008, 24976513162427653, 1934824269280528177, 149878484960033943221, 11610280860482785441201, 899384302182455890904869, 69670430204782040731619473, 5396990358379369075151309301

Offset: 0

Per H. Lundow

nonn

This sequence satisfies a recurrence relation of order 213. - Sergey Perepechko, Jul 07 2019

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.

Alois P. Heinz, Table of n, a(n) for n = 0..200
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
A. M. Karavaev and S. N. Perepechko, Dimer problem on two-layer rectangular grid graph, (in Russian) CMMASS'2013 slides
Sergey Perepechko, Generating function in Maple notation
Sergey Perepechko, Generating function in text format

Column k=6 of A181206.

A028451 Number of perfect matchings in graph P_{2} X P_{7} X P_{n}.

Original entry on oeis.org

1, 21, 6272, 880163, 152526845, 24972353440, 4161756233501, 690427159718433, 114725843769441312, 19056798015394695543, 3165986817537284900809, 525966380704787334395776, 87380576637559587656345353, 14516824056706613915897809761, 2411733911295546238838103099168

Offset: 0

Per H. Lundow

nonn

This sequence satisfies a recurrence relation of order 750. - Sergey Perepechko, Jul 11 2019

Alois P. Heinz, Table of n, a(n) for n = 0..450
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.
A. M. Karavaev and S. N. Perepechko, Dimer problem on two-layer rectangular grid graph, (in Russian) CMMASS'2013 slides
Sergey Perepechko, Generating function in Maple notation

Column k=7 of A181206.

A181205 Number of n X n matrices containing a permutation of 1..n*n moving each element at most to a neighboring position.

Original entry on oeis.org

1, 1, 9, 229, 32000, 19114420, 53786626921, 690427159718433, 40891433857372174697, 11135886394033736561250816, 13961976233873461322297385441657

Offset: 0

R. H. Hardin, Oct 10 2010

nonn

			All solutions for 2X2
..1..2....1..2....1..4....2..1....2..1....2..4....3..1....3..2....3..4
..3..4....4..3....3..2....3..4....4..3....1..3....4..2....1..4....1..2

Main diagonal of A181206.

Cf. A287152.

A181206 = Cases[Import["https://oeis.org/A181206/b181206.txt", "Table"], {, }][[All, 2]];
a[n_] := A181206[[2 n^2 - 2 n + 1]];
Table[a[n], {n, 1, 10}] (* Jean-François Alcover, Sep 23 2019 *)

a(n) = A287152(n,n^2).

a(0) and a(10) from Alois P. Heinz, May 20 2017

A287052 Number of perfect matchings in the graph P_2 X P_8 X P_n.

Original entry on oeis.org

1, 34, 23409, 6895792, 2573281769, 901990734650, 322462050747008, 114725843769441312, 40891433857372174697, 14569902220123180849570, 5192364005728133102693809, 1850411178640946683018130720, 659450907727206885142090933473, 235016288414744436265662641403648

Offset: 0

Alois P. Heinz, May 18 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..200
Eric Weisstein's World of Mathematics, Perfect Matching
Wikipedia, Matching (graph theory)

Column k=8 of A181206.

A287053 Number of perfect matchings in the graph P_2 X P_9 X P_n.

Original entry on oeis.org

1, 55, 87362, 54003765, 43402320448, 32567565264292, 24976513162427653, 19056798015394695543, 14569902220123180849570, 11135886394033736561250816, 8513244230416326065909810345, 6508281831123403112229534915956, 4975689584055269435866523080540937

Offset: 0

Alois P. Heinz, May 18 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..120
Eric Weisstein's World of Mathematics, Perfect Matching
Wikipedia, Matching (graph theory)

Column k=9 of A181206.

A287054 Number of perfect matchings in the graph P_2 X P_10 X P_n.

Original entry on oeis.org

1, 89, 326041, 422983905, 732106008249, 1176040842289105, 1934824269280528177, 3165986817537284900809, 5192364005728133102693809, 8513244230416326065909810345, 13961976233873461322297385441657, 22898547721543876821935695804773817

Offset: 0

Alois P. Heinz, May 18 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..50
Eric Weisstein's World of Mathematics, Perfect Matching
Wikipedia, Matching (graph theory)

Column k=10 of A181206.

cp's OEIS Frontend

A006253 Number of perfect matchings (or domino tilings) in C_4 X P_n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

PARI

PARI

PARI

Sage

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

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

Views

Author

Keywords

Links

Crossrefs

Formula

A028449 Number of perfect matchings in graph P_{2} X P_{5} X P_{n}.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A028450 Number of perfect matchings in graph P_{2} X P_{6} X P_{n}.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A028451 Number of perfect matchings in graph P_{2} X P_{7} X P_{n}.

Views

Author

Keywords

Comments

Links

Crossrefs

A181205 Number of n X n matrices containing a permutation of 1..n*n moving each element at most to a neighboring position.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A287052 Number of perfect matchings in the graph P_2 X P_8 X P_n.

Views

Author

Keywords

Links

Crossrefs

A287053 Number of perfect matchings in the graph P_2 X P_9 X P_n.

Views

Author

Keywords