login
A331537
Number of functions f:[n]->[n] such that no k exists such that |f^(-1)(k)| = k.
1
1, 0, 1, 11, 109, 1369, 20746, 369949, 7593125, 176345201, 4572347206, 130931415361, 4104011889242, 139764511141787, 5138808189163013, 202883167238975812, 8560512384275396645, 384440619030809237329, 18308365040501502456682, 921617113062659696899177, 48895575464165049028190246
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
Sequence in context: A124290 A094703 A324355 * A169631 A308005 A280855
KEYWORD
nonn
AUTHOR
Marko Riedel, Jan 19 2020
STATUS
approved