The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A006253 Number of perfect matchings (or domino tilings) in C_4 X P_n. (Formerly M1926) 20
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,2 COMMENTS 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 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, Results from the counting program 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 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 linear recurrences with constant coefficients, signature (3,3,-1). 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 EXAMPLE G.f. = 1 + 2*x + 9*x^2 + 32*x^3 + 121*x^4 + 450*x^5 + ... - Michael Somos, Mar 17 2022 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, a == 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 *) PROG (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 */ (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 (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 (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 CROSSREFS Cf. A002530, A004003, A006125, A217233 (first differences), A109437 (partial sums). Column k=2 of A181206, A189650, A233308. Cf. A100047. Sequence in context: A053369 A076959 A003697 * A045630 A075364 A026526 Adjacent sequences:  A006250 A006251 A006252 * A006254 A006255 A006256 KEYWORD nonn,easy AUTHOR STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 30 14:51 EDT 2022. Contains 354943 sequences. (Running on oeis4.)