The OEIS is supported by the many generous donors to the OEIS Foundation. Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 60th year, we have over 367,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”). Other ways to Give
 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A003757 Number of perfect matchings (or domino tilings) in D_4 X P_(n-1). 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 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). 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) 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 *) PROG (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 CROSSREFS Sequence in context: A131188 A247939 A203977 * A187985 A320043 A296619 Adjacent sequences: A003754 A003755 A003756 * A003758 A003759 A003760 KEYWORD nonn AUTHOR Frans J. Faase EXTENSIONS Offset and name changed by T. D. Noe, Dec 22 2008 0 and 1 prepended by T. D. Noe, Dec 22 2008 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 4 21:08 EST 2023. Contains 367565 sequences. (Running on oeis4.)