A001372 - OEIS

%I M2671 N1069 #114 Jun 30 2024 16:39:44

%S 1,1,3,7,19,47,130,343,951,2615,7318,20491,57903,163898,466199,

%T 1328993,3799624,10884049,31241170,89814958,258604642,745568756,

%U 2152118306,6218869389,17988233052,52078309200,150899223268,437571896993,1269755237948,3687025544605,10712682919341,31143566495273,90587953109272,263627037547365

%N Number of unlabeled mappings (or mapping patterns) from n points to themselves; number of unlabeled endofunctions.

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

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

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

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

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Alois P. Heinz, <a href="/A001372/b001372.txt">Table of n, a(n) for n = 0..1000</a> (first 501 terms from Christian G. Bower)

%H A. L. Agore, A. Chirvasitu, and G. Militaru, <a href="https://arxiv.org/abs/2303.06700">The set-theoretic Yang-Baxter equation, Kimura semigroups and functional graphs</a>, arXiv:2303.06700 [math.QA], 2023.

%H N. G. de Bruijn, <a href="http://dx.doi.org/10.1016/0097-3165(72)90081-7">Enumeration of mapping patterns</a>, J. Combin. Theory, 12 (1972), 14-20.

%H N. G. de Bruijn and D. A. Klarner, <a href="http://dx.doi.org/10.1137/0603037">Multisets of aperiodic cycles</a>, SIAM J. Algebraic Discrete Methods 3 (1982), no. 3, 359--368. MR0666861(84i:05008).

%H Robert L. Davis, <a href="http://dx.doi.org/10.1090/S0002-9939-1953-0055294-2">The number of structures of finite relations</a>, Proc. Amer. Math. Soc. 4 (1953), 486-495.

%H Oscar Defrain, Antonio E. Porreca and Ekaterina Timofeeva, <a href="https://arxiv.org/abs/2302.13832">Polynomial-delay generation of functional digraphs up to isomorphism</a>, arXiv:2302.13832 [cs.DS], 2023-2024.

%H Oscar Defrain, Antonio E. Porreca and Ekaterina Timofeeva, <a href="https://doi.org/10.1016/j.dam.2024.05.030">Polynomial-delay generation of functional digraphs up to isomorphism</a>, Disc. Appl. Math., vol 357 (2024), pp. 24-33.

%H Philippe Flajolet and Robert Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 480

%H Alexander Heaton, Songpon Sriwongsa, and Jeb F. Willenbring, <a href="https://doi.org/10.5802/alco.138">Branching from the General Linear Group to the Symmetric Group and the Principal Embedding</a>, Algebraic Combinatorics, vol. 4, issue 2 (2021), p. 189-200.

%H Florent Hivert, Jean-Christophe Novelli, and Jean-Yves Thibon, <a href="https://arxiv.org/abs/math/0605262">Commutative combinatorial Hopf algebras</a>, arXiv:math/0605262 [math.CO], 2006.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=144">Encyclopedia of Combinatorial Structures 144</a>

%H Sujoy Mukherjee and Petr Vojtěchovský, <a href="https://www.cs.du.edu/~petr/data/papers/minimal_representatives_of_endofunctions.pdf">Minimal representatives of endofunctions</a>, Univ. Denver (2024).

%H Ronald C. Read, <a href="http://dx.doi.org/10.1007/BF01342974">Note on number of functional digraphs</a>, Math. Ann., vol. 143 (1961), pp. 109-111.

%H Marko Riedel, stackexchange.com, <a href="https://math.stackexchange.com/questions/416811/">Enumeration of functions by Simultaneous Power Group Enumeration (SPGE)</a>

%H Marko Riedel, <a href="/A001372/a001372.maple.txt">Maple code for sequence using SPGE</a>

%H Sara Riva, <a href="https://theses.hal.science/tel-03937258/document">Factorisation of Discrete Dynamical Systems</a>, Ph.D. Thesis, Univ. Côte d'Azur (France 2023).

%H N. J. A. Sloane, <a href="/A001372/a001372.gif">Illustration of initial terms</a>

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

%H P. R. Stein, <a href="/A000048/a000048.pdf">Letter to N. J. A. Sloane, Jun 02 1971</a>

%F Euler transform of A002861.

%F 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

%e The a(3) = 7 mappings are:

%e 1->1, 2->2, 3->3

%e 1->1, 2->2, 3->1 (equiv. to 1->1, 2->2, 3->2, or 1->1, 2->1, 3->3, etc.)

%e 1->1, 2->3, 3->2

%e 1->1, 2->1, 3->2

%e 1->1, 2->1, 3->1

%e 1->2, 2->3, 3->1

%e 1->2, 2->1, 3->1

%p with(combstruct): M[ 2671 ] := [ F,{F=Set(K), K=Cycle(T), T=Prod(Z,Set(T))},unlabeled ]:

%p a:=seq(count(M[2671],size=n),n=0..27); # added by _W. Edwin Clark_, Nov 23 2010

%t Needs["Combinatorica`"];

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

%t 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_ *)

%o (PARI) N=66;  A=vector(N+1, j, 1);

%o for (n=1, N, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d * A[d]) * A[n-k+1] ) );

%o A000081=concat([0], A);

%o H(t)=subst(Ser(A000081, 't), 't, t);

%o x='x+O('x^N);

%o F=1/prod(n=1,N, 1 - H(x^n));

%o Vec(F)

%o \\ _Joerg Arndt_, Jul 10 2014

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

%K nonn,nice,easy

%O 0,3

%A _N. J. A. Sloane_

%E More terms etc. from _Paul Zimmermann_, Mar 15 1996

%E Name edited by _Keith J. Bauer_, Jan 07 2024