Circular Permutations With Identical Objects - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T20:59:45Z http://mathoverflow.net/feeds/question/86709 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/86709/circular-permutations-with-identical-objects Circular Permutations With Identical Objects Mental Inside 2012-01-26T10:27:09Z 2012-01-30T21:13:56Z <p>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?</p> http://mathoverflow.net/questions/86709/circular-permutations-with-identical-objects/86724#86724 Answer by Ira Gessel for Circular Permutations With Identical Objects Ira Gessel 2012-01-26T14:32:29Z 2012-01-26T14:32:29Z <p>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$.</p> http://mathoverflow.net/questions/86709/circular-permutations-with-identical-objects/87069#87069 Answer by Samuel Vidal for Circular Permutations With Identical Objects Samuel Vidal 2012-01-30T21:13:56Z 2012-01-30T21:13:56Z <p>Hi I suggest warmly the book <a href="http://books.google.fr/books?hl=fr&amp;lr=&amp;id=83odtWY4eogC&amp;oi=fnd&amp;pg=PR5&amp;dq=combinatorial+species+and+tree-like+structures&amp;ots=m-87VMAq30&amp;sig=ATCbMxkTlzZ0dleFKfBayefCXK8#v=onepage&amp;q=combinatorial%20species%20and%20tree-like%20structures&amp;f=false" rel="nofollow">Combinatorial species and tree-like structures</a> by Bergeron, Labelle and Leroux.</p> <p>Or the original article by A. Joyal "Une théorie combinatoire des séries formelles." Adv. in Math. 1981</p> <p>Si tu n'y a pas access je te conseil de jeter un oeil à <a href="http://bergeron.math.uqam.ca/Site/bergeron_anglais_files/livre_combinatoire.pdf" rel="nofollow">Introduction to the Theory of Species of Structures</a> disponible sur le web (lien clickable).</p> <p>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.</p> <p>Si tu veux un dénombrement étiqueté, \begin{aligned} C(t) &amp;= \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+...) &amp;= -\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$, ...</p> <p>Pour le dénombrement non-étiqueté c'est bien comme dit Ira.</p>