|
|
A003755
|
|
Number of spanning trees in S_4 X P_n.
|
|
1
|
|
|
1, 54, 2240, 89964, 3596725, 143700480, 5740732439, 229334969304, 9161621922880, 365994298083150, 14620972301965259, 584087869159280640, 23333512405041243469, 932141942728566562746, 37237797134599264280000, 1487599121840339002010544, 59427552583207598523644161
(list;
graph;
refs;
listen;
history;
text;
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
|
|
|
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+6*x^3-16*x^2+6*x+1)/ ((x^2-6*x+1)*(x^4-42*x^3+83*x^2-42*x+1)). - Paul Raff, Mar 06 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
|
|
MATHEMATICA
|
LinearRecurrence[{48, -336, 582, -336, 48, -1}, {1, 54, 2240, 89964, 3596725, 143700480}, 17] (* Jean-François Alcover, Aug 06 2018 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|