

A003751


Number of spanning trees in K_5 x P_n.


1



125, 300125, 663552000, 1464514260125, 3232184906328125, 7133430745792512000, 15743478429512478120125, 34745849760772636969860125, 76684074678559433693601792000, 169241718069731503830237768828125, 373516395095822778319979141039280125
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

This is a divisibility sequence.


REFERENCES

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129154.


LINKS

P. Raff, Analysis of the Number of Spanning Trees of G x P_n, where G = {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}}. Contains sequence, recurrence, generating function, and more.


FORMULA

a(n) = 2255a(n1) 105985a(n2) +105985a(n3) 2255a(n4) +a(n5).
G.f.: (125x(x^3+146x^2+146x+1)/(x^52255x^4+105985x^3105985x^2+2255x1)) [Paul Raff, Oct 29, 2009]
a(n) = 125*F(4n)^4/81.  R. K. Guy, Feb 24 2010


MATHEMATICA

(125*Fibonacci[4*Range[20]]^4)/81 (* or *) LinearRecurrence[ {2255, 105985, 105985, 2255, 1}, {125, 300125, 663552000, 1464514260125, 3232184906328125}, 20] (* Harvey P. Dale, Apr 24 2013 *)


CROSSREFS



KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



