Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
Solved

# Polya counting theory doubt

Posted on 2008-10-19
Medium Priority
319 Views
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.
(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?
0
Question by:dtivmk
• 3
• 3

LVL 85

Expert Comment

ID: 22755303
if number of men = 4, number  of women = 2, the possible permutations would change
0

LVL 1

Author Comment

ID: 22755321
Yes, they will.
So, how will the solution above change? that's the question...
Even in the above solution, premutations have been computed
without taking into account number of men/women...
They were accounted for only while calculating weights..
0

LVL 85

Accepted Solution

ozo earned 2000 total points
ID: 22755459

(1/6)*((x+y)^6 + (x^6+y^6) + (x^3+y^3)^2 + (x^2+y^2)^3 + (x^3+y^3)^2 + (x^6+y^6)
=
(
(y^6+6xy^5+15x^2y^4+20x^3y^3+15x^4y^2+6x^5y+x^6)
+
2(x^6+y^6)
+
2(x^6+2x^3y^3+y^6)
+
x^6+3x^4y^2+3x^2y^4+y^6
)
/6
=
(1y^6 + 1xy^5 + 3x^2y^4 + 4x^3y^3 + 3x^4y^2 + 1x^5y + 1x^6)
so
1 way to do it with 6 women
1 way to do it with 1 man 5 women
3 ways to do it with 2 men and 4 women
4 ways to do it with 3 men and 3 women
3 ways to do it with 4 men and 2 women
1 way to do it with 5 men 1 woman
1 way to do it with 6 men
total of 14

0

LVL 1

Author Comment

ID: 22755524
Ok,
so here it's assumed that the all men are indistinguishable from each other.
what if they are not?
can polya's theory deal with that scenario?
0

LVL 85

Assisted Solution

ozo earned 2000 total points
ID: 22755667
for 6 distinct people
(1/6)*((u+v+w+x+y+z)^6 + 2*(u^6+v^6+w^6+x^6+y^6+z^5) + 2*(u^3+v^3+w^3+x^3+y^3+z^3)^2 + (u^2+v^2+w^3+x^2+y^2+z^2)^3 )
where you have 1 of each person
so we are only intersted in the u*v*w*x*y*z term =
(1/6)*(... + 720*u*v*w*x*y*z + ... )
= 120 = 5! as expected
0

LVL 1

Author Comment

ID: 22765217
Just one question.
What is the concept of weights then?
Here weight of every color is 1.
What else could it possibly be?
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you ever thought of installing a power system that generates solar electricity to power your house? Some may say yes, while others may tell me no. But have you noticed that people around you are now considering installing such systems in their …
We take a look at the fast-evolving changes in Search Engine Optimization rules and algorithms by Google.
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
###### Suggested Courses
Course of the Month11 days, 10 hours left to enroll