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?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
1
|
|
|
|
|
5
|
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$. |
||||||||
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
1
|
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. |
|||
|
