|
| |
|
|
A006253
|
|
Number of perfect matchings (or domino tilings) in C_4 X P_n.
(Formerly M1926)
|
|
9
| |
|
|
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; 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 Faase (Frans_LiXia(AT)wxs.nl)
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. W. Lang (wolfdieter.lang_AT_physik_DOT_uni-karlsruhe_DOT_de), Oct 18 2004
|
|
|
REFERENCES
| M. Ciucu, Enumeration of perfect matchings in graphs with reflective symmetry. J. Combin. Theory Ser. A 77 (1997), no. 1, 67-97
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 360.
W. Jockusch, Perfect matchings and perfect squares. J. Combin. Theory Ser. A 67 (1994), no. 1, 100-115.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
| F. Faase, Counting Hamilton cycles in product graphs
F. Faase, Counting Hamilton cycles in product graphs
F. Faase, Results from the counting program
S. Plouffe, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
S. Plouffe, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
Index entries for sequences related to dominoes
Index entries for sequences related to bricks
|
|
|
FORMULA
| Nearest integer to (1/6)*(2+sqrt(3))^(n+1). - D. E. 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
Comment 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).
G.f.: (1-x)/((1+x)*(1-4*x+x^2)) = (1-x)/(1-3*x-3*x^2-x^3).
|
|
|
MAPLE
| A006253:=-(-1+z)/(z+1)/(z**2-4*z+1); [Conjectured (correctly) by S. Plouffe in his 1992 dissertation.]
|
|
|
CROSSREFS
| Cf. A002530, A004003, A006125.
Sequence in context: A053369 A076959 A003697 * A045630 A075364 A026526
Adjacent sequences: A006250 A006251 A006252 * A006254 A006255 A006256
|
|
|
KEYWORD
| nonn,easy
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
| |
|
|
