OFFSET
1,2
COMMENTS
a(n)/n^n is the average size of the largest component.
a(n)/n^(n + 1) is the probability that a particular node is in the largest component of the digraph.
REFERENCES
R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison and Welsey, 1996, Chapter 8.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..385
FORMULA
a(n) = Sum_{k=1..n} k * A209324(n,k).
MAPLE
g:= proc(n) option remember; add(n^(n-j)*(n-1)!/(n-j)!, j=1..n) end:
b:= proc(n, m) option remember; `if`(n=0, x^m, add(g(i)*
b(n-i, max(m, i))*binomial(n-1, i-1), i=1..n))
end:
a:= n-> (p-> add(coeff(p, x, i)*i, i=1..n))(b(n, 0)):
seq(a(n), n=1..20); # Alois P. Heinz, Dec 17 2021
MATHEMATICA
nn=20; g[list_]:= Sum[list[[i]]*i, {i, 1, Length[list]}]; t=Sum[n^(n-1)x^n/n!, {n, 1, nn}]; c=Log[1/(1-t)]; b=Drop[Range[0, nn]!CoefficientList[Series[c, {x, 0, nn}], x], 1]; f[list_]:=Select[list, #>0&]; Map[g, Map[ f, Drop[Transpose[Table[Range[0, nn]!CoefficientList[Series[ Exp[Sum[b[[i]]x^i/i!, {i, 1, n+1}]]-Exp[Sum[b[[i]]x^i/i!, {i, 1, n}]], {x, 0, nn}], x], {n, 0, nn-1}]], 1]]]
CROSSREFS
KEYWORD
nonn
AUTHOR
Geoffrey Critzer, Jan 19 2013
STATUS
approved