Solved

Polya counting theory doubt

Posted on 2008-10-19
6
306 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
  • 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
Live: Real-Time Solutions, Start Here

Receive instant 1:1 support from technology experts, using our real-time conversation and whiteboard interface. Your first 5 minutes are always free.

 
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

Live: Real-Time Solutions, Start Here

Receive instant 1:1 support from technology experts, using our real-time conversation and whiteboard interface. Your first 5 minutes are always free.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Locating peaks of a graph in Excel 9 62
Rounding Values 11 58
Permutation and Combination 9 87
Java. Convert method from recursion based to iteration based ( loop based ) 6 89
Complex Numbers are funny things.  Many people have a basic understanding of them, some a more advanced.  The confusion usually arises when that pesky i (or j for Electrical Engineers) appears and understanding the meaning of a square root of a nega…
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…
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.
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…

776 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