Ordering balls of different colors

Question

Imagine I have balls of different colors. Given all the balls (and their color) I want to know all the possible ways to order them.

Example: I have three balls, two of them are green and one is yellow. In this case I have three different orderings: (G, G, Y), (G, Y, G) and (Y, G, G).

My first question is, given the input $b_1,b_2,...,b_N$ where $b_i$ is the number of balls painted with the $i$th color, is there any mathematical expression to get the number of possible orderings?

Note that $N$ is the amount of colors and $B = \sum_{i=1}^{N}b_{i}$ is the amount of balls. Moreover, as shown in the example, balls of the same color are indistinguishable.

Finally, what would be an algorithm to enumerate all the possible orderings?

Answer 1

Yes, there is a way to find the number of possible orderings. If $S$ is the set containing all possible orderings, then $$n(S) = \frac{B!}{\prod_{i=1}^N b_i!} = \frac{B!}{b_1!b_2!...b_N!}$$

To find the elements of set $S$, a possible algorithm would be:

• List all the balls with their colours sequentially eg GGGBBB
• Pick the first element and swap it with the first element of a different colour eg BGGGBB. Doing this multiple times with the first element gives us the possibilities BGGBGB and BGGBBG as well
• Repeat the same logic with all the elements but do not swap them with any character that is behind them as these cases are already covered.