login
Number of spanning trees in K_4 X P_n.
1

%I #28 Aug 23 2023 09:44:24

%S 16,3456,686000,135834624,26894628304,5325000912000,1054323287943536,

%T 208750686023540736,41331581509440922000,8183444388183674181504,

%U 1620280657278860350213424,320807386696826179092096000

%N Number of spanning trees in K_4 X P_n.

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

%H Paul Raff, Jun 04 2008, <a href="/A003773/b003773.txt">Table of n, a(n) for n = 1..15</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/4/12-13-14-23-24-34/index.xml">Analysis of the Number of Spanning Trees of K_3 x P_n</a>. Contains sequence, recurrence, generating function, and more.

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

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

%F a(1) = 16,

%F a(2) = 3456,

%F a(3) = 686000,

%F a(4) = 135834624,

%F a(5) = 26894628304 and

%F a(n) = 205a(n-1) - 1394a(n-2) + 1394a(n-3) - 205a(n-4) + a(n-5).

%F a(n) = 204*a(n-1) - 1190*a(n-2) + 204*a(n-3) - a(n-4). - _Paul Raff_, Jun 04 2008

%F 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

%F a(n)=16*(A001109(n))^3=16*A001109(n)*A001110(n). [R. Guy, seqfan list, Mar 28 2009] - _R. J. Mathar_, Jun 03 2009

%t LinearRecurrence[{204, -1190, 204, -1},{16, 3456, 686000, 135834624},12] (* _Ray Chandler_, Aug 11 2015 *)

%K nonn

%O 1,1

%A _Frans J. Faase_

%E More terms from _Paul Raff_, Jun 04 2008

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