6
$\begingroup$

A party of $10$ consists of $2$ Americans, $2$ British men, $2$ Chinese & $4$ men of other nationalities (all different). Find the number of ways in which they can stand in a row so that no two men of the same nationality are next to one another. Find also the number of ways in which they can sit at a round table.
Here for the first one I try to use the gap method. So arrange $5$ to create gaps to accommodate all but we have only four of different nationalities. So a different method should be used.
All permutations - permutations of people of same country being together
But this has cases as only one pair together, two pairs together and three pairs together. Which overlap. How to handle ?

$\endgroup$
  • $\begingroup$ Condition for sitting at the round table is same as for standing in a row? $\endgroup$ – Gummy bears Jan 2 '16 at 15:30
  • $\begingroup$ @Gummybears bears no, one is a circular permutation $\endgroup$ – theREALyumdub Jan 2 '16 at 15:31
  • $\begingroup$ @theREALyumdub So we don't have the condition that no men of same nationalities can be sitting together - for the round table that is? $\endgroup$ – Gummy bears Jan 2 '16 at 15:32
  • $\begingroup$ @Gummybears maybe you are seeing something I am not, but you can rotate men around a round table and have the same permutation... or no? $\endgroup$ – theREALyumdub Jan 2 '16 at 15:33
  • $\begingroup$ @Gummybears in a round setting, men at the ends must be different nationalities $\endgroup$ – theREALyumdub Jan 2 '16 at 15:34
8
$\begingroup$

In a row: There are $10!$ ways to arrange the people. We now count the bad arrangements, in which two A's are next to each other, or two B's, or two C's.

To do the counting, we use Inclusion/Exclusion. How many arrangements have the two A's together? Put them in a bag. We now have $8$ people and $1$ bag. These can be arranged in $9!$ ways. Then when we let the A's out of the bag, they can arrange themselves in $2$ ways, for a total of $2\cdot 9!$.

Do the same for the B's, the C's, and add up. We get $3\cdot 2\cdot 9!$.

However, we have double-counted the bad arrangements in which, for example, the A's and the B's are together. The same bag argument shows there are $2^2\cdot 8!$ such arrangements, for a total of $3\cdot 2^2\cdot 8!$.

Thus our next estimate for the number of bads is $3\cdot 2\cdot 9!-3\cdot 2^2\cdot 8!$.

However, we have subtracted one too many times the arrangements in which the A's are together, and the B's, and the C's. The now familiar technique shows there are $2^3\cdot 7!$ of these. So add back $2^3\cdot 7!$.

We end up with $7!(6\cdot 9\cdot 8-12\cdot 8+8)$, which is $8!\cdot 43$.

This is the number of bad arrangements. The number of good arrangements is $10!-8!\cdot 43$, which is $8!\cdot 47$.

Circular table: We use the convention that two orders are to be considered the same if they differ by a rotation. Assume that one of the "others" is a Canadian. He/she is probably too polite to complain, so one can put the Canadian in the worst chair.

The remaining chairs can now be thought of as a line. We have $9$ people, including $3$ "others" to put in a line, with the condition that the two A's, two B's, and two C's are separated. Same Inclusion/Exclusion technique.

$\endgroup$
2
$\begingroup$

Seating in a row

I shall name the people of $3$ particular nationalities $A_1\;\; A_2\;\; B_1\;\; B_2\;\; C_1\;\; C_2$

First permute $4$ men of "other" nationalities + $A_1,\;B_1,\;C_1\;$ in $7!$ ways.
In the diagram below, $A_1$ is shown in black among the $7$

$\uparrow\huge\circ$$\uparrow\huge\circ$$\uparrow\huge\circ$$\uparrow\huge\circ$$\huge\bullet$$\huge\circ$$\uparrow\huge\circ$$\uparrow$

Wherever $A_1$ may be placed, $A_2$ has only $7-1 = 6 $ places where it can be put.

Similarly, $B_2$ will have $8-1 = 7$ places where it can be put, and $C_3$, $8$ places.

Thus number of arrangements $= 7!\times(6\cdot7\cdot8) = 42*8!$

Addendum

This misses a few possible placements by ignoring ones where a "duplicate" is placed together with the "original." On revisiting the question (after many days !) I have developed a method to work out a way to circumvent this lacuna


Suppose 2 objects are to be kept apart in a permutation, there are $2$ well known methods

  • the "gap method", where these $2$ objects are placed in the gaps (incl. ends)

  • the "subtraction method" [ total permutations - those with the $2$ objects together ]

By successively applying these, we can find the number of ways both $A's$ and $B's$ are apart, and then place the $C's$, as seperators, if so needed.

  • $A's$ apart or together, $B's$ apart $= 6!\times 7\cdot 6 = 6!\times 42$

  • $(a) A's$ together, $B's$ apart $= (2\times 5!) \times 6\cdot 5 = 6!\times 10$

  • $(b)$ thus both $A's$ and $B's$ apart = $6!(42-10) = 6!\times 32$

  • $(c)$ also, both $A's$ and $B's$ together = $6!\times 4$

Now placing the $C's$ appropriately, remembering that the two are distinct, and that there will be two versions of case $(a)$, we get

$6![ (2\times 10) \times (2\cdot 8) + (32\times8\cdot9) + (2\cdot4)] = 8!\times 47$

$\endgroup$
  • $\begingroup$ Could be more succinct as $ 4* 9! $ $\endgroup$ – theREALyumdub Jan 2 '16 at 15:52
  • $\begingroup$ Answer given is $(47).8!$ $\endgroup$ – mathemather Jan 2 '16 at 15:54
  • $\begingroup$ 47*8! for standing in a row ? $\endgroup$ – true blue anil Jan 2 '16 at 16:05
  • $\begingroup$ yes, for standing in row. $\endgroup$ – mathemather Jan 2 '16 at 16:20
  • 1
    $\begingroup$ @user84413: Inspired by your comment, I finally found time to develop the method . I know good old PIE is simpler, but the fun lies in trying new things ! $\endgroup$ – true blue anil Feb 11 '16 at 10:35
1
$\begingroup$

Use the principle of inclusion and exclusion. Say an arrangement has property $i$ if people of nationality $i$ sit together, and you want the arrangements with no properties. If, say, the two Britons, sit together, they can be considered one, and arranged among themselves in $2! = 2$ ways.

$\endgroup$
0
$\begingroup$

Many problems like this can be done by assuming the men are all of different nationalities (or some other distinction) and then computing the permutations of interchanging the same men, and dividing by it.

If all the men are different, putting them in a line can be done in $ 10! $ ways. So the answer will be

$$ \dfrac{10!}{2!2!2!} $$

The two factorials are the division by the same nationalities of men.

However, as you have pointed out, each man must not be next to a man of the same nationality. Your last few sentences are trying to address the case of the separate cases being the same.

As a fix for this, consider doing it case wise. Placing the men together in a line can be done in 9 ways (think of the two men as one unit). This means that, exclusive of the others being placed together, we have

$$ \dfrac{9!}{2!2!} $$

ways each of the nationalities can be placed together WITHOUT the others being placed together.

If two groups are placed together, then the two groups of men become like one unit. Therefore we have a way to place the two men, a way to place the other two men, and the ways to place the remaining men divided by $ 2! $ for the last men being placed together. That is like having 8 objects placed, divided by the two of the last nationality being separate, so we have

$$ \dfrac{8!}{2!} $$.

Finally, we subtract by the number of cases where all are adjacent illegally,

$$ 7! $$

which gives us a grand total of

$$ \dfrac{10!}{8} - 3* \dfrac{9!}{2!2!} - 3* \dfrac{8!}{2!} - 7! = 115,920 $$

This disagrees with the other answers.

$\endgroup$
0
$\begingroup$

This is not an original answer; it is simply another way to count the arrangements using the method presented by true blue anil:

If we label the people $A_1, A_2, B_1, B_2, C_1, C_2$ and $D, E, F, G$,

we can first arrange $A_1, B_1, C_1, D, E, F, G$ in order in $7!$ ways,

and then we have 6 places for $A_2$, 7 places for $B_2$ and 8 places for $C_2$

so that the $A's$ are not adjacent and similarly for the $B's$ and the $C's$.

This gives a total of $7!\cdot6\cdot7\cdot8=8!\cdot42$ possibilities.


Now we count the missing cases:

1) orderings with $A_1B_2A_2$ or $A_2B_2A_1$:

there are 2 ways to order the A's, $\;6!$ ways to arrange this block and $B_1, D, E, F, G,\;\;$ and $7\cdot6$ ways to place the C's so they are not adjacent, for a total of $2\cdot6!\cdot7\cdot6=7!\cdot12$ possibilities.

2) orderings with $A_1C_2A_2$ or $A_2C_2A_1:\;\;$ there are also $7!\cdot12$ possibilities, as above.

3) orderings with $B_1C_2B_2$ or $B_2C_2B_1:\;\;$ there are also $7!\cdot12$ possibilities, as above.

4) orderings with $A_1B_2C_2A_2$ or $A_2B_2C_2A_1$ or $A_1C_2B_2A_2$ or $A_2C_2B_2A_1$:

there are 2 ways to order the A's, 2 ways to order the B and C, and then $7!$ ways to order this block and the remaining 6 people, for a total of $2\cdot2\cdot7!=7!\cdot4$ possibilities.

Therefore we have a total of $8!\cdot42+7!\cdot36+7!\cdot4=8!\cdot47$ such arrangements.

$\endgroup$
0
$\begingroup$

In a row: There are 10!

ways to arrange the people. We now count the bad arrangements, in which two A's are next to each other, or two B's, or two C's.

To do the counting, we use Inclusion/Exclusion. How many arrangements have the two A's together? Put them in a bag. We now have
8 people and 1 bag. These can be arranged in 9! ways. Then when we let the A's out of the bag, they can arrange themselves in 2

ways, for a total of 2⋅9!

.

Do the same for the B's, the C's, and add up. We get 3⋅2⋅9!

.

However, we have double-counted the bad arrangements in which, for example, the A's and the B's are together. The same bag argument shows there are 2 2 ⋅8!

such arrangements, for a total of 3⋅2 2 ⋅8!

.

Thus our next estimate for the number of bads is 3⋅2⋅9!−3⋅2 2 ⋅8!

.

However, we have subtracted one too many times the arrangements in which the A's are together, and the B's, and the C's. The now familiar technique shows there are 23⋅7! of these. So add back 2 3 ⋅7!

.

We end up with 7!(6⋅9⋅8−12⋅8+8)

, which is 8!⋅43

.

This is the number of bad arrangements. The number of good arrangements is 10!−8!⋅43 , which is 8!⋅47

.

Circular table: We use the convention that two orders are to be considered the same if they differ by a rotation. Assume that one of the "others" is a Canadian. He/she is probably too polite to complain, so one can put the Canadian in the worst chair.

The remaining chairs can now be thought of as a line. We have 9

people, including 3 "others" to put in a line, with the condition that the two A's, two B's, and two C's are separated. Same Inclusion/Exclusion technique.

$\endgroup$
-1
$\begingroup$

For the first one, Total no of combinations is, $$ s = \frac{ 10!}{2!.2!.2!} $$ Now let A represent the group in which two Americans are together, B represent 2 British together and C represent group in which 2 Chinese are together, calculate $ A \cup B \cup C$ and subtract it from s.

So the final answer is $$ \frac{ 10!}{2!.2!.2!} - 3.\frac{9!}{2!.2!} + 3.\frac{8!}{2!} - 7! $$

$\endgroup$
  • $\begingroup$ How many elements are in each of A, B and C? $\endgroup$ – theREALyumdub Jan 2 '16 at 15:35
  • $\begingroup$ No of elements in A is $ \frac{9!}{2!.2!} $ $\endgroup$ – Cloverr Jan 2 '16 at 15:40
  • $\begingroup$ This is still not a correct answer, no? As OP points out, you have to consider the cases where two groups appear next to each other or even three, which will be in multiple sets, or none of the sets (as you have indicated). $\endgroup$ – theREALyumdub Jan 2 '16 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.