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

edit retag close merge delete

Sort by » oldest newest most voted

You 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

more

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


(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!)

more