cp's OEIS Frontend

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}.

%I A209327 #27 Dec 19 2021 08:02:26
%S A209327 1,7,70,863,13056,231187,4737986,109531991,2835638008,80950287311,
%T A209327 2533758258912,86089196479255,3161596017956936,124590870125959343,
%U A209327 5251666647713483356,235497961945975068767,11205025852314462333408,563351626162952600815087,29864689571162209608920060,1663796497123214306448307031
%N 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}.
%C A209327 a(n)/n^n is the average size of the largest component.
%C A209327 a(n)/n^(n + 1) is the probability that a particular node is in the largest component of the digraph.
%D A209327 R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison and Welsey, 1996, Chapter 8.
%H A209327 Alois P. Heinz, <a href="/A209327/b209327.txt">Table of n, a(n) for n = 1..385</a>
%F A209327 a(n) = Sum_{k=1..n} k * A209324(n,k).
%p A209327 g:= proc(n) option remember; add(n^(n-j)*(n-1)!/(n-j)!, j=1..n) end:
%p A209327 b:= proc(n, m) option remember; `if`(n=0, x^m, add(g(i)*
%p A209327       b(n-i, max(m, i))*binomial(n-1, i-1), i=1..n))
%p A209327     end:
%p A209327 a:= n-> (p-> add(coeff(p, x, i)*i, i=1..n))(b(n, 0)):
%p A209327 seq(a(n), n=1..20);  # _Alois P. Heinz_, Dec 17 2021
%t A209327 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]]]
%Y A209327 Cf. A001865, A209324, A350157.
%K A209327 nonn
%O A209327 1,2
%A A209327 _Geoffrey Critzer_, Jan 19 2013