25
$\begingroup$

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?

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

3 Answers 3

Reset to default
18
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
1
  • 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
    Commented Jul 27, 2010 at 7:01
0
$\begingroup$

A closed-form solution to this problem is

$$\frac{1}{n}\,\sum_{d\mid\gcd(r_1,r_2,\ldots,r_k)}\,\phi(d)\,\binom{n/d}{r_1/d,r_2/d,\ldots,r_k/d}$$

where $\phi(d)$ is the Euler's totient function.

More details and examples are provided here

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .