8
$\begingroup$

Let $m,n$ be two integers such that, $m\ge n$. Compute the number of surjections from $\{1,...,m\}$ to $\{1,...,n\}$

There are $n^m$ functions (total).

we subtract from $n^m$ the number of non-surjective functions.

There are $\binom{n}{1}(n-1)^m$ functions missing one element.

There are $\binom{n}{2}(n-2)^m$ functions missing two elements, but how many times did we count this in the previous count ?

Then we have to add this again by inclusion-exclusion but why is the difference always 1?

$\endgroup$
5
  • $\begingroup$ See this question $\endgroup$ Commented Mar 18, 2014 at 15:33
  • $\begingroup$ @Omnomnomnom yes this is a special case if $n=3$. My question is if we have functions, which don't hit at least one element, we count also the functions, which don't hit at least two elements, and these we have counted exactly twice. To compensate this miscount we add this again, and the net count is always 1 $\endgroup$
    – OBDA
    Commented Mar 18, 2014 at 15:44
  • $\begingroup$ Ah, I misread the intent of your question. Not sure why. $\endgroup$ Commented Mar 18, 2014 at 15:47
  • $\begingroup$ Have you studied the Stirling numbers? $\endgroup$
    – Mike F
    Commented Mar 18, 2014 at 16:02
  • $\begingroup$ @Mike No I only saw the Stirling's formula. $\endgroup$
    – OBDA
    Commented Mar 18, 2014 at 16:05

3 Answers 3

12
$\begingroup$

For all $1 \le i \le n$ define $$A_i = \{\rho \colon M \to N \text{ a mapping such that } i \notin \rho(M)\}.$$ Then $$S = \{\rho \colon M \to N\} \setminus \bigcup_{i=1}^n A_i$$ is the set of surjections.

By the principle of inclusion and exclusion, we may calculate $$|S| = |\{\rho \colon M \to N\}| - \sum_{1 \le i_1 \le n} |A_i| + \sum_{1 \le i_1 < i_2 \le n} |A_{i_1} \cap A_{i_2}| - \dots \pm |A_1 \cap \dots \cap A_n|.$$ Now $|\{\rho \colon M \to N\}| = n^m$. We also have $$A_{i_1} \cap \dots \cap A_{i_k} = \{\rho \colon M \to N \text{ a mapping such that } \{i_1,\dots,i_k\} \cap \rho(M) = \emptyset\},$$ so that $|A_{i_1} \cap \dots \cap A_{i_k}| = (n-k)^m$. Each sum contains ${n \choose k}$ terms, so we have $$|S| = n^m - {n \choose 1}(n-1)^m + {n \choose 2}(n-2)^m - \dots \pm {n \choose n}(n-n)^m.$$

$\endgroup$
1
  • $\begingroup$ Question in relation to this but not necessarily on topic, if we map a set to a subset of itself, i.e. $M=\{1,...,m\}$, $N\subset M=\{1,...,n\}$ where $m>n$. This way we can say that in some surjections, some elements may be mapped to themselves. Is there a way to modify this formula to restrict it to these cases? $\endgroup$
    – Jepsilon
    Commented Apr 28, 2018 at 13:21
6
$\begingroup$

For every pair of natural numbers $m\geq n$ let $\phi(m,n)$ be the number of surjections from a set with $m$ elements onto a set with $n$ elements.

We have $\phi(m,1)=1$ and $\phi(m,2)=2^m-2$. To compute $\phi(m,3)$ take $3^m$ and substract $\binom 32 \phi(m,2)+\binom 31 \phi(m,1)$.

Generalizing, $$\begin{align} \phi(m,n)&=n^m-\sum_{j=1}^{n-1}\binom nj\phi(m,j)=\\ &=n^m-\binom n{n-1}(n-1)^m+\sum_{j=1}^{n-2}\binom nj\phi(m,j)=\\ &=\sum_{j=0}^{n-1}(-1)^j\binom n{n-j}(n-j)^m \end{align}$$

$\endgroup$
1
  • 1
    $\begingroup$ You can write this as Stirling numbers of the 2nd kind: $\phi(m, n) = n!S(m, n)$. $\endgroup$
    – Elmex80s
    Commented Jun 14, 2018 at 15:21
1
$\begingroup$

The number of surjective mappings from an $n$-element set onto a $k$-element set is $$k!\cdot S(n,k),$$ where $S(n,k)$ is the Stirling number of the 2nd kind, i.e., the number of partitions of the $n$-element set into $k$ elements (blocks).

In the proof, one first constructs for each partition $P$ of the $n$-set into $k$ blocks a surjective function $f_P$. There are $S(n,k)$ such functions.

In the second part, each such function $f_P$ is composed with a permutation of the $k$-set $\pi$. This gives the surjective function $\pi\circ f_P$. The number of such permutations is $k!$.

All such functions $\pi\circ f_P$ are distinct for distinct $\pi,P$. Conversely, it is important to say that each surjection from an $n$-set onto a $k$-set arises in the form $\pi\circ f_P$. Hence, the result follows.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .