ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 27 Mar 2018 15:07:33 +0200cycle indexhttps://ask.sagemath.org/question/10661/cycle-index/I know that S4 = SymmetricGroup(4)
P = S4.cycle_index()
will return the cycle index polynomial for S_4. What I want to do is substitute variables into this polynomial for Polya Enumeration problems. So for instance, how do I substitute x+y into the cycles of length 1, x^2+y^2 into the cycles of length 2, etc.Sat, 26 Oct 2013 19:31:51 +0200https://ask.sagemath.org/question/10661/cycle-index/Answer by tmonteil for <p>I know that S4 = SymmetricGroup(4)
P = S4.cycle_index()</p>
<p>will return the cycle index polynomial for S_4. What I want to do is substitute variables into this polynomial for Polya Enumeration problems. So for instance, how do I substitute x+y into the cycles of length 1, x^2+y^2 into the cycles of length 2, etc.</p>
https://ask.sagemath.org/question/10661/cycle-index/?answer=15614#post-id-15614You can extract the contents of P as follows:
sage: list(P)
[([1, 1, 1, 1], 1/24),
([4], 1/4),
([3, 1], 1/3),
([2, 2], 1/8),
([2, 1, 1], 1/4)]
I am not sure i understand which polynomial you want, if you want to associate to a permutation the product of the `(x^j+y^j)` for each cycle of length `j` contained in the permutation, you can do:
sage: var('x y')
(x, y)
sage: sum([(i[1]*prod([(x^j + y^j) for j in i[0]])) for i in P])
1/24*(x + y)^4 + 1/4*x^4 + 1/4*y^4 + 1/4*(x^2 + y^2)*(x + y)^2 + 1/8*(x^2 + y^2)^2 + 1/3*(x^3 + y^3)*(x + y)
Or, if you want genuine polynomials instead of symbolic functions:
sage: R.<x,y> = PolynomialRing(QQ,2)
sage: sum([(i[1]*prod([(x^j + y^j) for j in i[0]])) for i in P])
x^4 + x^3*y + x^2*y^2 + x*y^3 + y^4
sage: Q = CyclicPermutationGroup(6).cycle_index()
sage: sum([(i[1]*prod([(x^j + y^j) for j in i[0]])) for i in Q])
x^6 + x^5*y + 3*x^4*y^2 + 4*x^3*y^3 + 3*x^2*y^4 + x*y^5 + y^6
Sat, 26 Oct 2013 20:33:16 +0200https://ask.sagemath.org/question/10661/cycle-index/?answer=15614#post-id-15614Answer by dan_fulea for <p>I know that S4 = SymmetricGroup(4)
P = S4.cycle_index()</p>
<p>will return the cycle index polynomial for S_4. What I want to do is substitute variables into this polynomial for Polya Enumeration problems. So for instance, how do I substitute x+y into the cycles of length 1, x^2+y^2 into the cycles of length 2, etc.</p>
https://ask.sagemath.org/question/10661/cycle-index/?answer=41792#post-id-41792**Prelude / Digression:**
These days i had to understand the PĆ³lya - de Brujin counting scheme, trying to implement some special counting in sage, i walked through this question.
The **solution**
is simple, if i correctly understand / digest the question, since the symmetric polynomials already come in the right basis:
S4 = SymmetricGroup(4)
P = S4.cycle_index()
# as posted so far
R.<x,y> = PolynomialRing(QQ) # the two variables wanted in the post
P.expand(2)(x,y)
This piece of code gives:
x^4 + x^3*y + x^2*y^2 + x*y^3 + y^4
**Comments:**
(1)
Above, `P` is the symmetric polynomial:
sage: P
1/24*p[1, 1, 1, 1] + 1/4*p[2, 1, 1] + 1/8*p[2, 2] + 1/3*p[3, 1] + 1/4*p[4]
written in the `p` basis.
(2)
One can illustrate this basis as follows:
sage: Sym = SymmetricFunctions(QQ)
sage: p = Sym.powersum()
sage: var('x,y,z,t');
sage: p([1,1]).expand(4)(x,y,z,t).factor()
(t + x + y + z)^2
sage: p([2,1]).expand(4)(x,y,z,t).factor()
(t^2 + x^2 + y^2 + z^2)*(t + x + y + z)
sage: (1/24*p[1, 1, 1, 1] + 1/4*p[2, 1, 1] + 1/8*p[2, 2] + 1/3*p[3, 1] + 1/4*p[4]).expand(2)(x,y)
x^4 + x^3*y + x^2*y^2 + x*y^3 + y^4
sage:
(3)
An application, which shows how to use the cycle index polynomial in combinatorics. We have 8 balls, only the colors differ. The colors are red, blue, green, white, and yellow. There are respectively
$$3,2,1,1,1$$
balls in these colors. How many possibilities exist to distribute them in three labeled recipients, I, II, III, containing respectively $3,3,2$ balls.
The sage solution to this problem is as follows:
P = product( [ SymmetricGroup(k).cycle_index() for k in [3, 2, 1, 1, 1] ] )
R.<y1,y2,y3> = PolynomialRing(QQ)
P.expand(3)(y1, y2, y3).coefficient( y1^3 * y2^3 * y3^2 )
which gives `108`. The explicitly written, human solution goes as follows, and it is not at a glance transparent to translate from this solution to the sage solution. One builds the cycle index polynomials
\begin{align}
P_1 &= x_1\ ,\\\\
P_2 &= \frac 12(x_1^2+x_2)\ ,\\\\
P_3 &= \frac 16(x_1^3+3x_1x_2+2x_3)\ ,\\\\
&\text{and the product}\\\\
P &= P_3\;P_2\;P_1\;P_1\;P_1\ ,\\\\
\end{align}
and then one substitutes for the $x_1, x_2, x_3$
\begin{align}
x_1 = y_1+y_2+y_3\ ,\\\\
x_2 = y_1^2+y_2^2+y_3^2\ ,\\\\
x_3 = y_1^3+y_2^3+y_3^3\ ,\\\\
\end{align}
and in the resulted symmetric polynomial, we isolate the monomial in $y_1^3y_2^3y_3^3$.
The "other code" being:
RX.<x1,x2,x3> = QQ[]
RY.<y1,y2,y3> = QQ[]
P = (x1^3 + 3*x1*x2 + 2*x3)/6 * (x1^2 + x2)/2 * x1^3
P(y1+y2+y3, y1^2+y2^2+y3^2, y1^3+y2^3+y3^3 ).coefficient( y1^3 * y2^3 * y3^2 )
It can be that the post was written with such a situation (or a similar one) in mind. The polynomial `P` comes as a symmetric polynomial and the problem may have been to evaluate it explicitly as in the above example.
(4) The post is rather trying to understand the question, and give a sample for the related world. (A programming language becomes strong, when both documentation and examples cover as much as possible. So let us make sage strong!) Tue, 27 Mar 2018 15:07:33 +0200https://ask.sagemath.org/question/10661/cycle-index/?answer=41792#post-id-41792