Find the number of ways so that each boy is adjacent to at most one girl.

There are $7$ boys and $3$ girls who need to be lined up in a row. Find the number of ways so that each boy is adjacent to at most one girl.

In simple terms the situation demands that any distribution of the type $$...GBG...$$ must not come into play.

First of all the total number of arrangements are $10!$ and we can actually find a complement of those situations which we don't want.

In order to calculate the number of ways in which the wrong position can be true, I considered $GBG$ to be kind of a single package. The number of ways to make this package are:$${7 \choose 1} \cdot {3 \choose 2} \cdot 2!$$, now considering this package and $6$ boys plus the $1$ girl left, we can permute them all in 8! ways [$6$ boys, $1$ girl and our "package"], thus making the total to be $$ {7 \choose 1} \cdot {3 \choose 2} \cdot 2! \cdot 8! \tag{1}$$

Things seem to be tractable hithero, but as I was writing this questions I saw one problem in my argument: The cases containing the configurations $GBGBG$ have been possible counted several times thus $(1)$ is not giving the correct number of ways to be subtracted.

Can we anyhow make some changes in this approach and find the solution?

Considering the boys and girls indistinguishable, each arrangement has the form

$$ (S_1\, G \,S_2 \,G \,S_3 \,G\, S_4)$$

where $S_i$ is the count of consecutive boys, with $S_i\ge 0$ and $\sum S_i=7$. The restriction ("each boy is adjacent to at most one girl") corresponds to $S_2\ne 1$ and $S_3\ne 1$.

Let $W_{n,k}=\binom{n+k-1}{k-1}$ count the weak compositions of $n$ in $k$ parts (ways of summing $k$ non-negative numbers to obtain $n$, order matters).

Then the legal arrangements are given by

$$ W_{7,4} - 2 W_{6,3} + W_{5,2}=\binom{10}{3}-2\binom{8}{2}+\binom{6}{1}=70$$

The $W_{6,3}$ term substracts the forbidden configurations ($S_2=1$ or $S_3=1$), and the $W_{5,2}$ term compensates (inclusion-exclusion) for the double counting of the $S_2=1$ and $S_3=1$ cases.

But boys and girls are distinguishable, hence we multiply by the permutations. And the final answer is

$$ 70 \times 7! \times 3! =2116800 $$

Before seating the individuals we have to count the admissible arrangements of boys and girls.

Between two girls there can be $0$ or $\geq2$ boys. It follows that the admissible arrangements are of the following four types: $$\eqalign{b^xg^3b^y,&\qquad x+y=7,\cr b^x gb^{2+y}g^2 b^z\quad{\rm or}\quad b^x g^2 b^{y+2}gb^z,&\quad x+y+z=5,\cr b^x g b^{2+y}gb^{2+z}gb^w,&\quad x+y+z+w=3\cr}$$ with $x$, $y$, $z$, $w$ integers $\geq0$. The number of these arrangements is $${8\choose1}+2\cdot{7\choose2}+{6\choose3}=70\ .$$ Taking the names of the boys and girls into account we arrive at $$7!\,3!\,70=2\,116\,800$$ admissible configurations.

I suggest another solution, based on methods of analytic combinatorics (I think the bible of the subject is this book by P. Flajolet and R. Sedgewick).

A good configuration (taking only gender into account) looks something like this

\begin{align*} {\mathop{SEQ}}(B) \,\,G \,\,{\mathop{SEQ}}^{\neq 1}(B) \,\,G \,\,{\mathop{SEQ}}^{\neq 1}(B) \,\,G \,\,{\mathop{SEQ}}(B), \end{align*}

meaning:

• A (possibly empty) sequence of $B$oys; followed by
• $G$irl; followed by
• A (possibly empty) sequence of $B$oys, except for the sequence with a single $B$oy; followed by
• $G$irl; followed by
• A (possibly empty) sequence of $B$oys, except for the sequence with a single $B$oy; followed by
• $G$irl; followed by
• A (possibly empty) sequence of $B$oys.

This corresponds to a generating function:

$$f(z) = \frac{1}{1-z} \cdot z \cdot \left(\frac{1}{1-z} - z\right) \cdot z \cdot \left(\frac{1}{1-z} - z\right) \cdot z \cdot \frac{1}{1-z} = \frac{z^3\,{(1-z+z^2)}^2}{(1-z)^4}.$$

You are interested in the case where there are $10$ persons, so that's the coefficient of $z^{10}$ in the expansion of $f(z)$:

$$[z^{10}]\,f(z) = [z^7]\,\frac{{(1-z+z^2)}^2}{(1-z)^4}.$$

This is easily computed to be $70$.

Now, for each such configuration we can permute the boys around in $7!$ ways and the girls around in $3!$ ways, while preserving the configuration. This should gives us a total of

$$70\cdot 7! \cdot 3! = 2116800$$

good orderings.

I think this exposition shows that the problem boils down to: How can we distribute $7$ boys over $4$ bins, where $2$ of the bins cannot be assigned exactly one boy? (Each bin can be empty.)
This also generalizes easily to $b$ boys and $g$ girls. We'd have

$$f(z) = \frac{z^g\,{\left(1-z+z^2\right)}^{g-1}}{(1-z)^{g+1}},$$

the coefficient would be

$$[z^{b+g}]\,f(z) = [z^b]\,\frac{{\left(1-z+z^2\right)}^{g-1}}{(1-z)^{g+1}}$$

and the answer would thus be

$$[z^b]\,\frac{{\left(1-z+z^2\right)}^{g-1}}{(1-z)^{g+1}} \cdot b! \cdot g!$$

Let's focus on the positions of the boys and girls initially, without worrying about which boy or girl sits in which seat.

Let $B$ denote the position of a boy; let $G$ denote the position of a girl.

We have a sequence of length $10$ comprised of $7$ $B$s and $3$ $G$s. If there were no restrictions, the number of such sequences would be $\binom{10}{3} = 120$. From these, we must subtract those sequences in which a $B$ is adjacent to two $G$s.

A $B$ is adjacent to two $G$s: We have eight objects to arrange: $GBG, G, B, B, B, B, B, B$. There are eight ways to choose the position of the block $GBG$ and seven ways to choose the position of $G$, which completely determines the sequence. Hence, there are $8 \cdot 7 = 56$ arrangements with a $B$ adjacent to two $G$s.

However, if we subtract these arrangements from the total, we will have subtracted too much since we will have subtracted those arrangements in which two $B$s are each adjacent to two $G$s twice, once for each way we could designate one of those $B$s as being the one that is adjacent to two $G$s. We only want to subtract them once, so we must add them back.

Two $B$s are each adjacent to two $G$s: Since there are only three $G$s, we must have a block of the form $GBGBG$. Thus, we have six objects to arrange: $GBGBG, B, B, B, B, B$. There are six ways to choose the position of the block, which completely determines the sequence.

By the Inclusion-Exclusion Principle, there are $120 - 56 + 6 = 70$ sequences of the positions of the boys and girls in which no boy is adjacent to two girls.

For each of the $70$ admissible ways of choosing the positions of the boys and girls, the seven boys can be arranged in their positions in $7!$ ways and the three girls can be arranged in their positions in $3!$ ways. Hence, the number of admissible seating arrangements is $70 \cdot 7!3!$.

Addendum: The reason your approach did not work is that you subtracted those arrangements in which a block of the form $GBGBG$ twice when you subtracted the number of arrangements that included a block of the form $GBG$, once for each way you could have designated one of the boys as the one who is adjacent to two girls. Therefore, we need to add those arrangements to your answer.

There are $\binom{7}{2}$ ways to choose the boys in the block of the form GBGBG and $2!$ ways to arrange them in the block. There is only one way to select all three girls to be in the block and $3!$ ways to arrange them within the block. Together with the other five boys, we have six objects to arrange, the block and the other five boys. These objects can be arranged in $6!$ ways. Therefore, there are $$\binom{7}{2}2!3!6!$$ arrangements in which two boys are each adjacent to two girls.

Adding this term to your count gives $$10! - \binom{7}{1}\binom{3}{2}2!8! + \binom{7}{2}2!3!6!$$ in agreement with the answer above.