A003751 - OEIS

%I #29 Aug 23 2023 09:37:13

%S 125,300125,663552000,1464514260125,3232184906328125,

%T 7133430745792512000,15743478429512478120125,

%U 34745849760772636969860125,76684074678559433693601792000,169241718069731503830237768828125,373516395095822778319979141039280125

%N Number of spanning trees in K_5 x P_n.

%C This is a divisibility sequence.

%D F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

%H P. Raff, <a href="/A003751/b003751.txt">Table of n, a(n) for n = 1..200</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 P. Raff, <a href="http://arxiv.org/abs/0809.2551">Spanning Trees in Grid Graphs</a>, arXiv:0809.2551 [math.CO], 2008.

%H P. Raff, <a href="http://www.math.rutgers.edu/~praff/span/5/12-13-14-15-23-24-25-34-35-45/index.xml">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}}.</a> Contains sequence, recurrence, generating function, and more.

%H P. Raff, <a href="http://www.myraff.com/projects/spanning-trees-in-grid-graphs">Analysis of the Number of Spanning Trees of Grid Graphs</a>.

%H <a href="/index/Di#divseq">Index to divisibility sequences</a>

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (2255,-105985,105985,-2255,1).

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

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

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

%F a(n) = 125*F(4n)^4/81. - _R. K. Guy_, Feb 24 2010

%t (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 *)

%K nonn

%O 1,1

%A _Frans J. Faase_

%E Added recurrence from Faase's web page. - _N. J. A. Sloane_, Feb 03 2009

%E More terms from _Harvey P. Dale_, Apr 24 2013