login
Number of functions f:[n]->[n] such that there exists a k such that |f^(-1)(k)| = k.
1

%I #19 Feb 12 2021 12:06:00

%S 0,1,3,16,147,1756,25910,453594,9184091,211075288,5427652794,

%T 154380255250,4812088559014,163110595450466,5973198636395003,

%U 235010723141883563,9886231689434154971,442799642855527526848,21038043034795035118742,1056802542597653892224802,55962024535834950971809754

%N Number of functions f:[n]->[n] such that there exists a k such that |f^(-1)(k)| = k.

%D P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009.

%H Darij Grinberg, Marko Riedel, Markus Scheuer, et al., Math.StackExchange, <a href="https://math.stackexchange.com/questions/3509979/">Number of functions f:[n]->[n] such that there exists an i such that |f^(-1)(i)| = i.</a>

%F a(n) = n^n - n! * [z^n] Product_{k=1..n} (exp(z) - z^k/k!).

%F a(n) = n^n - n! * [z^n] Product_{k=1..n} (Sum_{q=0..k-1} z^q/q! + Sum_{q=k+1..n} z^q/q!).

%F a(n) = n^n - A331537(n).

%e For n = 0: a(0) = 0^0 - 0! [z^0] 1 = 0.

%e Functions from [2]->[2] are

%e * [1,1] - pre-images are [1,2] and [], no contribution

%e * [1,2] - pre-images are [1] and [2], pre-image of one has one element, one contribution

%e * [2,1] - pre-images are [2] and [1], pre-image of one has one element, one contribution

%e + [2,2] - pre-images are [] and [1,2], pre-image of two has two elements, one contribution

%e = total contributions is three.

%o (PARI) a(n)={n^n - n!*polcoef(prod(k=1, n, exp(x + O(x*x^n)) - x^k/k!), n)} \\ _Andrew Howroyd_, Jan 19 2020

%Y Cf. A000312, A331537.

%K nonn

%O 0,3

%A _Marko Riedel_, Jan 19 2020