permutation

This topic has expert replies
Senior | Next Rank: 100 Posts
Posts: 34
Joined: Thu Jul 30, 2009 6:14 pm
Thanked: 3 times

permutation

by kauldheeraj » Mon Aug 31, 2009 11:18 am
Seven men and seven women have to sit around a circular table so that no 2 women are together. In how many different ways can this be done?

Master | Next Rank: 500 Posts
Posts: 379
Joined: Wed Jun 03, 2009 3:05 am
Thanked: 19 times
Followed by:1 members
GMAT Score:690

by sreak1089 » Mon Aug 31, 2009 11:25 am
Is it 720? OA please?

Newbie | Next Rank: 10 Posts
Posts: 5
Joined: Mon Aug 31, 2009 10:51 pm

by gmat550 » Mon Aug 31, 2009 11:12 pm
Arranging 7 men around a circular table = 6! ways

There would be 7 spots in between any two men in the above arrangments and the 7 women can sit in any of those 7 places in 7! ways (note: this is not a circular arrangement)

So, the total ways = 6!*7! = 720 * 5,040 = 3,628,800 !

Senior | Next Rank: 100 Posts
Posts: 34
Joined: Thu Jul 30, 2009 6:14 pm
Thanked: 3 times

by kauldheeraj » Tue Sep 01, 2009 8:08 am
Why is arrangement of 7 men around the table = 6! and not 7!?
A bit confusing these permutations are for me.
Please clarify.

Junior | Next Rank: 30 Posts
Posts: 15
Joined: Sun Aug 23, 2009 6:58 am
Thanked: 1 times
GMAT Score:770

by gmatcoach » Tue Sep 01, 2009 8:43 am
I agree with gmat550's solution. I would solve it with a little more elaborately:

first consider in how many ways 3 people can be arranged linearly:

ABC
BCA
CAB
BAC
CBA
ACB

As seen above it is 3! = 6. So in general you can arrange n people linearly in n! ways.

Now consider in the ways in which 3 people can be arrange circularly around a table. The attached picture shows 2 ways that are equivalent to each other: A-B-C is equivalent to B-C-A.

So only valid seating arrangements for 3 people are:
ABC (equivalent to BCA, CAB)
BAC (equivalent to CBA, ACB)

So only 2 ways are possible.

Think of equibvalent positions the following way: Equivalent positions are those where the seating positions (on right and left of any given person) is the same regardless of the actual chair the person in seated in.

For n people seated around a table, every arrangement will have n-1 equivalent ways of arrangement. So n!/n = (n-1)! ways to seat n people circularly

Now in the given problem, there are 14 people - men and women must alternate so that no 2 women are seated next to each other.

You can select the 1st man-woman pair in 7x7 ways.
2nd man-woman pair in 6x6 ways
3rd man-woman pair in 5x5 ways
4th man-woman pair in 4x4 ways
5th man-woman pair in 3x3 ways
6th man-woman pair in 2x2 ways
7th man-woman pair in 1x1 ways

Also the man/woman couple can be arranged in 2 ways (man-woman) or (woman-man).

So the number of ways of arranging the 14 people linearly (no women are together) is W = 2x(7x7x6x6x5x5x3x3x2x2x1x1) = 2x(7!)^2

Now when you arrange them in a circle, there will be 13 equivalent positions for every arrangement. So divide W by 14 ==> answer = 2x(7!)^2/14 = 7!6!
Attachments
table.jpg

Junior | Next Rank: 30 Posts
Posts: 16
Joined: Sat Sep 05, 2009 8:58 am
Location: London
Thanked: 6 times
GMAT Score:770

by Michael Birdsall » Sun Sep 06, 2009 3:36 am
Good question kauldheeraj.

I think this can be explained in two ways:

First each position has to be different only if an arrangement is considered the same when people are sitting in the same position relative to each other.

For example, Suppose the 7 people sat in the arrangement

1 - ABCDEFG

This would be the same as the arrangements

2 - BCDEFGA
3 - CDEFGAB
4 - DEFGABC
5 - EFGABCD
6 - FGABCDE
7 - GABCDEF

Since 7! would include all the arrangements from above, which are all the same, 7! should be divided by the number of the arrangements that are same. So the number of arrangements of 7 people around a round table is equal to 7!/7.

This approach goes nicely with the formula for the arrangements of n objects around a round table the formula is:

(n-1)!

Another way to justify 6! over 7!,and my preferred method, is to imagine yourself as someone coming to a dinner party that will be attended by 7 people. It comes time to sit down at a round table. How many choices of places to sit does each person have?

It seems as though the first person to sit down would have 7 choices of places to sit, but since positions are defined by where someone sits relative to another person, the first person who sits down has no choice in who he or she sits next to, because none of the position have been defined yet.

Once that first person sits down, however, all the other guests can choose their position relative to the position the first person's position. So the second person to sit down will have 6 choices of places. The third person to sit down will have 5 choices of places. The fourth person will have 4 choices of places...

What you end up with is the arrangements of the 6 remaining guests:

6X5X4X3X2X1=720.

I like this explanation because it seems to go well with the experience of attending a dinner party or being a kid at a school cafeteria. When a group of people attempt to sit down at a table it always a bit confusing to figure out where everyone should sit relative to each other. However, once one person just sits down it is easier for everyone else to take a decision on where to sit.

I hope this helps.

Master | Next Rank: 500 Posts
Posts: 109
Joined: Sun May 10, 2009 7:53 am

by sanjib » Sun Sep 06, 2009 1:00 pm
Excellent application.
However if the question is like:
one circular table of consisting 20 chairs where 7 Actors to be seated with 7 actresses in suh a way that none of the actresses would sit together and all the 14 people should sit side by side and empty chairs are only allowed between two end seated chairs by actor/actresses.
Last edited by sanjib on Tue Sep 08, 2009 2:35 am, edited 1 time in total.

Junior | Next Rank: 30 Posts
Posts: 16
Joined: Sat Sep 05, 2009 8:58 am
Location: London
Thanked: 6 times
GMAT Score:770

by Michael Birdsall » Sun Sep 06, 2009 11:59 pm
one circular table of consisting 10 chairs where 7 Actors to be seated with 7 actresses in suh a way that none of the actresses would sit together and all the 14 people should sit side by side
I am afraid I don't understand your question.

There are only ten chairs and 14 people.

Senior | Next Rank: 100 Posts
Posts: 34
Joined: Thu Jul 30, 2009 6:14 pm
Thanked: 3 times

by kauldheeraj » Tue Sep 08, 2009 5:25 pm
Thanks for your response, and why would the women sit in a combination of 7! since they also are sitting in a circular seating arrangement?
Attachments
Probability_and_Combinations.doc
Few solved probability questions.
(99.5 KiB) Downloaded 129 times

Junior | Next Rank: 30 Posts
Posts: 16
Joined: Sat Sep 05, 2009 8:58 am
Location: London
Thanked: 6 times
GMAT Score:770

by Michael Birdsall » Wed Sep 09, 2009 12:03 am
Another good question.

In the explanations above, it has been pointed out that there are 7 places for for men to sit and 7 places for women to sit. So if you think that once one woman sits down all positions for women can be defined relative to her position, and once one man sits down all the positions for men can be defined relative to his position. You would naturally conclude that the solution must be (7-1)! X (7-1)!.

However, the first person who sits down defines all places relative to his or her position. So only one person needs to sit down and everyone else can choose their seats based on where that one person is sitting. So we end up with the expression (7-1)!X(7!).

Again, what is nice about this is that we can think of the common experience of a dinner party. Once anyone sits down, everyone else, will decide where to sit relative to that person, regardless of his or her GMAT.

In the question we do have to ensure that the arrangements are male-female-male-female...
To ensure that we consider this restriction, we don't need to do anything more than divide the group of 14 into 2 groups consisting of 7 men and 7 women. In other words, we have already made a consideration for the male-female pattern.

I hope this explanation helps.

Junior | Next Rank: 30 Posts
Posts: 16
Joined: Sat Sep 05, 2009 8:58 am
Location: London
Thanked: 6 times
GMAT Score:770

by Michael Birdsall » Wed Sep 09, 2009 12:03 am
Another good question.

In the explanations above, it has been pointed out that there are 7 places for for men to sit and 7 places for women to sit. So if you think that once one woman sits down all positions for women can be defined relative to her position, and once one man sits down all the positions for men can be defined relative to his position. You would naturally conclude that the solution must be (7-1)! X (7-1)!.

However, the first person who sits down defines all places relative to his or her position. So only one person needs to sit down and everyone else can choose their seats based on where that one person is sitting. So we end up with the expression (7-1)!X(7!).

Again, what is nice about this is that we can think of the common experience of a dinner party. Once anyone sits down, everyone else, will decide where to sit relative to that person, regardless of his or her GMAT.

In the question we do have to ensure that the arrangements are male-female-male-female...
To ensure that we consider this restriction, we don't need to do anything more than divide the group of 14 into 2 groups consisting of 7 men and 7 women. In other words, we have already made a consideration for the male-female pattern.

I hope this explanation helps.

Senior | Next Rank: 100 Posts
Posts: 34
Joined: Thu Jul 30, 2009 6:14 pm
Thanked: 3 times

by kauldheeraj » Wed Sep 09, 2009 8:00 am
Thanks a lot again.
A pinning question now here again:
I am just pondering what type of questions would encounter me in the exam on permutations/combinations/probability?
Will they be tought ones or fair enough and solvable with some decent practice on the topic?
I have been doing a lot of work on Probability for quite some time now and am feeling saturated.
Is there a trend of the probability or perm/comb questions that we should expect to see in the exam, or is it absolutely random?
Help required desperately.

Senior | Next Rank: 100 Posts
Posts: 60
Joined: Thu Sep 24, 2009 2:38 pm
Location: NYC
Thanked: 33 times
Followed by:9 members
GMAT Score:710

Re: permutation

by benjiboo » Thu Sep 24, 2009 3:19 pm
kauldheeraj wrote:Seven men and seven women have to sit around a circular table so that no 2 women are together. In how many different ways can this be done?
What is not clear about this question is if the position of the person at the table matters in relation to to which seat they chose and not who they are next to. For example, if each chair had a different letter on it, A through N for the 14 seats, would an arrangement of people with Johnny starting on seat A, be considered the same as the same arrangement with Johnny sitting start on seat B.

Is this not true?