# Number of ways of coloring $n$ boxes

I want to color $n$ ordered boxes, the coloring is specified by $(a_1,\cdots,a_d)$ meaning that one color is used $a_1$ times and another different color is used $a_2$ times and so on... with the property that $a_1+\cdots + a_d=n$. I want to count the number of ways of coloring the $n$ boxes with $(a_1,\cdots,a_d)$.

For example $n=4$.

• There are ${4 \choose 2}$ ways to color the $4$ boxes with $(1, 1, 2)$ which are: aabc, abac,abca,baac, baca,bcaa.
• There are $\dfrac{4 \choose 2}{2}$ ways to color the $4$ boxes with $(2,2)$ which are : aabb, abab, abba.

Notice that we divided by two to take account of the repetitions because aabb and bbaa are the same, also abab=baba and abba=baab. That is, the colors are not important; what is important is what boxes have the same color and what boxes have different colors.

• There is something missing in your problem. Is the number d specified? – Kristjan Kica Jun 21 '17 at 13:38
• and what does the 2 stand for? – Kristjan Kica Jun 21 '17 at 13:41
• The number $n$ and the partition $(a_1,\cdots,a_d)$ are given. – palio Jun 21 '17 at 13:41

If you didn't count swapping two colours to give you the same colouring, the answer would be $\frac{n!}{a_1!a_2!\cdots a_d!}$. This is if you take $a_1$ different boxes of the first colour, $a_2$ different boxes of the second colour, and so on, there are $n!$ ways to order them, but these don't correspond to different colourings; in fact each colouring can come from $a_1!a_2!\cdots a_d!$ different orders.

If you also want to have swapping colours treated as equivalent, then each equivalence class of colourings contains $b_1!b_2!\cdots b_n!$ of the colourings above, where $b_i:=|\{j:a_j=i\}|$. This is because the $b_2$ colours which appear twice can be rearranged in $b_2!$ ways to give equivalent colourings, etc.

So the answer is $$\frac{n!}{(a_1!a_2!\cdots a_d!)(b_1!b_2!\cdots b_n!)},$$ with $b_i$ defined as above. (Many of these $b_i$ will be $0$; recall that $0!=1$ so you can just ignore these.)

• Just out of curiosity, does there exist a simple expression solely in $a_k$? – orlp Jun 21 '17 at 14:06
• @orlp you can substitute the expressions of $b_i$ in the $a_j$. Then you have an expression purely in $a_j$. More simple is simply not possible. – drhab Jun 21 '17 at 14:08

Write out the colours in order as $\omega = 11\cdots122\cdots2\cdots dd\cdots d$ where you have $a_i$ occurrences of $i$. Let $S_n$ act on $\omega$ by shuffling. We will declare two strings equal if there is a permutation of $1,\dots,d$ that sends one to the other. For instance, $1122 \equiv 2211$ using the permutation $1 \leftrightarrow 2$.

The stabiliser subgroup of $\omega$ is isomorphic to $S_{a_1} \times \dots \times S_{a_d} \times S_{r_1} \dots \times S_{r_t}$ where $S_{a_i}$ acts by permuting the $i$'s only and each $S_{r_j}$ acts by permuting a collection of $r_j$ letters $i$ which have the same value $a_i$. For instance in the partition $(1,2,2)$ you have a copy of $S_2$ that acts by permutting the letters $2$ and $3$.

Thus the orbit of $\omega$ has size

$$\frac{n!}{a_1! \cdots a_d! \cdot r_1! \cdots r_t!}$$

or equivalently if $(a_1,\dots,a_d)$ has $m_i$ parts equal to $i$ then the orbit has size

$$n! \left( \prod_{i = 1}^{\infty} (i!)^{m_i}m_i! \right)^{-1}.$$

For example, with $(1,1,2,4,7,7,7)$ you have $m_1 = 2$, $m_2 = 1$, $m_3 = 0$, $m_4 = 1$, $m_5 = m_6 = 0$ and $m_7 = 3$ with $m_k = 0$ for $k \ge 8$. This gives you

$$\frac{29!}{1!^2\cdot 2!^1\cdot 4!^1\cdot 7!^3\cdot 2!\cdot1!\cdot1!\cdot3! }$$ where I've left out the terms where $m_i = 0$.