login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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), 129-154.

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

F. Faase, Counting Hamilton 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(n-1) - 1394a(n-2) + 1394a(n-3) - 205a(n-4) + a(n-5).

a(n) = 204*a(n-1) - 1190*a(n-2) + 204*a(n-3) - a(n-4). - Paul Raff, Jun 04 2008

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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 26 02:24 EDT 2017. Contains 288749 sequences.