The twelve fold way

I really struggle to remember the combinatorial rules. Do I need to use choose or do I need to use permute? How do I calculate each of them? Is this a case of stars and bars or is this something else?

One of the things I want to add to my chatbot program is a way to ask which of the many systems should I be using? I did once try to build a javascript tool although I don’t think it ever really made itself into a useful state.

I recently found a paper called “The twelvefold way” which explains all the different ways you put balls in boxes (or urns as is used in the paper).

It really helped me to understand, at least a little better, how to calculate the different permutations of the problem. With this newfound understanding, I once again had a go at producing a program to calculate each, with a simple form-based input.

One of the things that I wanted to extend this to doing was informing me of what the calculation method was. I really like the way google now lends a hand when you ask it unit conversion problems.

The number of n-tuples of k things

The problem of how many ways there are to arrange b labeled balls in u labelled urns is equivalent to the problem of the number of b-tuples of u things.

There are u places for the first ball, u for the second... There are therefore u to the b possibilities.

$u^b$

At least one labelled ball in each of the labelled urns

We first assume that the urns are unlabeled, this gives us the formula from the Stirling numbers of the second kind.

Since the urns can be permuted in u! ways among themselves, the number of possibilities for labelled urns is u! times as many as when the urns are unlabeled. We can therefore simply multiply the Stirling number by the factorial of the number of urns.

$u!S(b,u) = u!\begin{Bmatrix}b\\u \end{Bmatrix}$

The nth falling factor of k

The number of ways to place b labelled balls in u labelled urns is calculated as follows. There are u choices for where to place the first ball, u-1 for the second and so forth.

$\prod_{n=0}^{b-1}u-n$

Unlabeled balls, labelled urns, at least one ball per urn

To calculate the number of ways to put b unlabeled balls into u labelled urns, put one ball in each urn. The problem is now how many ways with any number of the remaining b-u balls in each urn. This is choosing without replacement of u urns for b-u balls.

$\begin{pmatrix}\begin{pmatrix}u\\b-u\end{pmatrix}\end{pmatrix} =\begin{pmatrix}b-1\\u-1\end{pmatrix}=\frac{(b-1)!}{(u-1)!(b-u)!}$

Choosing with replacement

The number of ways to distribute any number of b unlabeled balls into u urns is the same as asking how many ways can you chose k items from a set of size n with replacement. This is because for each ball one can choose which urn to put it in. since an urn can be selected several times this is choosing with replacement. (It is important to think of choosing urns, not balls). Using a double bracket notation for choosing with replacement, and a single bracket for choosing without replacement.

$\begin{pmatrix}n\\k\end{pmatrix}\ The\ number\ of\ ways\ to\ chose\ k\ things\ from\ a\ set\ of\ n\ \bold{without}\ replacement\\\\ \begin{pmatrix}\begin{pmatrix}n\\k\end{pmatrix}\end{pmatrix}\ The\ number\ of\ ways\ to\ chose\ k\ things\ from\ a\ set\ of\ n\ \bold{with}\ replacement\\\\$

It turns out that:

$\begin{pmatrix}\begin{pmatrix}n\\k\end{pmatrix}\end{pmatrix} =\begin{pmatrix}n+k-1\\k\end{pmatrix}$

This is really well explained by the numberphile video on stars and bars and bagels:

Combinations

If there can be no more than one ball in each unlabeled urn the problem becomes which urn will each ball go into. There are u chose b ways to chose b urns out of a total of u urns. This is choosing without replacement. The chose function is denoted below:

$\begin{pmatrix}u\\b\end{pmatrix}=\frac{u!}{b!(u-b)!}$

You can derive this by thinking about how you might place the balls. If we have 3 balls and 4 urns. We have 4 places to put the first ball 3 places to put the second and 2 places to put the first.

In general, we will have u places to put the first ball, u-1 places for the second and so on:

$\prod_{n=0}^{b-1}u-n=\frac{u!}{(u-b)!}$

The order in which we pick the balls doesn't matter though. There are b! ways we can pick the balls. That means we b! times more combinations than we need. We can simply divide out these to get the result.

Labelled balls, unlabeled urns, any number of balls per urn

The number of ways to place b labelled balls into u unlabeled urns, such that there are any number of balls per urn, is related to the number of ways to place labelled balls in unlabeled urns such that there is at least one. Each example where there are n empty urns can be thought of as the problem of placing balls into urns such that there is at least one ball per urn in u-n urns.

To calculate this we simply sum the number of ways to place at least one ball into the urns for every example where some of the urns are empty. This leads to the following formula:

$\sum_{n=1}^uS(b,n)$

Where the function S is the Stirling number of the second kind, as explained below.

Stirling numbers of the second kind

To work out the number of ways to place labelled balls into unlabeled urns such that there is at least one ball per urn is calculated using the Stirling numbers of the second kind. James Stirling was a mathematician who did a lot of the founding work on combinatorics and coined the term the twelvefold way.

The Stirling number of the second kind S(n,k) is the number of ways to partition n objects into k non-empty sets. For example, there are 3 ways to partition 3 things into 2 sets:

The formula for the Stirling numbers is given recursively as follows:

$S(n,k) = \begin{Bmatrix} n\\ k \end{Bmatrix}=k\begin{Bmatrix}n-1\\k \end{Bmatrix}+ \begin{Bmatrix}n-1\\k-1 \end{Bmatrix}\\\\ With\ the\ base\ cases:\\\\ \begin{Bmatrix}n\\n \end{Bmatrix}=1\\\\ \forall (k>n) \bullet \begin{Bmatrix}n\\k \end{Bmatrix} =0\\\\ \forall (n\geq 1)\bullet \begin{Bmatrix}n\\1 \end{Bmatrix} = 1$

The base cases read:

If n and k are the same S(n,k) will be 1
For all cases where k is larger than n S(nk) will be zero
For all cases where n is greater than or equal to 1 and k is 1. S(n,k) will be 1.

Unlabeled and unrestricted

For the case where the number of balls per urn is unrestricted and both the balls and urns are unlabeled, this becomes similar to the partitions problem. The difference here is that because we can leave some of the earns empty. In the case where we leave n urns empty, the problem is the same as having at least one ball in u-n urns.

This leads us to the situation where to calculate how many ways there are, we sum over leaving different numbers of urns empty.

$\sum_{n=1}^{u}p_n(b)$

Where p is the partitions function as defined below.

Partitions

The question of how many ways b unlabeled balls can go into u unlabeled urns, such that there is at least one ball per urn, turns out to be the same question as how many ways can you write n as the sum of k positive integers. Numberphile did a great video on this using lego.

The way to think about this is recursively, and that is how the formula is defined:

$p_k(n)=p_{k-1}(n-1) + p_k(n-k)\\With\ the\ base\ cases:\\p_0(0)=1\\p_k(n)=0\ for\ (k\leq 0\vee \leq0)\wedge \overline{(k=0\wedge n=0 )}$

The second base case reads that the function will be 0 for all k and n if either k or n are less than or equal to zero. This has the exception of if the other base case is met, where both k and n are zero, in that case, the first base case takes precedence and the value of the function is 1.

At most one ball per unlabeled urn

For any situation where the urns are unlabeled and there is the condition that there must be no more than one ball per urn, then depending on the number of balls and urns, it can either be done, or it can't.

If there are more balls than urns, $b>u$ there is no way to place all the balls such that there is no more than one ball per urn.

In the case where the number of balls equals the number of urns, $b=u$ Each ball simply goes in an urn. Since the urns are no labelled, it is irrelevant if the balls are labelled.

In the final case where the number of balls is fewer than the number of urns $b<u$ , since the urns are unlabeled there is only one way to place the balls, just put one per urn, until you run out of balls, leave the other urns empty.

Search This Blog