Solved

Polya counting theory doubt

Posted on 2008-10-19
6
311 Views
Last Modified: 2012-08-14
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?
0
Comment
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
  • Learn & ask questions
  • 3
  • 3
6 Comments
 
LVL 84

Expert Comment

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

Author Comment

by:dtivmk
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

by:
ozo earned 500 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
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 1

Author Comment

by:dtivmk
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

by:ozo
ozo earned 500 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

by:dtivmk
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

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Introduction On a scale of 1 to 10, how would you rate our Product? Many of us have answered that question time and time again. But only a few of us have had the pleasure of receiving a stack of the filled out surveys and being asked to do somethi…
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 …
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…

688 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question