2
$\begingroup$

Two seatings are considered the same if one can be obtained from the other by rotating the table.

The question I am stuck on is: How many different ways can the $10$ kids be seated if no two girls can sit next to each other?

So far what I have is there are $(4-1)=3!$ ways to seat the girls around the table. To ensure that the girls are not seated next to each other we put one boy in between each girl. Then there are $\binom{6}{4}$ ways to seat four boys in this way. To seat the two remaining boys, there are $9$ seats for the fifth one, and after placing the fifth another seat opens, so there are $9$ ways to seat the last one. So we have:

$3!\cdot\binom{6}{4}\cdot8\cdot9=6480$ as the answer.

The second part that I'm unsure about is: How many different ways can the $10$ kids be seated if all $6$ boys want to sit next to each other, that is, the $6$ boys must be seated in $6$ adjacent seats?

My solution is there are $6!$ ways to arrange the boys and then $4$! ways to arrange the girls. So there are $6!\cdot4!=17280$ ways to arrange them, but this feels far too large.

Would anybody be able to check this? Thanks in advance

$\endgroup$
  • 1
    $\begingroup$ 17280 is not to large, I agree with the 2nd part $\endgroup$ – Rocco van Vreumingen Feb 20 at 22:22
  • $\begingroup$ Note for the 1st part that if you see all boys and girls as the same, then there are only 3 ways. $\endgroup$ – Rocco van Vreumingen Feb 20 at 22:34
1
$\begingroup$

Your second answer is correct.

In how many ways can six boys and four girls be seated around a table if no two girls are adjacent?

Method 1: Suppose one of the boys is Asa. We will use him as a reference point. The remaining five boys can be seated in $5!$ ways as we proceed clockwise around the table from Asa. Seating the six boys creates six spaces in which a girl could be placed, one to the left of each boy. To separate the girls, we must choose four of these six spaces in which to place a girl. The girls can be arranged in the four selected spaces in $4!$ ways as we proceed clockwise around the table from Asa. Hence, the number of admissible seating arrangements is $$5!\binom{6}{4}4!$$

Method 2: We modify your attempt. Suppose Adrienne is one of the girls. The other girls can be seated in $3!$ ways as we proceed clockwise around the table from Adrienne. This creates four spaces in which to place the boys, one to the left of each girl. Let $x_1, x_2, x_3, x_4$ denote, respectively, the number of boys in the first, second, third, and fourth spaces as we proceed clockwise around the table from Adrienne. Since there are a total of six boys, $$x_1 + x_2 + x_3 + x_4 = 6$$ Since no two of the girls are adjacent, there must be at least one boy in each of the four spaces. Hence, this is an equation in the positive integers. A particular solution of the equation corresponds to placing three addition signs in the five spaces between successive ones in a row of six ones.
$$1 \square 1 \square 1 \square 1 \square 1 \square 1$$ For instance, placing an addition sign in the first, second, and fourth spaces gives $$1 + 1 + 1 1 + 1 1$$ which corresponds to the solution $x_1 = 1$, $x_2 = 1$, $x_3 = 2$, $x_4 = 2$. The number of such solutions is the number of ways we can place three addition signs in the five spaces between successive one in a row of six ones, which is $$\binom{6 - 1}{4 - 1} = \binom{5}{3}$$ One the number of boys in each space has been selected, the boys can be arranged in those spaces in $6!$ ways as we proceed clockwise around the table from Adrienne. Hence, there are $$3!\binom{5}{3}6!$$ admissible seating arrangements.

Method 3: We correct your approach. Again, suppose Adrienne is one of the girls. The other girls can be seated in $3!$ ways as we proceed clockwise around the table from Adrienne. Choose which four of the six boys will sit to the immediate left of a girl. Those boys can be arranged in $4!$ ways as we proceed clockwise around the table from Adrienne. That leaves two boys to place. There are two possibilities: both boys are placed between the same two girls so that there are three boys between those girls or they are placed between separate pairs of girls so that there are two pairs of girls with two boys between them.

Both of the remaining boys are placed between the same two girls: There are four ways to choose the pair of girls the boys sit between. Both boys must sit to the left of the boy who has already been seated to the immediate left of the first girl we encounter in the pair as we proceed clockwise around the table from Adrienne (starting with Adrienne). There are two ways to choose which of the boys who has not yet been seated sits next to that boy. Hence, there are $\binom{4}{1}2!$ such cases.

The remaining boys are placed between two different pairs of girls: There are $\binom{4}{2}$ ways to choose which two pairs of girls the boys sit between. In each case, the boy must be seated to the left of the boy who has already been seated to the immediate left of the first girl we encounter in the pair as we proceed clockwise around the table from Adrienne (starting with Adrienne). There are two ways to choose which of the boys we will encounter first as we proceed clockwise around the table from Adrienne. There are $\binom{4}{2}2!$ such cases.

Thus, there are $$3!\binom{6}{4}4!\left[\binom{4}{1}2! + \binom{4}{2}2!\right]$$ admissible seating arrangements.

Your errors:

You forgot to arrange the four boys you placed in the gaps, so you were missing a factor of $4!$. Had you included that factor, your count would have been too large. The reason for this is that you counted the same arrangement more than once. For instance, if Asa, Bradley, and Charles all sit between Adrienne and Bronwyn, your approach would count the same arrangement $3! = 6$ times, corresponding to the $3!$ orders in which the same boys could be placed in the same seats. If Asa and Bradley were to be placed between Adrienne and Bronwyn and Charles and David were to be placed between Bronwyn and Claire, then your approach would count the same arrangement four times, corresponding to the $2!$ orders in which Asa and Bradley could be placed in the same seats and the $2!$ orders in which Charles and David could be placed in the same seats.

$\endgroup$
1
$\begingroup$

HINTS:

For the first question: imagine glueing a boy on the left of each girl and consider them as one entity, this way you can ensure that there wont be girls next to eachother.

For your second question: it seems correct, one sometimes gets unexpectedly large numbers when dealing with combinatorics

Hope I could help :)

$\endgroup$

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.