OFFSET
0,4
REFERENCES
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009.
LINKS
Darij Grinberg, Marko Riedel, Markus Scheuer, et al., Math.StackExchange, Number of functions f:[n]->[n] such that there exists an i such that |f^(-1)(i)| = i.
FORMULA
a(n) = n! * [z^n] Product_{k=1..n} (exp(z) - z^k/k!).
a(n) = n! * [z^n] Product_{k=1..n} (Sum_{q=0..k-1} z^q/q! + Sum_{q=k+1..n} z^q/q!).
a(n) = n^n - A331538(n).
EXAMPLE
For n = 0: a(0) = 0! [z^0] 1 = 1.
Functions from [2]->[2] are
* [1,1] - pre-images are [1,2] and [], one contribution
* [1,2] - pre-images are [1] and [2], pre-image of one has one element, no contribution
* [2,1] - pre-images are [2] and [1], pre-image of one has one element, no contribution
+ [2,2] - pre-images are [] and [1,2], pre-image of two has two elements, no contribution
= total contributions is one.
PROG
(PARI) a(n)={n!*polcoef(prod(k=1, n, exp(x + O(x*x^n)) - x^k/k!), n)} \\ Andrew Howroyd, Jan 19 2020
CROSSREFS
KEYWORD
nonn
AUTHOR
Marko Riedel, Jan 19 2020
STATUS
approved