# 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

$$\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.