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
Examples
G.f. = 1 + 2*x + 9*x^2 + 32*x^3 + 121*x^4 + 450*x^5 + ... - _Michael Somos_, Mar 17 2022
References
- 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).
Links
- 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).
Crossrefs
Programs
-
GAP
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
-
Magma
m:=30; R
:=PowerSeriesRing(Integers(), m); Coefficients(R!((1-x)/(1-3*x-3*x^2+x^3))); // G. C. Greubel, Nov 16 2018 -
Mathematica
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 *) -
PARI
a(n)=(sqrt(3)+2)^(n+1) \/ 6 \\ Charles R Greathouse IV, Aug 18 2016
-
PARI
a(n)=([0,1,0; 0,0,1; -1,3,3]^n*[1;2;9])[1,1] \\ Charles R Greathouse IV, Aug 18 2016
-
PARI
Vec((1 - x) / ((1 + x)*(1 - 4*x + x^2)) + O(x^40)) \\ Colin Barker, Dec 16 2017
-
PARI
{a(n) = simplify((-1)^n * polchebyshev(n, 2, quadgen(-8)/2)^2)}; /* Michael Somos, Mar 17 2022 */ -
Sage
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
Formula
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
Comments