A002861 Number of connected functions (or mapping patterns) on n unlabeled points, or number of rings and branches with n edges.

1, 2, 4, 9, 20, 51, 125, 329, 862, 2311, 6217, 16949, 46350, 127714, 353272, 981753, 2737539, 7659789, 21492286, 60466130, 170510030, 481867683, 1364424829, 3870373826, 10996890237, 31293083540, 89173833915, 254445242754, 726907585652, 2079012341822

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice

References

• S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.6.
• R. A. Fisher, Contributions to Mathematical Statistics, Wiley, 1950, 41.399.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 500 terms from C. G. Bower)
• A. L. Agore, A. Chirvasitu, and G. Militaru, The set-theoretic Yang-Baxter equation, Kimura semigroups and functional graphs, arXiv:2303.06700 [math.QA], 2023.
• C. G. Bower, Transforms (2)
• Oscar Defrain, Antonio E. Porreca and Ekaterina Timofeeva, Polynomial-delay generation of functional digraphs up to isomorphism, Disc. Appl. Math., vol 357 (2024), pp. 24-33.
• Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, 2009; see page 480
• R. K. Guy, Letter to N. J. A. Sloane, 1988-04-12 (annotated scanned copy)
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 118

Crossrefs

Row sums of A339428.

Cf. A000081, A001372.

Cf. A027852, A029852, A029853, A029868.

Programs

Maple

spec2861 := [B, {A=Prod(Z,Set(A)), B=Cycle(A)}, unlabeled]; [seq(combstruct[count](spec2861,size=n), n=1..27)];

Mathematica

Needs["Combinatorica`"];
nn = 30; s[n_, k_] := s[n, k] = a[n + 1 - k] + If[n < 2 k, 0, s[n - k, k]]; a[1] = 1; a[n_] := a[n] = Sum[a[i] s[n - 1, i] i, {i, 1, n - 1}]/(n - 1); rt = Table[a[i],{i, 1, nn}]; Apply[Plus, Table[Take[CoefficientList[CycleIndex[CyclicGroup[n], s] /. Table[s[j] -> Table[Sum[rt[[i]] x^(k * i), {i, nn}], {k, 1, nn}][[j]], {j, nn}], x], nn], {n, 30}]]  (* Geoffrey Critzer, Oct 12 2012, after code given by Robert A. Russell in A000081 *)
M = 66; A = Table[1, {M + 1}]; For[n = 1, n <= M, n++, A[[n + 1]] = 1/n * Sum[Sum[d * A[[d]], {d, Divisors[k]}] * A[[n - k + 1]], {k, n}]]; A81 = {0} ~ Join ~ A; H[t_] = A81.t^Range[0, Length[A81] - 1]; L = Sum[EulerPhi[j]/j * Log[1/(1 - H[x^j])], {j, M}] + O[x]^M; CoefficientList[L, x] // Rest (* Jean-François Alcover, Dec 28 2019, after Joerg Arndt *)

PARI

N=66;  A=vector(N+1, j, 1);
for (n=1, N, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d * A[d]) * A[n-k+1] ) );
A000081=concat([0], A);
H(t)=subst(Ser(A000081, 't), 't, t);
x='x+O('x^N);
L=sum(j=1,N, eulerphi(j)/j * log(1/(1-H(x^j))));
Vec(L)
\\ Joerg Arndt, Jul 10 2014

Formula

CIK transform of A000081.

a(n) = A000081 + A027852 + A029852 + A029853 + A029868 + ... - Geoffrey Critzer, Oct 12 2012

Extensions

More terms from Philippe Flajolet and Paul Zimmermann, Mar 15 1996