MATHS BITE: Stars and Bars

A common problem in combinatorics is when we are asked to count the number of ways to group identical objects, such as placing indistinguishable balls into labelled urns. Popularised by William Feller in his book on probability, the Stars and Bars methods aims to solve such problems.

Theorem

The number of ways to put n indistinguishable balls into k labelled urns is

Related image

Proof using Stars and Bars:

Represent n balls by n adjacent stars and consider inserting k – 1 bars between the starts to separate them into k groups.

For example, for n = 12 and k = 5 the following is a possible arrangement:

**|****||***|***

Here, urns 1, 2, 3, 4 and 5 are of size 2, 4, 0, 3 and 3 respectively.

There are a total of n + k – 1 positions, of which n are stars and k – 1  are bars. So, the number of ways to place n indistinguishable balls into k labeled urns in the same as the number of ways of choosing n positions (or k – 1 positions) amount n + k – 1 spaces, with all the remaining positions taken as bars (stars), i.e.

Related image

ways.

M x