A003751 Number of spanning trees in K_5 x P_n.

125, 300125, 663552000, 1464514260125, 3232184906328125, 7133430745792512000, 15743478429512478120125, 34745849760772636969860125, 76684074678559433693601792000, 169241718069731503830237768828125, 373516395095822778319979141039280125

Offset: 1

Author

Frans J. Faase

Keywords

• nonn

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), 129-154.

Links

• P. Raff, Table of n, a(n) for n = 1..200
• 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
• P. Raff, Spanning Trees in Grid Graphs, arXiv:0809.2551 [math.CO], 2008.
• 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.
• P. Raff, Analysis of the Number of Spanning Trees of Grid Graphs.
• Index to divisibility sequences
• Index entries for sequences related to trees
• Index entries for linear recurrences with constant coefficients, signature (2255,-105985,105985,-2255,1).

Programs

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 *)

Formula

a(n) = 2255a(n-1)- 105985a(n-2) +105985a(n-3) -2255a(n-4) +a(n-5).

a(n) = 125*(A004187(n))^4 = 125*(A049682(n))^2. [R. Guy, seqfan list, Mar 28 2009] [From R. J. Mathar, Jun 03 2009]

G.f.: -(125x(x^3+146x^2+146x+1)/(x^5-2255x^4+105985x^3-105985x^2+2255x-1)) [Paul Raff, Oct 29 2009]

a(n) = 125*F(4n)^4/81. - R. K. Guy, Feb 24 2010

Extensions

Added recurrence from Faase's web page. - N. J. A. Sloane, Feb 03 2009

More terms from Harvey P. Dale, Apr 24 2013