Number of functions $f:\{1,...,n\}\to\{1,...,n\}$ that have $|f^{-1}(\{i\})|=i$ for some $i$ 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.
 A: 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.
A: 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 $$
