A003757 Number of perfect matchings (or domino tilings) in D_4 X P_(n-1).

0, 1, 1, 6, 13, 49, 132, 433, 1261, 3942, 11809, 36289, 109824, 335425, 1018849, 3104934, 9443629, 28756657, 87504516, 266383153, 810723277, 2467770054, 7510988353, 22861948801, 69584925696, 211799836801, 644660351425

Offset: 0

Author

Frans J. Faase

Keywords

• nonn

Comments

Here D_4 is the graph on 4 vertices with edges (1,2), (1,3), (2,3), (1.4): a triangular kite with a tail.

This is a divisibility sequence; that is, if n divides m, then a(n) divides a(m). - T. D. Noe, Dec 22 2008

This is the case P1 = 1, P2 = -8, Q = 1 of the 3 parameter family of 4th-order linear divisibility sequences found by Williams and Guy. - Peter Bala, Mar 31 2014

References

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

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..160
• 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
• F. J. Faase, Results from the counting program
• Paul Raff, Spanning Trees in Grid Graphs, arXiv:0809.2551 [math.CO], 2008.
• H. C. Williams and R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory 7 (5) (2011) 1255-1277.
• H. C. Williams and R. K. Guy, Some Monoapparitic Fourth Order Linear Divisibility Sequences, Integers, Volume 12A (2012) The John Selfridge Memorial Volume
• Index to divisibility sequences
• Index entries for sequences related to dominoes
• Index entries for linear recurrences with constant coefficients, signature (1,6,1,-1).

Programs

Magma

I:=[0,1,1,6]; [n le 4 select I[n] else Self(n-1)+6*Self(n-2)+Self(n-3)-Self(n-4): n in [1..30]]; // Vincenzo Librandi, Sep 24 2011

Mathematica

CoefficientList[Series[x(1-x^2)/(1-x-6x^2-x^3+x^4), {x,0,30}], x] (* T. D. Noe, Dec 22 2008 *)
LinearRecurrence[{1,6,1,-1},{0,1,1,6},40] (* Harvey P. Dale, Sep 23 2011 *)

Formula

a(n) = a(n-1) + 6a(n-2) + a(n-3) - a(n-4), n>4.

G.f.: x(1-x^2)/(1-x-6x^2-x^3+x^4). [T. D. Noe, Dec 22 2008]

From Peter Bala, Mar 31 2014: (Start)

a(n) = ( T(n,alpha) - T(n,beta) )/(alpha - beta), where alpha = (1 + sqrt(33))/4 and beta = (1 - sqrt(33))/4 and T(n,x) denotes the Chebyshev polynomial of the first kind.

a(n) = the bottom left entry of the 2 X 2 matrix T(n, M), where M is the 2 X 2 matrix [0, 2; 1, 1/2].

a(n) = U(n-1,i*(1 + sqrt(3))/sqrt(8))*U(n-1,i*(1 - sqrt(3))/sqrt(8)), where U(n,x) denotes the Chebyshev polynomial of the second kind.

See the remarks in A100047 for the general connection between Chebyshev polynomials and 4th-order linear divisibility sequences. (End)

Extensions

Offset and name changed by T. D. Noe, Dec 22 2008

0 and 1 prepended by T. D. Noe, Dec 22 2008