

A003757


Number of perfect matchings (or domino tilings) in D_4 X P_(n1).


8



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


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 4thorder 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), 129154.


LINKS



FORMULA

a(n) = a(n1) + 6a(n2) + a(n3)  a(n4), n>4.
G.f.: x(1x^2)/(1x6x^2x^3+x^4). [T. D. Noe, Dec 22 2008]
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(n1,i*(1 + sqrt(3))/sqrt(8))*U(n1,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 4thorder linear divisibility sequences. (End)


MATHEMATICA

CoefficientList[Series[x(1x^2)/(1x6x^2x^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 *)


PROG

(Magma) I:=[0, 1, 1, 6]; [n le 4 select I[n] else Self(n1)+6*Self(n2)+Self(n3)Self(n4): n in [1..30]]; // Vincenzo Librandi, Sep 24 2011


CROSSREFS



KEYWORD

nonn


AUTHOR



EXTENSIONS

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


STATUS

approved



