A189003 -id:A189003 - cp's OEIS frontend

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

Frans J. Faase

nonn

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.

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).

Row 5 of array A099390.

Bisection of A189003.

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

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

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 *)

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

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

A189006 Array A(m,n) read by antidiagonals: number of domino tilings of the m X n grid with upper left corner removed iff m*n is odd, (m>=0, n>=0).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 5, 4, 5, 1, 1, 1, 1, 8, 11, 11, 8, 1, 1, 1, 1, 13, 15, 36, 15, 13, 1, 1, 1, 1, 21, 41, 95, 95, 41, 21, 1, 1, 1, 1, 34, 56, 281, 192, 281, 56, 34, 1, 1, 1, 1, 55, 153, 781, 1183, 1183, 781, 153, 55, 1, 1, 1, 1, 89, 209, 2245, 2415, 6728, 2415, 2245, 209, 89, 1, 1

Offset: 0

Alois P. Heinz, Apr 15 2011

			A(3,3) = 4, because there are 4 domino tilings of the 3 X 3 grid with upper left corner removed:
  . .___. . .___. . .___. . .___.
  ._|___| ._|___| ._| | | ._|___|
  | |___| | | | | | |_|_| |___| |
  |_|___| |_|_|_| |_|___| |___|_|
Array begins:
  1, 1,  1,  1,   1,    1,    1, ...
  1, 1,  1,  1,   1,    1,    1, ...
  1, 1,  2,  3,   5,    8,   13, ...
  1, 1,  3,  4,  11,   15,   41, ...
  1, 1,  5, 11,  36,   95,  281, ...
  1, 1,  8, 15,  95,  192, 1183, ...
  1, 1, 13, 41, 281, 1183, 6728, ...

Alois P. Heinz, Antidiagonals n = 0..75, flattened
Eric Weisstein's World of Mathematics, Perfect Matching
Wikipedia, FKT algorithm
Wikipedia, Matching (graph theory)
Index entries for sequences related to dominoes

Rows m=0+1, 2-12 give: A000012, A000045(n+1), A002530(n+1), A005178(n+1), A189003, A028468, A189004, A028470, A189005, A028472, A210724, A028474.
Main diagonal gives: A189002.
Cf. A099390, A187596, A187616, A187617, A187618, A004003.

with(LinearAlgebra):
A:= proc(m, n) option remember; local i, j, s, t, M;
      if m=0 or n=0 then 1
    elif m1 or j>1 or s=0 then
               if j

A[1, 1] = 1; A[m_, n_] := A[m, n] = Module[{i, j, s, t, M}, Which[m == 0 || n == 0, 1, m < n, A[n, m], True, s = Mod[n*m, 2];M[i_, j_] /; j < i := -M[j, i]; M[, ] = 0; For[i = 1, i <= n, i++, For[j = 1, j <= m, j++, t = (i-1)*m+j-s; If[i > 1 || j > 1 || s == 0, If[j < m, M[t, t+1] = 1]; If[i < n, M[t, t+m] = 1-2*Mod[j, 2]]]]]; Sqrt[Det[Array[M, {n*m-s, n*m-s}]]]]]; Table[Table[A[m, d-m], {m, 0, d}], {d, 0, 15}] // Flatten (* Jean-François Alcover, Dec 26 2013, translated from Maple *)

cp's OEIS Frontend

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

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

Extensions