A001372 - OEIS

A001372

Number of unlabeled mappings (or mapping patterns) from n points to themselves; number of unlabeled 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

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

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

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

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

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

Alexander Heaton, Songpon Sriwongsa, and Jeb 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.

Florent Hivert, Jean-Christophe Novelli, and Jean-Yves Thibon, Commutative combinatorial Hopf algebras, arXiv:math/0605262 [math.CO], 2006.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 144

Sujoy Mukherjee and Petr Vojtěchovský, Minimal representatives of endofunctions, Univ. Denver (2024).

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