|
| |
|
|
A003775
|
|
Number of perfect matchings (or domino tilings) in P_5 X P_2n.
|
|
4
| |
|
|
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; 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
| 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
F. Faase, Counting Hamilton cycles in product graphs
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
|
|
|
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-7*x+7*x^2-x^3)/(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). - DELEHAM Philippe, Aug 08, 2003
Lim_{n -> Inf} a(n)/a(n-1) = (3 + Sqrt(5))*(5 + Sqrt(21))/4 = 12.54375443458... - Philippe DELEHAM, 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 *)
|
|
|
CROSSREFS
| Row 5 of array A099390.
Sequence in context: A080208 A099298 A182648 * A121785 A116144 A074114
Adjacent sequences: A003772 A003773 A003774 * A003776 A003777 A003778
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Frans Faase (Frans_LiXia(AT)wxs.nl)
|
|
|
EXTENSIONS
| Added recurrence from Faase's web page. - N. J. A. Sloane (njas(AT)research.att.com), Feb 03 2009
|
| |
|
|
