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,3

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.

Links

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

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

Example

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

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]

Crossrefs

Cf. A055541, A195203, A098875.

Sequence in context: A376515 A362702 A356259 * A376492 A371018 A376476

Adjacent sequences: A215717 A215718 A215719 * A215721 A215722 A215723

Keyword

nonn

Author

Geoffrey Critzer, Aug 22 2012

Status

approved