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?

  • 1
    $\begingroup$ BTW, the answer is not $\frac{1}{n}\cdot\frac{n!}{r_1!r_2!\cdots r_k!}$. $\endgroup$
    – kennytm
    Jul 23 '10 at 19:31
  • $\begingroup$ Could you go into the motivation behind the problem? $\endgroup$ Jul 23 '10 at 20:37
  • $\begingroup$ 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. $\endgroup$
    – Chao Xu
    Jul 23 '10 at 21:10
  • $\begingroup$ 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)}$. $\endgroup$
    – Chao Xu
    Jul 23 '10 at 21:23
  • $\begingroup$ @Kenny: Why not? Seems perfectly sensible to me. $\endgroup$
    – Noldorin
    Jul 23 '10 at 21:26

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.

  • 1
    $\begingroup$ 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? $\endgroup$
    – Isaac
    Jul 27 '10 at 7:01

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.