|
%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
|
