login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003775 Number of perfect matchings (or domino tilings) in P_5 X P_2n. 8
1, 8, 95, 1183, 14824, 185921, 2332097, 29253160, 366944287, 4602858719, 57737128904, 724240365697, 9084693297025, 113956161827912, 1429438110270431, 17930520634652959, 224916047725262248, 2821291671062267585, 35389589910135145793, 443918325373278904936 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

REFERENCES

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

R. P. Stanley, Enumerative Combinatorics I, p. 292.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..300

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.

F. Faase, Counting Hamilton cycles in product graphs

F. Faase, Results from the counting program

David Klarner, Jordan Pollack, Domino tilings of rectangles with fixed width, Disc. Math. 32 (1980) 45-52

R. J. Mathar, Paving rectangular regions with rectangular tiles,...., arXiv:1311.6135 [math.CO], Table 4.

James A. Sellers, Domino Tilings and Products of Fibonacci and Pell Numbers, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.2

Index entries for sequences related to dominoes

Index entries for linear recurrences with constant coefficients, signature (15,-32,15,-1).

FORMULA

If b(n) denotes the number of perfect matchings (or domino tilings) in P_5 X P_n we have:

b(1) = 0,

b(2) = 8,

b(3) = 0,

b(4) = 95,

b(5) = 0,

b(6) = 1183,

b(7) = 0,

b(8) = 14824 and

b(n) = 15b(n-2) - 32b(n-4) + 15b(n-6) - b(n-8).

G.f.: (1-x)*(1-6*x+x^2)/(1-15*x+32*x^2-15*x^3+x^4).

Let M be the 4 X 4 matrix |1 0 2 8 | 0 1 0 2 | 2 1 5 21| 1 1 1 8 |; then a(n) = M^n(4, 4). - Philippe Deléham, Aug 08 2003

Lim_{n -> Inf} a(n)/a(n-1) = (3 + Sqrt(5))*(5 + Sqrt(21))/4 = 12.54375443458... - Philippe Deléham, Jun 13 2005

a(n) = ((35+7*sqrt(5)+5*sqrt(21)+sqrt(105))*((3+sqrt(5))*(5+sqrt(21))/4)^n+(35-7*sqrt(5)+5*sqrt(21)-sqrt(105))*((3-sqrt(5))*(5+sqrt(21))/4)^n+(35+7*sqrt(5)-5*sqrt(21)-sqrt(105))*((3+sqrt(5))*(5-sqrt(21))/4)^n+(35-7*sqrt(5)-5*sqrt(21)+sqrt(105))*((3-sqrt(5))*(5-sqrt(21))/4)^n)/140. [Tim Monahan, Aug 13 2011]

MAPLE

a:= n-> (<<15|-32|15|-1>, <1|0|0|0>, <0|1|0|0>, <0|0|1|0>>^n. <<8, 1, 1, 8>>)[2, 1]: seq(a(n), n=0..20);  # Alois P. Heinz, Sep 24 2011

MATHEMATICA

a = 3; b = 5; c = 7; d = a*c; e = b*c; g = a*b*c; f[n_] := Simplify[((e + c*Sqrt[b] + b*Sqrt[d] + Sqrt[g])*((a + Sqrt[b])*(b + Sqrt[d])/4)^n + (e - c*Sqrt[b] + b*Sqrt[d] - Sqrt[g])*((a - Sqrt[b])*(b + Sqrt[d])/4)^n + (e + c*Sqrt[b] - b*Sqrt[d] - Sqrt[g])*((a + Sqrt[b])*(b - Sqrt[d])/4)^n + (e - c*Sqrt[b] - 5*Sqrt[d] + Sqrt[g])*((a - Sqrt[b])*(b - Sqrt[d])/4)^n)/ 140]; Array[f, 17, 0] (* Robert G. Wilson v, Aug 13 2011 *)

a[n_] := (MatrixPower[{{15, -32, 15, -1}, {1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}}, n].{8, 1, 1, 8})[[2]]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jan 31 2016, after Alois P. Heinz *)

CROSSREFS

Row 5 of array A099390.

Bisection of A189003.

Sequence in context: A080208 A099298 A182648 * A262737 A121785 A229294

Adjacent sequences:  A003772 A003773 A003774 * A003776 A003777 A003778

KEYWORD

nonn

AUTHOR

Frans J. Faase

EXTENSIONS

Added recurrence from Faase's web page. - N. J. A. Sloane, Feb 03 2009

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified November 21 06:31 EST 2017. Contains 294989 sequences.