Counting surjective functions

functions

We have $r$ objects and $n$ boxes. I have to count all the combinations possible if the objects and boxes could be both different. If that happens I can count the number of variations from $n$ to $r$ (number of functions between objects and boxes). I mean, $n^r$.

But if I have to count all the combinations possible if anyone of the boxes is empty ($r\ge n$). Now I have to count the surjective functions.

For example if I have $r$ objects and 1 box. The number of surjective functions is 1. Then, if I have $r$ objects and 2 boxes, the number of surjective functions is $2^r-2$. And finally if I have $r$ objects and 3 boxes, I will count $3^r-2\cdot[3\cdot2^r-3]$. How do I get the formula for $r$ objects and $n$ boxes?


We want the number of surjections from $r$ to $n$.

First, note that the Stirling number of the second kind $$ \begin{Bmatrix} x\\ y \end{Bmatrix} $$ is a quantity that solves most of the puzzle: this number equals the number of partitions of $x$ into $y$-many nonempty subsets.

Clearly, every surjection $f\colon [r]\to [n]$ determines such a partition: $\{f^{-1}(j)\mid 1\le j\le n\}$, and each such partition of $r$ corresponds to $n!$ different surjections (permutations of the range). (Here, $[m]$ denotes $\{1,\dotsc,m\}$.) So the total number of surjections $[r]\to [n]$ is: $$ n! \begin{Bmatrix} r\\ n \end{Bmatrix} $$

The Stirling number of the second kind can be computed from the explicit formula $$ \begin{equation*} \begin{Bmatrix} r\\ n \end{Bmatrix} =\frac{1}{n!}\sum_{j=0}^{n}(-1)^{n-j}\binom{n}{j}j^r \end{equation*} $$ As you can see, a kind of "inclusion/exclusion" principle is at work. Various answers to the following question (the special case $n=3$ of yours) provide some intuition about why that is so: Counting the number of surjections.

Notice the factor of $\frac 1 {n!}$, which we multiplied the Stirling number of 2nd kind by when counting surjections. So finally can simplify further: the number of surjections $[r]\to [n]$ is $$ \sum_{j=0}^{n}(-1)^{n-j}\binom{n}{j}j^r $$

Related

Prove $X(\omega) = \sup\{y \in \mathbb{R}: F(y) < \omega\}$ is a random variable.
In any Pythagorean triplet at least one of them is divisible by $2$, $3$ and $5$.
Does $\zeta(-1)=-1/12$ or $\zeta(-1) \to -1/12$? [duplicate]
If : $\tan^2\alpha \tan^2\beta +\tan^2\beta \tan^2\gamma + \tan^2\gamma \tan^2\alpha + 2\tan^2\alpha \tan^2\beta \tan^2\gamma =1\dots$
Trigonometry problem
limits of sequences exponential and factorial: $a_n=e^{5\cos((\pi/6)^n)}$ and $a_n=\frac{n!}{n^n}$
Solving linear congruence $2x + 11 \equiv 7 \pmod 3$
If $a_n>0$ converges to $a>0$, then $(a_0 a_1\cdots a_n)^{\frac{1}{n}}$ converges to $a.$ [closed]
Stability region for two step Nyström method
Encode each $n_1,n_2,n_3,...∈N^N$ by an infinite sequence of 0s and 1s with infinitely many 0s, and give a proof that $N^N$ is equinumerous with $R$.
Fixed point in a continuous function
Prove X is a martingale