A215720 The number of functions f:{1,2,...,n}->{1,2,...,n}, endofunctions, such that exactly one nonrecurrent element is mapped into each recurrent element.

1, 0, 2, 6, 60, 560, 7350, 111552, 2009672, 41378976, 963527850, 25009038560, 716437784172, 22453784964624, 764345507271710, 28085186967504240, 1107971902218683280, 46710909213378892352, 2095883952368863510098, 99724281567446320231104, 5015524096516005263567540

Offset: 0

Author

Geoffrey Critzer, Aug 22 2012

Keywords

• nonn

Comments

x in {1,2,...,n} is a recurrent element if there is some k such that f^k(x) = x where f^k(x) denotes iterated functional composition. In other words, a recurrent element is in a cycle of the functional digraph.

Examples

			a(2) = 2 because we have: (1->1,2->1), (1->2,2->2).
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..150

Crossrefs

Cf. A055541, A195203, A098875.

Programs

Maple

a:= n-> `if`(n=0, 1, n! *add(i*(n-i)^(n-2*i-1)/(n-2*i)!, i=0..n/2)):
seq(a(n), n=0..30);  # Alois P. Heinz, Aug 22 2012

Mathematica

nn = 20; t = Sum[n^(n - 1) x^n/n!, {n, 1, nn}];
Range[0, nn]! CoefficientList[Series[1/(1 - x t) , {x, 0, nn}], x]

Formula

E.g.f.: 1/(1 - x*T(x)) where T(x) is the e.g.f. for A000169.

a(n) = n! * Sum_{i=0..floor(n/2)} i*(n-i)^(n-2*i-1)/(n-2*i)! for n>0, a(0) = 1. - Alois P. Heinz, Aug 22 2012

a(n) ~ exp(1)/(exp(1)-1)^2 * n^(n-1). - Vaclav Kotesovec, Sep 30 2013