# Circular permutations with indistinguishable objects

Given n distinct objects, there are $n!$ permutations of the objects and $n!/n$ "circular permutations" of the objects (orientation of the circle matters, but there is no starting point, so $1234$ and $2341$ are the same, but $4321$ is different).

Given $n$ objects of $k$ types (where the objects within each type are indistinguishable), $r_i$ of the $i^{th}$ type, there are

\begin{equation*} \frac{n!}{r_1!r_2!\cdots r_k!} \end{equation*}

permutations. How many circular permutations are there of such a set?

-
BTW, the answer is not $\frac{1}{n}\cdot\frac{n!}{r_1!r_2!\cdots r_k!}$. –  kennytm Jul 23 '10 at 19:31
Could you go into the motivation behind the problem? –  Jonathan Fischoff Jul 23 '10 at 20:37
A trivial observation: For string S, concatenate with itself infinite many times to get a infinite string. Find the period of this infinite string. The period shows how many strings you can generate from string S and considered different permutations. –  Chao Xu Jul 23 '10 at 21:10
Period of $p$ is not feasible unless $p$ is divisible by $\sum_{i=1}^k \frac{r_i}{\gcd(r_1, r_2, r_3....,r_k)}$. –  Chao Xu Jul 23 '10 at 21:23
@Kenny: Why not? Seems perfectly sensible to me. –  Noldorin Jul 23 '10 at 21:26

## 2 Answers

I wrote a series of blog posts which explains how to solve questions like this; the relevant one is here. The generating function you want is

$$\frac{1}{n} \sum_{d | n} (x_1^{n/d} + ... + x_k^{n/d})^d \varphi \left( \frac{n}{d} \right)$$

where the coefficient of $x_1^{r_1} ... x_k^{r_k}$ is the number you want.

-

This problem is best solved with Pólya's enumeration theorem, which follows from Burnside's lemma. See the first section of this Wikipedia article.

-
Okay, I can see how the first section of the Wikipedia article appears to talk about this problem as the necklace problem, but can't quite get a handle on how to use it. How would one apply Pólya's enumeration theorem to necklaces made with, say, 3 red beads and 5 blue beads? –  Isaac Jul 27 '10 at 7:01