Question

How many onto functions are there from an n-element set to an m-element set?

Answer 1

Answer on Question #39341 – Math – Abstract Algebra

Question. How many onto functions are there from an $n$-element set to an $m$-element set?

Solution. Let $N=\{1,\ldots,n\}$, and $M=\{1,\ldots,m\}$ and $Q(n,m)$ be the number of surjective functions $N\to M$. For every finite set $X$ denote by $|X|$ the number of elements in $X$.

If $n<m$, then there is no such function, that is

$Q(n,m)=0,\qquad n<m.$

Thus assume that $n\geq m$.

Notice that in general, the number of all functions $N\to M$ is $m^{n}$. Let $T(n,m,k)$ be the number of functions $f:N\to M$ whose image consists exactly of $k$ elements, so $|f(N)|=k$. Then

$Q(n,m)=T(n,m,m).$

Let $X\subset M$ be a subset such that $|X|=k$ and $0<k<m$. Then the number of function $f:N\to M$ such that $f(N)=X$ is equal to

$Q(n,k).$

The number of $k$-element subsets of $M$ is equal to the binomial coefficient

$C_{k}^{m}=\frac{m!}{k!(m-k)!}.$

Therefore

$T(n,m,k)=C_{k}^{m}Q(n,k).$

Hence the number of surjective functions $N\to M$ is equal to

$Q(n,m)$ $=m^{n}-T(n,m,m-1)-T(n,m,m-2)-\cdots-T(n,m,1)$

$=m^{n}-C_{m-1}^{m}Q(n,m-1)-C_{m-2}^{m}Q(n,m-2)-\cdots-C_{1}^{m}Q(n,1).$

Now let us compute $Q(n,m)$ for small values of $m$ to find a general rule for $Q(n,m)$.

If $m=1$, then there exists only one function $N\to M=\{1\}$, so

$Q(n,1)=1.$

Suppose $m=2$, and let $f:N\to M=\{1,2\}$ be any surjective function. Then we obtain a partition of $N$ into two non-empty sets:

$f^{-1}(1),\qquad f^{-1}(2).$

In fact, $f^{-1}(2)=N\setminus f^{-1}(1)$, and so $f$ is uniquely determined by the set $f^{-1}(1)$. Conversely, any subset $X\subset N$ distinct from two sets $\varnothing$ and $X$ determines a unique function:

$f:N\to M,\qquad f(X)=1,\qquad,f(N\setminus X)=2.$

The number of all subsets in $N$ is $2^{n}$, whence the number all subsets of $N$ distinct from $\varnothing$ and $X$, that is the number of onto functions $N\to M$ is $2^{n}-2$. Thus

$Q(n,2)=2^{n}-2.$

Let $m=3$. Then

$Q(n,3)$ $=3^{n}-C_{2}^{3}Q(n,2)-C_{1}^{3}Q(n,1)$

$=3^{n}-3(2^{n}-2)-3=3^{n}-3\cdot 2^{n}+3.$

Answer on Question #39341 - Math - Abstract Algebra

For $m = 4$ we have

$$\begin{array}{l} Q(n, 4) = 4^n - C_3^4 Q(n, 3) - C_2^4 Q(n, 2) - C_1^4 Q(n, 1) \\ = 4^n - 4(3^n - 3 \cdot 2^n + 3) - 6(2^n - 2) - 4 \\ = 4^n - 4 \cdot 3^n + 12 \cdot 2^n - 12 - 6 \cdot 2^n + 12 - 4 \\ = 4^n - 4 \cdot 3^n + 6 \cdot 2^n - 4. \end{array}$$

We see that for $m = 1,2,3,4$ the following formula holds true:

$$\begin{array}{l} Q(n, 1) = C_1^1 \cdot 1^n, \\ Q(n, 2) = C_2^2 \cdot 2^n - C_1^2 \cdot 1^n, \\ Q(n, 3) = C_3^3 \cdot 3^n - C_2^3 \cdot 2^n + C_1^3 \cdot 1^n, \\ Q(n, 4) = C_4^4 \cdot 4^n - C_3^4 \cdot 3^n + C_2^4 \cdot 2^n - C_1^4 \cdot 1^n. \end{array}$$

Let us prove that

$$Q(n, m) = m^n - C_{m-1}^m (m - 1)^n + C_{m-2}^m (m - 2)^n - C_{m-3}^m (m - 3)^n \cdots$$

For $i \in M$ let

$$F_i = \{f : N \to M \mid f(X) \subset M \setminus \{i\}\}$$

be the set of functions $f: N \to M$ whose image does not contain $i$ and $F$ be the set of all functions $f: N \to M$.

Then the number of all surjective functions $f: N \to M$ is equal to

$$\left| \bigcap_{i=1}^m (F \setminus F_i) \right| = \left| F \setminus \bigcup_{i=1}^m F_i \right| |F| - \left| \bigcup_{i=1}^m F_i \right|.$$

Notice that for any family $\{F_i\}$ of subsets of a set $F$ we have that

$$\begin{array}{l} \left| \bigcup_{i=1}^m F_i \right| = \sum_i |F_i| - \sum_{i_1 < i_2} |F_{i_1} \cap F_{i_2}| + \sum_{i_1 < i_2 < i_3} |F_{i_1} \cap F_{i_2} \cap F_{i_3}| + \cdots \\ \cdots + (-1)^{m-1} |F_1 \cap F_2 \cap \cdots \cap F_m|. \end{array}$$

Indeed, suppose $x \in \bigcup_{i=1}^m F_i$ belongs exactly to $k$ subsets, say $F_1, \ldots, F_k$. Then $x$ is counted in

$$\sum_i |F_i|$$

$k = C_1^m$ times, in

$$\sum_{i_1 < i_2} |F_{i_1} \cap F_{i_2}|$$

$C_2^m$ times, in

$$\sum_{i_1 < i_2 < i_3} |F_{i_1} \cap F_{i_2} \cap F_{i_3}|$$

$C_3^m$ times and so on. Therefore in right hand side $x$ will be counted

$$a = C_1^m - C_2^m + C_3^m - \cdots + (-1)^{m-1} C_m^m$$

times. But from the identity

$$\begin{array}{l} 0 = (1 - 1)^m = C_0^m - C_1^m + C_2^m - C_3^m + \cdots + (-1)^{m-1} C_m^m \\ = C_0^m - a = 1 - a, \end{array}$$

Answer on Question #39341 - Math - Abstract Algebra

we get that

$$a = C _ {1} ^ {m} - C _ {2} ^ {m} + C _ {3} ^ {m} - \dots + (- 1) ^ {m - 1} C _ {m} ^ {m} = 1.$$

This proves (2).

Now turning back to (1) notice that

$$\left| F _ {i} \right| = (m - 1) ^ {n}.$$

Also

$$\left| F _ {i _ {1}} \cap F _ {i _ {2}} \cap \dots \cap F _ {i _ {k}} \right|$$

is the set of all functions $N \to M \setminus \{i_1, \ldots, i_k\}$ , and so this number is $(m - k)^n$ . Hence

$$\sum_ {i _ {1} < i _ {2} < \dots < i _ {k}} | F _ {i _ {1}} \cap F _ {i _ {2}} \cap \dots \cap F _ {i _ {k}} | = C _ {k} ^ {m} (m - k) ^ {n}.$$

Therefore

$$\begin{array}{l} \left| \bigcup_ {i = 1} ^ {m} F _ {i} \right| = \sum_ {i} | F _ {i} | - \sum_ {i _ {1} < i _ {2}} | F _ {i _ {1}} \cap F _ {i _ {2}} | + \sum_ {i _ {1} < i _ {2} < i _ {3}} | F _ {i _ {1}} \cap F _ {i _ {2}} \cap F _ {i _ {3}} | + \dots \\ \dots + (- 1) ^ {m - 1} \left| F _ {1} \cap F _ {2} \cap \dots \cap F _ {m} \right| = \\ = C _ {m - 1} ^ {m} (m - 1) ^ {n} - C _ {m - 2} ^ {m} (m - 2) ^ {n} + C _ {m - 3} ^ {m} (m - 3) ^ {n} \dots \\ \end{array}$$

Thus

$$\begin{array}{l} Q (n, m) = \left| \bigcap_ {i = 1} ^ {m} (F \setminus F _ {i}) \right| = | F | - \left| \bigcup_ {i = 1} ^ {m} F _ {i} \right| = \\ = m ^ {n} - C _ {m - 1} ^ {m} (m - 1) ^ {n} + C _ {m - 2} ^ {m} (m - 2) ^ {n} - C _ {m - 3} ^ {m} (m - 3) ^ {n} \dots \\ \end{array}$$

Answer. The number of onto functions from an $n$ -element set to an $m$ -element set is

$$Q (n, m) = 0, \qquad n < m$$

and

$$Q (n, m) = m ^ {n} - C _ {m - 1} ^ {m} (m - 1) ^ {n} + C _ {m - 2} ^ {m} (m - 2) ^ {n} - C _ {m - 3} ^ {m} (m - 3) ^ {n} \dots$$

for $n\geq m$