# cycle index

Anonymous

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

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

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