login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

REFERENCES

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

LINKS

Table of n, a(n) for n=0..20.

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

Cf. A000312, A331538.

Sequence in context: A124290 A094703 A324355 * A169631 A308005 A280855

Adjacent sequences:  A331534 A331535 A331536 * A331538 A331539 A331540

KEYWORD

nonn

AUTHOR

Marko Riedel, Jan 19 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 28 18:44 EDT 2022. Contains 354907 sequences. (Running on oeis4.)