Circular Permutations With Identical Objects - MathOverflow

Circular Permutations With Identical Objects

2012-01-26T10:27:09Z

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?

Answer by Ira Gessel for Circular Permutations With Identical Objects

2012-01-26T14:32:29Z

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

Answer by Samuel Vidal for Circular Permutations With Identical Objects

2012-01-30T21:13:56Z

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.