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.

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

  • $\begingroup$ Just out of curiosity, does there exist a simple expression solely in $a_k$? $\endgroup$ – orlp Jun 21 '17 at 14:06
  • $\begingroup$ @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. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.