Solved

Polya counting theory doubt

Posted on 2008-10-19
6
310 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
Industry Leaders: 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

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

How to Win a Jar of Candy Corn: A Scientific Approach! I love mathematics. If you love mathematics also, you may enjoy this tip on how to use math to win your own jar of candy corn and to impress your friends. As I said, I love math, but I gu…
The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20. The divisors of 12 are 1, 2, 3, 4, 6, 12 The divisors of 20 are 1, 2, 4, 5, 10 20 The highest number among the c…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…
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…

733 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