login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001372 Number of mappings (or mapping patterns) from n points to themselves; number of endofunctions.
(Formerly M2671 N1069)
33
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

Christian G. Bower, Table of n, a(n) for n = 0..500

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

N. G. de Bruijn, 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

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

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

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

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

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 A049117 A146810

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.

Added line to the Maple code to show how to obtain the output by W. Edwin Clark, Nov 23 2010

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 23 02:46 EDT 2017. Contains 286909 sequences.