17
$\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?

  • 1
    BTW, the answer is *not* [$\frac{1}{n}\cdot\frac{n!}{r_1!r_2!\cdots r_k!}$](http://latex.codecogs.com/gif.latex?%5Cfrac%7B1%7D%7Bn%7D%5Ccdot%5Cfrac%7Bn%21%7D%7Br_1%21r_2%21%5Ccdots%20r_k%21%7D).2010-07-23
  • 0
    Could you go into the motivation behind the problem?2010-07-23
  • 0
    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.2010-07-23
  • 0
    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)}$.2010-07-23
  • 0
    @Kenny: Why not? Seems perfectly sensible to me.2010-07-23
  • 0
    @Noldorin: Counter example, two 1's.2010-07-23

2 Answers 2

15

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.

4

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
    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?2010-07-27