[Math] How many ways are there to seat six boys and eight girls in a row of chairs so that no two boys are seated next to each other

combinatorics

The way I did it was I first drew out $6$ boys and put a girl between each boy. Then I made $6$ barriers so it looked like this:
b | g b | g b | g b | g b | g b |

From these barriers, I arranged the $3$ remaining girls into one of the slots (from $6$ barriers and 3 girls or $\binom{9}{3}$. Then, I multiplied by the number of ways to arrange the girls and boys. My final answer was
$$\binom{6 + 3}{3} \cdot 8! \cdot 6!$$

After looking at similar questions on Stack, I was able to solve the problems using this strategy, however the answer my textbook has tells me that I'm over counting.

Best Answer

Method 1: We can arrange the eight girls in a row in $8!$ ways. This creates nine spaces in which to insert the boys, seven between successive girls and two at the ends of the row.
$$\square g \square g \square g \square g \square g \square g \square g \square g \square$$ To ensure that no two of the boys sit in consecutive seats, we choose six of these nine spaces in which to insert the boys, which we can do in $\binom{9}{6}$ ways. The boys can be arranged in the six selected spaces in $6!$ orders, so the number of seating arrangements of eight girls and six boys in which no two of the boys sit in consecutive seats is $$8!\binom{9}{6}6!$$ as you found.

Method 2: This is a modification of your approach.

We can arrange the six boys in a row in $6!$ ways. This creates seven spaces in which to place the girls, five between successive boys and two at the ends of the row. $$\square b \square b \square b \square b \square b \square b \square$$ If $x_k$ represents the number of girls placed in the $k$th space, then $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 = 8 \tag{1}$$ The requirement that no two boys sit in adjacent seats means that $x_2, x_3, x_4, x_5, x_6 \geq 1$, while $x_1, x_7 \geq 0$. If we let $y_k = x_k - 1$, $2 \leq k \leq 6$, then $y_k$ is a nonnegative integer. Substituting $y_k + 1$ for $x_k$, $2 \leq k \leq 6$, in equation 1 yields \begin{align*} x_1 + y_1 + 1 + y_2 + 1 + y_3 + 1 + y_4 + 1 + y_5 + 1 + y_6 + 1 + x_7 & = 8\\ x_1 + y_1 + y_2 + y_3 + y_4 + y_5 + y_6 + x_7 & = 3 \tag{2} \end{align*} Equation 2 is an equation in the nonnegative integers. A particular solution corresponds to the insertion of six addition signs in a row of three ones. The number of such solutions is $$\binom{6 + 3}{6} = \binom{9}{6}$$ since we must choose which three of the nine positions (three ones and six addition signs) will be filled with additions signs. Finally, we can arrange the eight girls in the selected positions in $8!$ ways, again yielding $$6!\binom{9}{3}8!$$

Related Question