Counting bijective, injective, and surjective functions

Here I derive formulas for the number of bijective, injective, and surjective functions from one finite set to another. Actually, computing the number of bijective and injective functions is easy. But computing the number of surjective functions is much harder.

I like this problem a lot because it was one of the first problems I solved as an undergrad that got me interested in recurrence relations and combinatorics.

Anyway, 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:

Here’s a graph of $\log(n!)$ so you can see the rapid growth of the factorial visually:

Quite a few functions, don’t you think?

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]$.