A001372 Number of mappings (or mapping patterns) from n points to themselves; number of endofunctions. (Formerly M2671 N1069)

1, 1, 3, 7, 19, 47, 130, 343, 951, 2615, 7318, 20491, 57903, 163898, 466199, 1328993, 3799624, 10884049, 31241170, 89814958, 258604642, 745568756, 2152118306, 6218869389, 17988233052, 52078309200, 150899223268, 437571896993, 1269755237948, 3687025544605, 10712682919341, 31143566495273, 90587953109272, 263627037547365

Offset

0,3

References

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, pp. 41, 209.

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.6.

R. A. Fisher, Contributions to Mathematical Statistics, Wiley, 1950, 41.401.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 70, Table 3.4.1.

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 = 0..1000 (first 501 terms from Christian 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.

N. G. de Bruijn, Enumeration of mapping patterns, J. Combin. Theory, 12 (1972), 14-20.

N. G. de Bruijn and D. A. Klarner, Multisets of aperiodic cycles, SIAM J. Algebraic Discrete Methods 3 (1982), no. 3, 359--368. MR0666861(84i:05008).

R. L. Davis, The number of structures of finite relations, Proc. Amer. Math. Soc. 4 (1953), 486-495.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 480

A. Heaton, S. Sriwongsa and J. F. Willenbring, Branching from the General Linear Group to the Symmetric Group and the Principal Embedding, Algebraic Combinatorics, vol. 4, issue 2 (2021), p. 189--200.

F. Hivert, J.-C. Novelli and J.-Y. Thibon, Commutative combinatorial Hopf algebras, arXiv:math/0605262 [math.CO], 2006.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 144

Antonio E. Porreca and Ekaterina Timofeeva, Polynomial-delay generation of functional digraphs up to isomorphism, arXiv:2302.13832 [cs.DS], 2023.

Ronald C. Read, Note on number of functional digraphs, Math. Ann., vol. 143 (1961), pp. 109-111.

Marko Riedel, stackexchange.com, Enumeration of functions by Simultaneous Power Group Enumeration (SPGE)

Marko Riedel, Maple code for sequence using SPGE

Sara Riva, Factorisation of Discrete Dynamical Systems, Ph.D. Thesis, Univ. Côte d'Azur (France 2023).

N. J. A. Sloane, Illustration of initial terms

N. J. A. Sloane, Transforms

P. R. Stein, Letter to N. J. A. Sloane, Jun 02 1971

Formula

Euler transform of A002861.

a(n) ~ c * d^n / sqrt(n), where d = A051491 = 2.9557652856519949747148... (Otter's rooted tree constant), c = 0.442876769782206479836... (for a closed form see "Mathematical Constants", p.308). - Vaclav Kotesovec, Mar 17 2015

Example

The a(3) = 7 mappings are:
1->1, 2->2, 3->3
1->1, 2->2, 3->1 (equiv. to 1->1, 2->2, 3->2, or 1->1, 2->1, 3->3, etc.)
1->1, 2->3, 3->2
1->1, 2->1, 3->2
1->1, 2->1, 3->1
1->2, 2->3, 3->1
1->2, 2->1, 3->1

Maple

with(combstruct): M[ 2671 ] := [ F, {F=Set(K), K=Cycle(T), T=Prod(Z, Set(T))}, unlabeled ]:
a:=seq(count(M[2671], size=n), n=0..27); # added by W. Edwin Clark, Nov 23 2010

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}]; c=Drop[Apply[Plus, Table[Take[CoefficientList[CycleIndex[CyclicGroup[n], s]/.Table[s[j]->Table[Sum[rt[[i]] x^(k*i), {i, 1, nn}], {k, 1, nn}][[j]], {j, 1, nn}], x], nn], {n, 1, 30}]], 1]; CoefficientList[Series[Product[1/(1-x^i)^c[[i]], {i, 1, nn-1}], {x, 0, nn}], x]  (* after code given by Robert A. Russell in A000081 *) (* Geoffrey Critzer, Oct 12 2012 *)
max = 40; A[n_] := A[n] = If[n <= 1, n, Sum[DivisorSum[j, #*A[#]&]*A[n-j], {j, 1, n-1}]/(n-1)]; H[t_] := Sum[A[n]*t^n, {n, 0, max}]; F = 1 / Product[1 - H[x^n], {n, 1, max}] + O[x]^max; CoefficientList[F, x] (* Jean-François Alcover, Dec 01 2015, 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);
F=1/prod(n=1, N, 1 - H(x^n));
Vec(F)
\\ Joerg Arndt, Jul 10 2014

Crossrefs

Cf. A000312, A002861, A006961, A001373, A054050, A054745.

Sequence in context: A026581 A151535 A181360 * A179467 A308153 A049117

Adjacent sequences: A001369 A001370 A001371 * A001373 A001374 A001375

Keyword

nonn,nice,easy

Author

N. J. A. Sloane

Extensions

More terms etc. from Paul Zimmermann, Mar 15 1996

Status

approved