This is a guest post by researcher Audace Dossou-Olory of Stellenbosch University, South Africa.

In assignment problems, one wants to find an optimal and efficient way to assign objects of a given set to objects of another given set. An assignment can be regarded as a bijective map $\pi$ between two finite sets $E$ and $F$ of $n\geq 1$ elements. By identifying the sets $E$ and $F$ with $\{1,2,\ldots, n\}$, we can represent an assignment by a permutation.

Permutations

A permutation $\pi$ can be described by the sequence

$\Big(\pi(1),\pi(2),\ldots, \pi(n) \Big)$

which means $1,2,\ldots, n$ are mapped to $\pi(1),\pi(2),\ldots, \pi(n)$, respectively. The number of permutations of $\{1,2,\ldots, n\}$ is the number of ways to arrange $1,2,\ldots, n$ in a row, which is given by $1\cdot 2 \cdot \ldots \cdot n=n!$. For instance, all the $4!=24$ permutations of $\{1,2,\ldots, 4\}$ are given by

\begin{align*}
&1234,~1243,~1324,~1342,~1423,~1432,\\
&2134,~2143,~2314,~2341,~2413,~2431,\\
&3124,~3142,~3214,~3241,~3412,~3421,\\
&4123,~4132,~4213,~4231,~4312,~4321\,.
\end{align*}

If $(a_1~a_2~\ldots~a_n)$ is a permutation such that

$\pi(a_1)=a_2,~\pi(a_2)=a_3,~\ldots,\pi(a_{n-1})=a_n,~\pi(a_n)=a_1$

then $(a_1~a_2~\ldots~a_n)$ is called a cycle. In fact, every permutation can be broken up into cycles that do not have any common elements. For example,

\begin{align*}
&(1)(2)(3)(4),~(1)(2)(34),~(1)(23)(4),~(1)(234),~(1)(243),~(1)(24)(3),\\
&(12)(3)(4),~(12)(34),~(123)(4),~(1234),~(1243),~(124)(3),\\
&(132)(4),~(1342),~(13)(2)(4),~(134)(2),~(13)(24),~(1324),\\
&(1432),~(142)(3),~(143)(2),~(14)(2)(3),~(1423),~(14)(23)
\end{align*}

are the cycle decompositions of the permutations of $\{1,2,\ldots, 4\}$. The permutations

$(1432),~(1)(234),~(1)(24)(3),~(1)(2)(3)(4)$

have one, two, three and four cycles, respectively.

Stirling Numbers

Given a positive integer $1\leq k \leq n$, can we answer the question what is the total number of permutations of $\{1,2,\ldots, n\}$ of $k$ cycles? Denote by $S(n;k)$ the number of permutations of $\{1,2,\ldots, n\}$ that have exactly $k$ cycles. For $n=4$, the counts gives

$S(n;1)=6,~S(n;2)=11,~S(n;3)=6,~S(n;4)=1\,.$

The $S(n;k)$’s are known as the Stirling numbers of the first kind, in honour of James Stirling who first discovered them and put them forward in the late 1800’s.

Unfortunately, there is no nice formula for $S(n;k)$. However, mathematicians have proved that when expanding the product

$\boldsymbol{t(t+1)\ldots (t+n-2)(t+n-1)}$

into sum and collecting $t$-like terms, the coefficient of $t^k$ is exactly $\boldsymbol{S(n;k)}$. Back to our working example $n=4$, we have $t(t+1)(t+2)(t+3) =6\cdot t + 11\cdot t^2 +6 \cdot t^3 +t^4$, which agrees with

$S(n;1)=6,~S(n;2)=11,~S(n;3)=6,~S(n;4)=1\,.$

Nevertheless, we can still collect some few properties of $S(n;k)$. These are summarised as follows:

• Every permutation of $\{1,2,\ldots, n\}$ has only between $1$ and $n$ cycles. So, summing $S(n;k)$ over all possible values of $k=1,2,\ldots,n$, evidently, we recover the total number of permutations which is $n!$:

$\boldsymbol{n!=S(n;1)+S(n;2)+\cdots +S(n;n)}\,.$

• It can be seen that $(1)(2)\ldots (n)$ is the unique permutation with $n$ cycles. This means

$\boldsymbol{S(n;n)=1}\,.$

• If we want to count permutations with a single cycle, then there are $n-1$ ways of choosing which element the first entry of the cycle must be mapped to; once this is done, there are now $n-2$ ways to select the element to which the second entry of the cycle must be assigned to; etc. – the last entry in the cycle is already mapped to the first element of the cycle. So, we obtain

$\boldsymbol{S(n;1)=(n-1)(n-2)\ldots 2 \cdot 1 =(n-1)!}\,.$

• If there is a permutation with $n-1$ cycles, then no two of them can contain more than one element, since there are $n$ elements over all. This means, a permutation with $n-1$ cycles must have exactly $n-2$ cycles with a single entry and one cycle with two entries. This shows that $S(n;n-1)$ is just the number of ways of choosing the two elements that compose the cycle with two entries:

$\boldsymbol{S(n;n-1)=\binom{n}{2}}\,.$

A more general way to compute $S(n;k)$ is to employ the beautiful recursion

$\boldsymbol{S(n;k)=S(n-1;k-1)+(n-1)S(n-1;k)}$

which also has a simple combinatorial interpretation. This is left as an exercise for the reader!

Stirling’s numbers have seen their appearance in many branches of mathematics such as the theory of finite differences. They also have a connection to other famous numbers in combinatorics.

If you’d like to learn more, there is yet another type of Stirling’s numbers known as the Stirling numbers of the second kind, which are related to set partitions.