

A003773


Number of spanning trees in K_4 X P_n.


1



16, 3456, 686000, 135834624, 26894628304, 5325000912000, 1054323287943536, 208750686023540736, 41331581509440922000, 8183444388183674181504, 1620280657278860350213424, 320807386696826179092096000
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


REFERENCES

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


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), 129154.
F. Faase, Counting Hamiltonian cycles in product graphs
F. Faase, Results from the counting program
P. Raff, Spanning Trees in Grid Graphs.
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 sequences related to trees
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(n1)  1394a(n2) + 1394a(n3)  205a(n4) + a(n5).
a(n) = 204*a(n1)  1190*a(n2) + 204*a(n3)  a(n4).  Paul Raff, Jun 04 2008
G.f.: 16x(1+12x+x^2)/((16x+x^2)(x^2198x+1)). a(n) = 35*A097731(n1)/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 *)


CROSSREFS

Sequence in context: A266824 A249599 A281821 * A217021 A087519 A222917
Adjacent sequences: A003770 A003771 A003772 * A003774 A003775 A003776


KEYWORD

nonn


AUTHOR

Frans J. Faase


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



