A003775 Number of perfect matchings (or domino tilings) in P_5 X P_2n.

1, 8, 95, 1183, 14824, 185921, 2332097, 29253160, 366944287, 4602858719, 57737128904, 724240365697, 9084693297025, 113956161827912, 1429438110270431, 17930520634652959, 224916047725262248, 2821291671062267585, 35389589910135145793, 443918325373278904936

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 Hamiltonian cycles in product graphs

F. Faase, Results from the counting program

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

R. J. Mathar, Paving rectangular regions with rectangular tiles: tatami and non-tatami tilings, arXiv:1311.6135 [math.CO], 2013, 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.

Thotsaporn ”Aek” Thanatipanonda, Statistics of Domino Tilings on a Rectangular Board, Fibonacci Quart. 57 (2019), no. 5, 145-153. See p. 151.

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

Limit_{n -> infinity} 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 *)
a[0] = 1; a[n_] := Product[2(2+Cos[j Pi/3]+Cos[2k Pi/(2n+1)]), {k, 1, n}, {j, 1, 2}] // Round;
Table[a[n], {n, 0, 19}] (* Jean-François Alcover, Aug 20 2018 *)
LinearRecurrence[{15, -32, 15, -1}, {1, 8, 95, 1183}, 20] (* Vincenzo Librandi, Aug 20 2018 *)

Prog

(Magma) I:=[1, 8, 95, 1183]; [n le 4 select I[n] else 15*Self(n-1)-32*Self(n-2)+15*Self(n-3)-Self(n-4): n in [1..30]]; // Vincenzo Librandi, Aug 20 2018

Crossrefs

Row 5 of array A099390.

Bisection of A189003.

Sequence in context: A299611 A099298 A182648 * A262737 A299747 A300261

Adjacent sequences: A003772 A003773 A003774 * A003776 A003777 A003778

Keyword

nonn

Author

Frans J. Faase

Extensions

Recurrence from Faase's web page added by N. J. A. Sloane, Feb 03 2009

Status

approved