A212559 Number of functions f:{1,2,...,n}->{1,2,...,n} such that every non-recurrent element has at most one preimage.

1, 1, 4, 27, 244, 2745, 36966, 580111, 10399096, 209672721, 4696872490, 115732052271, 3110867569140, 90587751885241, 2840805169411678, 95450112571474095, 3420897993621996016, 130266500391456691233, 5252293203395848789842, 223535386151669737094095, 10014286301754519472897900

Offset

0,3

Comments

An element x of {1,2,...,n} is a recurrent element if there exists a positive integer k such that (f^k)(x) = x where f^k is the k-th iteration of functional composition.

The functional digraphs are composed of cycles of rooted trees with every non-root vertex of degree 1 or 2. Cf. A006152.

Links

Table of n, a(n) for n=0..20.

Formula

E.g.f.: 1/(1-A(x)) where A(x) is the e.g.f. for A006152.

Mathematica

nn=20; a=x Exp[x/(1-x)]; Range[0, nn]! CoefficientList[Series[1/(1-a), {x, 0, nn}], x]

Crossrefs

Sequence in context: A303559 A161120 A183430 * A265268 A121063 A229619

Adjacent sequences: A212556 A212557 A212558 * A212560 A212561 A212562

Keyword

nonn

Author

Geoffrey Critzer, May 21 2012

Status

approved