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

Author

Geoffrey Critzer, Jan 19 2013

Keywords

• nonn

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

Crossrefs

Cf. A001865, A209324, A350157.

Programs

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]]]

Formula

a(n) = Sum_{k=1..n} k * A209324(n,k).