# 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 ith type, there are $\frac{n!}{r_1!r_2!\cdots r_k!}$ 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
show 1 more comment

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.

-