4 Sorting

How many ways can we sort 5 indistinct balls into 3 buckets?

We can think about this in the following way: Instead of “buckets” we can use dividers. But for 3 buckets we only need 2 dividers:

But then we can think about sorting 5 indistinct balls into 3 buckets as “ordering 7 objects (5 balls and 2 dividers)”. We already know how to calculate this (see Number of permutations of partially non-distinct objects): The number of ways to arrange 5 balls and 2 dividers is:

\[ \frac{7!}{5!2!} = 21 \]

Sorting \(k\) indistinct objects into \(n\) buckets{rule}

The number of ways to sort \(k\) indistinct objects into \(n\) buckets is:

\[ \frac{(k+n-1)!}{k!(n-1)!} = \binom{k+n-1}{k} \]