In how many different ways can $6$ students be seated in a row of $9$ seats if a certain $3$ students* Alvin, John and Albert refuse to sit next to each other?
*No two of them are adjacent.
My attempt,
$(9P6 – 9P4)*3!=344736$
Is it correct?
[Math] In how many ways can $6$ students be seated in a row of $9$ seats if a certain $3$ students refuse to sit next to each other
combinatorics
Related Solutions
Another way of thinking is. You can freely position 9 people (including one of the special two), therefore $9!$. However the remaining one cannot sit next to the other special person, so only 8 possible positions. Overall $8 \times 9!$
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.
Best Answer
Method 1: We begin by arranging three blue balls and three red balls in a row. There are $\binom{6}{3}$ such arrangements since we must choose which three of the six spaces will be occupied by the blue balls. This creates seven spaces in which we can place three green balls, five spaces between successive balls and two at the ends of the row. For instance, $$\square \color{red}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{red}{\bullet} \square \color{blue}{\bullet} \square \color{red}{\bullet} \square$$ We now wish to insert three green balls so that no two of them are adjacent. To do so, we must choose three of these seven spaces, which can be done in $\binom{7}{3}$ ways. One such arrangement is balls and two at the ends of the row. For instance, $$\color{green}{\bullet} \color{red}{\bullet} \color{green}{\bullet} \color{blue}{\bullet} \color{blue}{\bullet} \color{green}{\bullet} \color{red}{\bullet} \color{blue}{\bullet} \color{red}{\bullet}$$
The green balls represent the positions that can be occupied by Alvin, John, and Albert; the blue balls represent the positions of the other three people; the red balls represent the positions of the three unoccupied seats. We can arrange Alvin, John, and Albert in the places occupied by green balls in $3!$ ways. We can arrange the remaining three people in the positions occupied by the blue balls in $3!$ ways.
Consequently, the number of permissible seating arrangements is $$\binom{6}{3}\binom{7}{3}3!3!$$
Method 2: We use the Inclusion-Exclusion Principle.
There are $\binom{9}{3}$ ways of choosing the locations of the empty seats and $6!$ ways of arranging the six people in the remaining seats. From these seating arrangements, we must exclude those arrangements in which the three students who do not wish to sit in adjacent seats sit in adjacent seats.
If two of Alvin, John, and Albert sit together, we have eight objects to arrange, the pair of seats in which we will place those students, the three empty seats, and the other four students. There are $\binom{8}{3}$ ways to choose three of the eight positions for the empty seats, $\binom{3}{2}$ ways to choose two of the three students to sit together, $5!$ ways to arrange the remaining objects, and $2!$ ways to arrange the pair of chosen students in the designated pair of seats.
$$\binom{8}{3}\binom{3}{2}5!2!$$
Subtracting this from the total removes those cases in which all three students sit together twice, once when we designate the leftmost two students as the pair and once when we designate the rightmost two students as the pair. Since we only wish to exclude these arrangements once, we must add them back.
If all three students sit together, we have seven objects to arrange, the three empty seats, the trio of seats occupied by Alvin, John, and Albert, and the other three people. We can select three of these seven positions for the empty seats in $\binom{7}{3}$ ways. We can arrange the remaining four objects in $4!$ ways. We can arrange Alvin, John, and Albert within the designated trio of seats in $3!$ ways. Hence, the number of seating arrangements in which Alvin, John, and Albert sit together is $$\binom{7}{3}4!3!$$
By the Inclusion-Exclusion Principle, the number of permissible seating arrangements is $$\binom{9}{3}6! - \binom{8}{3}\binom{3}{2}5!2! + \binom{7}{3}4!3!$$