|
%I #44 Mar 21 2023 12:52:35
%S 0,1,1,6,13,49,132,433,1261,3942,11809,36289,109824,335425,1018849,
%T 3104934,9443629,28756657,87504516,266383153,810723277,2467770054,
%U 7510988353,22861948801,69584925696,211799836801,644660351425
%N Number of perfect matchings (or domino tilings) in D_4 X P_(n-1).
%C 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.
%C This is a divisibility sequence; that is, if n divides m, then a(n) divides a(m). - _T. D. Noe_, Dec 22 2008
%C 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
%D F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
%H Vincenzo Librandi, <a href="/A003757/b003757.txt">Table of n, a(n) for n = 0..160</a>
%H F. Faase, <a href="http://www.iwriteiam.nl/Cpaper.zip">On the number of specific spanning subgraphs of the graphs G X P_n</a>, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
%H F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamiltonian cycles in product graphs</a>
%H F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>
%H F. J. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>
%H Paul Raff, <a href="http://arxiv.org/abs/0809.2551">Spanning Trees in Grid Graphs</a>, arXiv:0809.2551 [math.CO], 2008.
%H H. C. Williams and R. K. Guy, <a href="http://dx.doi.org/10.1142/S1793042111004587">Some fourth-order linear divisibility sequences</a>, Intl. J. Number Theory 7 (5) (2011) 1255-1277.
%H H. C. Williams and R. K. Guy, <a href="http://www.emis.de/journals/INTEGERS/papers/a17self/a17self.pdf">Some Monoapparitic Fourth Order Linear Divisibility Sequences</a>, Integers, Volume 12A (2012) The John Selfridge Memorial Volume
%H <a href="/index/Di#divseq">Index to divisibility sequences</a>
%H <a href="/index/Do#domino">Index entries for sequences related to dominoes</a>
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,6,1,-1).
%F a(n) = a(n-1) + 6a(n-2) + a(n-3) - a(n-4), n>4.
%F G.f.: x(1-x^2)/(1-x-6x^2-x^3+x^4). [_T. D. Noe_, Dec 22 2008]
%F From _Peter Bala_, Mar 31 2014: (Start)
%F 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.
%F 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].
%F 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.
%F See the remarks in A100047 for the general connection between Chebyshev polynomials and 4th-order linear divisibility sequences. (End)
%t CoefficientList[Series[x(1-x^2)/(1-x-6x^2-x^3+x^4), {x,0,30}], x] (* _T. D. Noe_, Dec 22 2008 *)
%t LinearRecurrence[{1,6,1,-1},{0,1,1,6},40] (* _Harvey P. Dale_, Sep 23 2011 *)
%o (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
%K nonn
%O 0,4
%A _Frans J. Faase_
%E Offset and name changed by _T. D. Noe_, Dec 22 2008
%E 0 and 1 prepended by _T. D. Noe_, Dec 22 2008
|
