Solved

# Polya counting theory doubt

Posted on 2008-10-19
Medium Priority
313 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
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 3
• 3

LVL 84

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 84

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 84

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

Okay. So what exactly is the problem here? How often have we come across situations where we need to know if two strings are 'similar' but not necessarily the same? I have, plenty of times. Until recently, I thought any functionality like that wo…
One of Google's most recent algorithm changes affecting local searches is entitled "The Pigeon Update." This update has dramatically enhanced search inquires for the keyword "Yelp." Google searches with the word "Yelp" included will now yield Yelp a…
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…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
###### Suggested Courses
Course of the Month14 days, 12 hours left to enroll