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
Vincenzo Librandi, Table of n, a(n) for n = 1..200
I. Novik, A. Postnikov and B. Sturmfels, Syzygies of oriented matroids, arXiv:math/0009241 [math.CO], 2000.
A. Postnikov, Papers
FORMULA
E.g.f.: exp(1/2*LambertW(-x)^2). - Vladeta Jovovic, Apr 10 2001
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) ~ exp(-1/2)*n^(n-2). - Vaclav Kotesovec, Dec 12 2012
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)
df(n)=(2*n)!/(n!*2^n); \\ A001147
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) );
/* Joerg Arndt, May 06 2013 */
CROSSREFS
KEYWORD
nonn,nice,easy
AUTHOR
Alex Postnikov (apost(AT)math.mit.edu), Nov 06 2000
EXTENSIONS
More terms from James A. Sellers, Nov 08 2000
Additional comments from Woong Kook (andrewk(AT)math.uri.edu), Feb 12 2002
Further comments from Michael Somos, Sep 18 2002
Updated author's URL and e-mail address R. J. Mathar, May 23 2010
STATUS
approved