|
| |
|
|
A003755
|
|
Number of spanning trees in S_4 X P_n.
|
|
0
| |
|
|
1, 54, 2240, 89964, 3596725, 143700480, 5740732439, 229334969304, 9161621922880, 365994298083150, 14620972301965259, 584087869159280640, 23333512405041243469, 932141942728566562746
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
REFERENCES
| F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
|
|
|
LINKS
| 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
Index entries for sequences related to trees
F. Faase, Counting Hamilton cycles in product graphs
P. Raff, Spanning Trees in Grid Graphs. [From Paul Raff, Mar 06 2009]
P. Raff, Analysis of the Number of Spanning Trees of S_4 x P_n. Contains sequence, recurrence, generating function, and more. [From Paul Raff, Mar 06 2009]
|
|
|
FORMULA
| a(1) = 1,
a(2) = 54,
a(3) = 2240,
a(4) = 89964,
a(5) = 3596725,
a(6) = 143700480 and
a(n) = 48a(n-1) - 336a(n-2) + 582a(n-3) - 336a(n-4) + 48a(n-5) - a(n-6).
G.f.: x(x^4+6x^3-16x^2+6x+1)/(x^6-48x^5+336x^4-582x^3+336x^2-48x+1) [From Paul Raff, Mar 06 2009]
a(n) = A001109(n)*A049684(n). [R. Guy, seqfan list, Mar 28 2009] [From R. J. Mathar, Jun 03 2009]
|
|
|
MAPLE
| a:= n-> (Matrix([[1, 0, -1, -54, -2240, -89964]]). Matrix(6, (i, j)-> if (i=j-1) then 1 elif j=1 then [48, -336, 582, -336, 48, -1][i] else 0 fi)^(n-1))[1, 1]; seq (a(n), n=1..14); # Alois P. Heinz, Aug 01 2008
|
|
|
CROSSREFS
| Sequence in context: A004363 A062144 A076009 * A174445 A188612 A188605
Adjacent sequences: A003752 A003753 A003754 * A003756 A003757 A003758
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Frans Faase (Frans_LiXia(AT)wxs.nl)
|
|
|
EXTENSIONS
| Added recurrence from Faase's web page. - N. J. A. Sloane (njas(AT)research.att.com), Feb 03 2009
|
| |
|
|
