A002861 - OEIS

A002861

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

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

A000081 + A027852 + A029852 + A029853 + A029868 + ... - Geoffrey Critzer, Oct 12 2012

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

FORMULA

CIK transform of A000081.

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 *)

PROG

(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

CROSSREFS

Row sums of A339428.