Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is there a closed form solution for Circular permutations of N objects of n1 are identical of one type, n2 are identical of another type and so on, such that n1+n2+n3+..... = N?

share|improve this question
add comment

2 Answers 2

This is a straightforward application of Pólya's theorem. The answer is the coefficient of $x_1^{n_1} x_2^{n_2}\dots$ in the cycle index of the cyclic group of order $N$, which is $$\frac{1}{N}\sum_{d | N} \phi(d) p_d^{N/d}.$$ Here $\phi$ is Euler's totient function and $p_d$ is the power sum symmetric function $x_1^d + x_2^d+\cdots$.

share|improve this answer
    
Thanks a lot! Is there any way we can prove this combinatorially? –  Mental Inside Jan 30 '12 at 14:14
1  
What do you mean by combinatorially? Pólya's theorem is a special case of Burnside's lemma, which is proved by counting a set of ordered pairs in two different ways. The only part of the proof that you might call noncombinatorial is that the size of the orbit of a point under a finite group action is the index of the stabilizer of the point. –  Ira Gessel Jan 30 '12 at 20:19
add comment

Hi I suggest warmly the book Combinatorial species and tree-like structures by Bergeron, Labelle and Leroux.

Or the original article by A. Joyal "Une théorie combinatoire des séries formelles." Adv. in Math. 1981

Si tu n'y a pas access je te conseil de jeter un oeil à Introduction to the Theory of Species of Structures disponible sur le web (lien clickable).

Dans le formalisme des espèces, ton problème est décrit par l'espèce des cycles $C$. Chacune des sources que je t'ai donné explique comment traduire cette description en séries génératrices, les preuves sont combinatoires.

Si tu veux un dénombrement étiqueté, $$ \begin{aligned} C(t) &= \log\left(\frac{1}{1-t}\right) = t + \tfrac{1}{2}t^2+\tfrac{1}{3}t^3+... \\\ C(t_1+t_2+t_3+...) &= -\log\left(1-t_1-t_2-t_3-...\right)\\\ \end{aligned} $$ La solution que tu cherche est, $$ -\frac{\partial^{n_1}}{\partial t_1^{n_1}} ... \frac{\partial^{n_k}}{\partial t_1^{n_k}}\log\left(1-t_1-t_2-t_3-...\right) $$ évalué en $t_1 = 0$, ..., $t_k= 0$, ...

Pour le dénombrement non-étiqueté c'est bien comme dit Ira.

share|improve this answer
    
J'aurais du noté $x_k$ à la place de $t_k$ et du coup $C(p_1)=\log(\frac{1}{1−p_1})$ pour être en ligne avec l'autre réponse. –  Samuel Vidal Jan 30 '12 at 21:18
add comment

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.