Solved

# Polya counting theory doubt

Posted on 2008-10-19

saw a solution for the following problem in a book :

Problem :

Suppose there are 6 chairs around a circular table.

3 men and 3 women need to be seated around it.

Assuming that two sittings are equivalent when one

can find the other by means of a clockwise rotation

through 60k degrees 0<=K<=5,

how many different sittings are possible?

Solution :

There are 6 permutations possible : (set of vertices = {1,2,3,4,5,6})

P1 = (1) (2) (3) (4) (5) (6)

P2 = (1 2 3 4 5 6 )

P3 = (1 3 5 ) (2 4 6)

P4 = (1 4) (2 5) (3 6)

P5 = (1 5 3) (2 6 4)

P6 = (1 6 5 4 3 2)

So the cycle index is :

(1/6)*(x1^6 + x6 + x3^2 + x2^3 + x3^2 + x6)

Since number of men and women are equal, weight of both the colors is 1,

i.e. W(Men) = W(Women) = 1,

so putting x1 = 1+1, x2 = 1^2+1^2, x3 = 1^3 + 1^3 etc.

answer is

(1/6)*(2^6 + 2^3 + 2*2^2 + 2*2) = (1/6)*(64+8+2*4 + 2*2)

= (1/6)*(64+16+4) = (1/6)*84 = 14

--------------------------------------------------------------------------------------

Now, here the weights assigned for men and women are 1, since number of men = number of women = 3.

What if number of men = 4, number of women = 2,

what would be the weights then?

What is the procedure to find out the weights in general?