Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
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? –  Isaac Jul 27 '10 at 7:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.