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, 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 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
KEYWORD
nonn
AUTHOR
EXTENSIONS
STATUS
approved