I know that the number of ways to arrange $n$ distinct objects in a circle in $(n-1)!$ from Circular Permutation.
But suppose we have $n_1$ identical objects of Type $1$, $n_2$ identical objects of Type $2$ and so on upto $n_k$ identical objects of Type $k$, with the total number of objects equal to $n$. How many ways are there to arrange these objects in a circle?
I tried selecting the first object in $1$ (say of Type $1$) way (since it is a circle) and then considering the remaining objects to be permuted in a line, so we get the total number of ways as: $$\dfrac{(n-1)!}{(n_1 – 1)! n_2 ! \cdots n_k !} + \dfrac{(n-1)!}{n_1 ! (n_2 – 1)! \cdots n_k !} + \cdots + \dfrac{(n-1)!}{n_1! n_2 ! \cdots (n_k-1) !}$$
But this is clearly an overcount, since if we take the problem of arranging $9$ blue and $3$ red beads in a circle, the answer we get from the above is $\dfrac{11!}{8! \cdot 3!} + \dfrac{11!}{9! \cdot 2!} = 220$, while the correct answer (from here) is $19$.
Can anyone solve the general case?
Thanks in advance.
Best Answer
Answer: $$ \text{# arrangements } = \frac1{n}\sum_{d|\gcd(n_1,\dots,n_k)}\varphi(d)\binom{n/d}{n_1/d,\dots,n_k/d} $$
There are (at least) two general methods for solving problems of this type: Burnside's Lemma (which was mentioned in the solution by N.F. Taussig in the question you linked to) and the Polya Enumeration Theorem. I will illustrate the use of the Polya method in the case of $9$ blue balls and $3$ red balls arranged around a circle. We want to count the distinct arrangements.
The group of symmetries in the case of $12$ objects arranged around a circle is the cyclic group of order $12$, $C_{12}$. In general, for a cyclic group of order $n$, the cycle index is $$Z = \frac{1}{n} \sum_{d|n} \phi(d) x_d^{n/d}$$ where the summation takes place over all divisors $d$ of $n$ and $\phi(d)$ is the Euler Phi function. For the case of $n=12$, we have $$Z = \frac{1}{12} (x_1^{12} + x_2^6 + 2 x_3^4 + 2x_4^3 +2 x_6^2 +4x_{12})$$ Using the variables $b$ and $r$ to denote the colors blue and red, we have after "substitution" (replacing $x_i$ with $b^i+r^i$) $$Z = \frac{1}{12}((b + r)^{12} + (b^2 + r^2)^6 + 2 (b^3 + r^3)^4 + 2 (b^4 + r^4)^3 + 2 (b^6 + r^6)^2 + 4 (b^{12} + r^{12}))$$ which after expansion becomes $$Z = b^{12}+b^{11} r+6 b^{10} r^2+19 b^9 r^3+43 b^8 r^4+66 b^7 r^5+80 b^6 r^6+66 b^5 r^7+43 b^4 r^8+19 b^3 r^9+6 b^2 r^{10}+b r^{11}+r^{12}$$ The coefficient of $b^i r^j$ in this polynomial is the number of distinct arrangements using $i$ blue balls and $j$ red balls. Since the coefficient of $b^9 r^3$ is $19$, the answer to the original problem is $19$. But notice that we have simultaneously solved the problem for all possible combinations of $12$ balls in two colors; for example, the number of arrangements with $7$ blue balls and $5$ red balls is $66$.
If you apply this in general when the distribution type is given by the vector $(n_1,\dots,n_k)$, the result works out to be the answer quoted at the top.
One source of examples of the use of Polya's Enumeration Theorem is Schaum's Theory and Problems of Combinatorics by V.K. Balakrishnan.