# Circular Permutations With Identical Objects

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?

-

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

-
Thanks a lot! Is there any way we can prove this combinatorially? – Mental Inside Jan 30 '12 at 14:14
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

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.

-
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