OFFSET
1,1
REFERENCES
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
LINKS
Paul Raff, Jun 04 2008, Table of n, a(n) for n = 1..15
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
P. Raff, Spanning Trees in Grid Graphs, arXiv:0809.2551 [math.CO], 2008.
P. Raff, Analysis of the Number of Spanning Trees of K_3 x P_n. Contains sequence, recurrence, generating function, and more.
Index entries for linear recurrences with constant coefficients, signature (204,-1190,204,-1).
FORMULA
a(1) = 16,
a(2) = 3456,
a(3) = 686000,
a(4) = 135834624,
a(5) = 26894628304 and
a(n) = 205a(n-1) - 1394a(n-2) + 1394a(n-3) - 205a(n-4) + a(n-5).
a(n) = 204*a(n-1) - 1190*a(n-2) + 204*a(n-3) - a(n-4). - Paul Raff, Jun 04 2008
G.f.: 16x(1+12x+x^2)/((1-6x+x^2)(x^2-198x+1)). a(n) = 35*A097731(n-1)/2 - 3*A001109(n)/2. - R. J. Mathar, Dec 16 2008
a(n)=16*(A001109(n))^3=16*A001109(n)*A001110(n). [R. Guy, seqfan list, Mar 28 2009] - R. J. Mathar, Jun 03 2009
MATHEMATICA
LinearRecurrence[{204, -1190, 204, -1}, {16, 3456, 686000, 135834624}, 12] (* Ray Chandler, Aug 11 2015 *)
PROG
(PARI) a(n)=([0, 1, 0, 0; 0, 0, 1, 0; 0, 0, 0, 1; -1, 204, -1190, 204]^(n-1)*[16; 3456; 686000; 135834624])[1, 1] \\ Charles R Greathouse IV, May 31 2026
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
EXTENSIONS
More terms from Paul Raff, Jun 04 2008
Added recurrence from Faase's web page. - N. J. A. Sloane, Feb 03 2009
STATUS
approved