|
|
A057817
|
|
Moebius invariant of cographic hyperplane arrangement for complete graph K_n. Also value of Tutte dichromatic polynomial T_G(0,1) for G=K_n. Also alternating sum F_{n,1} - F_{n,2} + F_{n,3} - ..., where F_{n,k} is the number of labeled forests on n nodes with k connected components.
|
|
6
|
|
|
1, 0, 1, 6, 51, 560, 7575, 122052, 2285353, 48803904, 1171278945, 31220505800, 915350812299, 29281681800384, 1015074250155511, 37909738774479600, 1517587042234033425, 64830903253553212928, 2944016994706445303937
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
The rank of reduced homology groups for the matroid complex of acyclic subgraphs in complete graph K_n (n>1). It is also the number of labeled edge-rooted forests on n-1 nodes where each connected component contains at least one edge.
The description of this sequence as the number of labeled edge-rooted forests on n-1 nodes appeared in W. Kook's Ph.D. thesis (G. Carlsson, advisor), Categories of acyclic graphs and automorphisms of free groups, Stanford University, 1996.
|
|
REFERENCES
|
W. Kook, Categories of acyclic graphs and automorphisms of free groups, Ph.D. thesis (G. Carlsson, advisor), Stanford University, 1996
|
|
LINKS
|
|
|
FORMULA
|
E.g.f.: integral exp( Sum_{m>1}(m-1)*m^{m-2}*x^{m}/m!) dx (n-1) Sum_{k=0}^{[(n-2)/2]} binomial((n-2)! , 2^k k! (n-2-2k)!) n^{n-2-2k}.
E.g.f.: exp( Sum_{m>1}(m-1)*m^{m-2}*x^{m}/m!).
E.g.f.: integral(exp(1/2*LambertW(-x)^2)dx). - Vladeta Jovovic, Apr 10 2001
a(n) = n^(n-2) - Sum_{k=1..n-1} binomial(n-1,k-1) * k^(k-2) * a(n-k). - Ilya Gutkovskiy, Feb 07 2020
|
|
EXAMPLE
|
For n=4, the number of labeled edge-rooted forests on three (= n-1) nodes is 6: There are 3 labeled trees on three nodes. These are the only forests with at least one edge in each connected component. Each tree has 2 edges and each of the two may be marked as the root.
|
|
MAPLE
|
for n from 1 to 50 do printf(`%d, `, (n-1)*sum((n-2)!/(2^k*k!*(n-2-2*k)!)*n^(n-2-2*k), k=0..floor((n-2)/2))) od:
|
|
MATHEMATICA
|
s=20; (*generates first s terms starting from n=2*) K := Exp[Sum[(m-1)*(m^(m-2))*(x^m)/m!, {m, 2, 2s}]]; S := Series[K, {x, 0, s}]; h[i_] := SeriesCoefficient[S, i-1]*(i-1)!; Table[h[n+1], {n, s}]
a[n_] := (n-2)*Sum[ (n-1)^(n-2k-3)*(n-3)! / (2^k*k!*(n-2k-3)!), {k, 0, Floor[ (n-3)/ 2 ]}]; a[1] = 1; Table[a[n], {n, 1, 19}] (* Jean-François Alcover, Dec 11 2012, after Maple *)
|
|
PROG
|
(PARI) a(n)=if(n<1, 0, (n-1)!*polcoeff(exp(sum(k=1, n-1, k^(k-1)*x^k/k!, O(x^n))^2/2), n-1))
(PARI) a(n)=if(n<2, n==1, sum(k=0, (n-3)\2, (n-1)!/(2^k*k!*(n-3-2*k)!)*(n-1)^(n-4-2*k)))
(PARI)
he(n, x)=x^n+sum(k=1, n\2, binomial(n, 2*k) * df(k) * x^(n-2*k) );
a(n)=if( n<3, n==1, (n-2)*he(n-3, n-1) );
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
Alex Postnikov (apost(AT)math.mit.edu), Nov 06 2000
|
|
EXTENSIONS
|
Additional comments from Woong Kook (andrewk(AT)math.uri.edu), Feb 12 2002
Updated author's URL and e-mail address R. J. Mathar, May 23 2010
|
|
STATUS
|
approved
|
|
|
|