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?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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$.
-
$\begingroup$ Thanks a lot! Is there any way we can prove this combinatorially? $\endgroup$ Commented Jan 30, 2012 at 14:14
-
1$\begingroup$ 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. $\endgroup$ Commented Jan 30, 2012 at 20:19
$\begingroup$
$\endgroup$
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.
-
$\begingroup$ 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. $\endgroup$ Commented Jan 30, 2012 at 21:18