Posted by Jason Polak on 01. March 2017 · Write a comment · Categories: combinatorics

In this post we’ll give formulas for the number of bijective, injective, and surjective functions from one finite set to another. Although it’s not difficult, a formula for the number of surjective functions was one of the first problems I solved as an undergrad that got me interested in recurrence relations and combinatorics.

Let’s use the notation $[n] = \{ 1,2,\dots,n\}$ for an $n$-element set.

Bijective Functions

The number of bijective functions $[n]\to [n]$ is the familiar factorial:
$$n! = 1\times 2\times\cdots\times n$$
Another name for a bijection $[n]\to [n]$ is a permutation. In fact, the set all permutations $[n]\to [n]$ form a group whose multiplication is function composition. Here is a table of some small factorials:

n n! n n!
0 1 7 5040
1 1 8 40320
2 2 9 362880
3 6 10 3628800
4 24 11 39916800
5 120 12 479001600
6 720 13 6227020800

Injective Functions

What about injective functions $[k]\to[n]$ where $1 \leq k\leq n$? In that case, the image in $[n]$ consists of $k$ elements, and the order in which they are chosen determines the function, so the number of injective functions $[k]\to [n]$ is
$$k!\binom{n}{k} = \frac{n!}{(n-k)!}$$
Sometimes this is denoted by nPk on calculators. For example, 73P5 = 1802440080.

Surjective Functions

Calculating the number of surjective functions $[n]\to [k]$ where $n\geq k \geq 1$ is the most interesting. Let’s denote by $S(n,k)$ this number. For example, $S(n,n) = n!$ and $S(n,1) = 1$. A degenerate case is $S(0,0) = 1$, though $S(n,0) = 0$. Another easy to calculate one is $S(n,2) = 2^n – 2$: this is because there are $2^n$ functions $[n]\to [2]$, but two of them send everything to just one element. What about an explicit formula in general?

The most natural thing to do is perhaps come up with a recurrence relation. So let’s divide up the number of surjective functions into two classes: the first is where if we restrict the function to $[n-1]$, we still get a surjective function. It’s clear there are $kS(n-1,k)$ of these. On the other hand, if after restricting to $[n-1]$ the function is no longer surjective, then there are $kS(n-1,k-1)$ of these, because to make such a function you choose one element in $[k]$ that has $n$ mapping to it, and then a surjective function $[n-1]$ onto the remaining $k-1$ elements. Thus, we have the recurrence relation:
$$S(n,k) = kS(n-1,k) + kS(n-1,k-1).$$
At this point, it’d be easy to compute $S(n,k)$ for small values of $n$ and $k$ by hand, or via a computer using a recursive function. What about an explicit formula that is not a recurrence relation?

To find one, we can use the generating function technique. Write $A_k(x) = \sum_n S(n,k)x^n$. Multiplying the recurrence relation by $x^n$ and summing over all $n$ gives the relation
$$A_k(x) = \frac{kx}{1 – kx}A_{k-1}(x).$$
We also have $A_0(x) = 1$ because the only nonzero term in $A_0$ is $S(0,0)x^0$. Therefore, we have an explicit formula for this generating function
$$A_k(x) = \frac{k!x^k}{(1-x)(1-2x)\cdots(1-kx)}.$$
Now, if we split this fraction up using partial fractions into a sum of the form
$$\sum_{j=1}^k \frac{a_j}{1-jx}$$
we find that
$$a_j = \frac{(-1)^{k-j}}{j!(k-j)!}.$$
Now, using the fact that $(1-jx)^{-1} = 1 + jx + j^2x^2 + \cdots$ and that $S(n,k)$ is by definition the coefficient of $x^n$ in this power series, we get that
$$S(n,k) = \sum_{j=1}^k \frac{(-1)^{k-j}k!j^n}{j!(k-j)!}.$$
For example, $S(n,3) = 3(3^{n-1} – 2^n + 1)$ so that $S(12,3) = 519156$.

Some readers may recognize that this formula is very similar to the one for the number of partitions of $[n]$ into $k$ nonempty subsets. In fact it’s $k!$ times this number. That makes good combinatorial sense: to make a surjective function, you first partition $[n]$ into $k$ nonempty subsets and then in one of $k!$ ways, assign one of these subsets for each element in $[k]$.

Leave a Reply

Your email address will not be published. Required fields are marked *