A209327 Total number of nodes in the largest connected component of a functional digraph summed over all endofunctions f:{1,2,...,n}-> {1,2,...,n}.

1, 7, 70, 863, 13056, 231187, 4737986, 109531991, 2835638008, 80950287311, 2533758258912, 86089196479255, 3161596017956936, 124590870125959343, 5251666647713483356, 235497961945975068767, 11205025852314462333408, 563351626162952600815087, 29864689571162209608920060, 1663796497123214306448307031

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

Cf. A001865, A209324, A350157.

Sequence in context: A002296 A027394 A346767 * A255519 A305966 A226805

Adjacent sequences: A209324 A209325 A209326 * A209328 A209329 A209330

Keyword

nonn

Author

Geoffrey Critzer, Jan 19 2013

Status

approved