Number of functions $f:\{1,...,n\}\to\{1,...,n\}$ that have $|f^{-1}(\{i\})|=i$ for some $i$

Question

Let $S=\{1,...,n\}$, I am looking at number of functions functions $f:S\to S$ such that there exists $i \in S$ such that $$|f^{-1}(\{i\})|=i$$

I am guessing I am supposed to use PIE (Principle of Inclusion and Exclusion)

I let $X=\{f:S\to S\}$. My attempt is to define $A_i=\{f\in X;|f^{-1}(\{i\})|=i\}$.

It can be computed that $|A_i|=\binom{n}{i}(n-1)^{n-i}$.

Similarly, $|A_i\cap A_j|=\binom{n}{i}\binom{n-i}{j}(n-2)^{n-i-j}$.

but I am not sure how to proceed.

Answer 1

Let $a_n, n\geq 1$ denote the number of functions $f:[n]\to[n]$ such that there exists $i\in [n]$ such that \begin{align*} |f^{-1}(\{i\})|=i \end{align*}

Calculation of $a_n$ for small numbers $n$ gives \begin{align*} (a_n)_{n\geq 1}=(1,3,16,147,1\,756,\ldots) \end{align*} which is archived in OEIS as A331538 (thanks to @MarkoRiedel).

General expression:

Using PIE we can write \begin{align*} \color{blue}{a_n}&=\sum_{j=1}^n\left|A_j\right|-\sum_{{1\leq j_1<j_2\leq n}\atop{j_1+j_2\leq n}}\left|A_{j_1}\cap A_{j_2}\right|\\ &\qquad+\cdots+(-1)^{k-1}\sum_{{1\leq j_1< j_2<\ldots<j_k\leq n}\atop{j_1+j_2+\cdots+j_k\leq n}}\left|A_{j_1}\cap A_{j_2}\cap \cdots\cap A_{j_k}\right|\pm\cdots\\ &=\sum_{j=1}^n\binom{n}{j}(n-1)^{n-j}-\sum_{{1\leq j_1<j_2\leq n}\atop{j_1+j_2\leq n}}\binom{n}{j_1,j_2,n-j_1-j_2}(n-2)^{n-j_1-j_2}\\ &\quad+\cdots+(-1)^{k-1}\sum_{{1\leq j_1<\ldots<j_k\leq n}\atop{j_1+\cdots+j_k\leq n}}\binom{n}{j_1,\ldots,j_k,n-j_1-\cdots-j_k}(n-k)^{n-j_1-\cdots -j_k}\pm\cdots\\ \end{align*}

Here we use the multinomial coefficient notation $\binom{n}{j_1,\ldots,j_k}=\frac{n!}{j_1!\cdots j_k!}$.

Main term:

The following is valid for $n\geq1$ \begin{align*} \sum_{j=1}^n\left|A_j\right|=n^n-(n-1)^n\tag{1} \end{align*}

[Simplification thanks to @darijgrinberg]: We obtain \begin{align*} \color{blue}{\sum_{j=1}^n\left|A_j\right|}&=\sum_{j=1}^n\binom{n}{j}(n-1)^{n-j}\\ &=\sum_{j=1}^n\binom{n}{j}1^j(n-1)^{n-j}\\ &=(1+(n-1))^n-(n-1)^n\\ &\,\,\color{blue}{=n^n-(n-1)^n} \end{align*} and the claim (1) follows.

Note: The sequence $\left(\sum_{j=1}^n\left|A_j\right|\right)_{n\geq 1}=(1, 3, 19, 175, 2\,101,\ldots)$ of the main terms is archived in OEIS as A045531.

Answer 2

Using combinatorial classes as in Analytic Combinatorics by Flajolet and Sedgewick we get for the complementary problem i.e. no pre-image $f^{-1}(k)$ of $k$ having $k$ elements the class

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \prod_{k=1}^n \textsc{SET}_{\ne k}(\mathcal{Z})$$

with EGF

$$F(z) = \prod_{k=1}^n \left(\exp(z)-\frac{z^k}{k!}\right).$$

The desired quantity is then given by

$$n^n - n! [z^n] F(z)$$

or

$$\bbox[5px,border:2px solid #00A000]{ n^n - n! [z^n] \prod_{k=1}^n \left(\exp(z)-\frac{z^k}{k!}\right).}$$

It appears that for computational purposes the alternate form below is slightly more efficient:

$$\bbox[5px,border:2px solid #00A000]{ n^n - n! [z^n] \prod_{k=1}^n \sum_{q=0, q\ne k}^n \frac{z^q}{q!}.}$$

Here we have used the class

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \prod_{k=1}^n \textsc{SET}_{\ne k, \le n}(\mathcal{Z}).$$

The sequence starts as follows:

$$1, 3, 16, 147, 1756, 25910, 453594, 9184091, 211075288, 5427652794, \\ 154380255250, 4812088559014, 163110595450466, 5973198636395003, \ldots $$