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

 

Logo


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 August 22 20:19 EDT 2017. Contains 290951 sequences.