In how many ways can $7$ girls and $3$ boys sit on a bench in such a way that every boy sits next to at least one girl

$7$ girls can be seated in $7!=5040$ ways. Each seating creates six inner slots where one or two boys can be placed, and two end slots where at most one boy can be placed.

When no two boys shall sit together we can place them in $8\cdot 7\cdot6=336$ ways in the eight slots ($8$ choices for the first boy, $7$ remaining for the second, and $6$ for the third).

When two boys shall sit together we can choose any of the $6$ inner slots for them. Then we can pick the lefthand one of the two in $3$ ways, the righthand one in $2$ ways. Finally we can choose any of the $7$ leftover slots for the third boy. In all we have $6\cdot3\cdot2\cdot 7=252$ possibilities for such an arrangement.

It follows that the total number of admissible seatings is given by $$5040\cdot(336+252)=2\,963\,520\ .$$


Hint: Consider the complement, which is "there is a boy who sits between two boys OR there is a boy at the end of the line who is next to a boy".

There are 10! ways to arrange without restriction.

There are $ 3! \times 8!$ ways to arrange BBB as a block.

There are $3! \times 8! \times 2$ ways to arrange BB as a block at either end.

There are $ 3! \times 7! \times 2$ ways to arrange BBB as a block at either end.


We can also solve it using a two variable recursion:

Let $A(b,g)$ be the number of ways of arranging the string of B's and G's, such that it does not contain ``BBB'' as a substring. It can be written as:

\begin{align*} A(b,g) &= A(b,g-1)+A(b-1,g-1)+A(b-2,g-1) \\ A(0,g) &= 1 \\ A(1,g) &= 1+g \\ A(2,g) &= \binom{2+g}{2} \\ A(b,0) &= 0 \end{align*} Since we also need a condition that it cannot begin with "BBG'' or end with "GBB'', the number of valid strings (by PIE) are $$A(m,n)-2\, A(m-2,n-1)+A(m-4,n-2)$$ where $m$ and $n$ are the number of boys and girls, respectively.

Since B's and G's are distinguishable, the total number of possible ways are

$$\mathbb{N}\left(m,n\right) = \Big(A(m,n)-2\, A(m-2,n-1)+A(m-4,n-2)\Big)\cdot m!\cdot n!$$

And for our problem, $\mathbb{N}(3,7) = 98\cdot 3!\cdot 7! = 2963520$

Update

We can get a generating function, from its regular expression (obtained by building a deterministic finite automaton and minimizing it), as described in analytic combinatorics

The RE is $((g+bg)g^*b)^*(\epsilon+(g+bg)g^*)$ and the g.f. obtained will be: \begin{align*} G(x,y) &= \mathrm{SEQ}\left(\left(y+xy\right)\mathrm{SEQ}(y)x\right)\left(1+(y+xy)\mathrm{SEQ}(y)\right) \\ &= \mathrm{SEQ}\left(\frac{y+xy}{1-y} x\right)\left(1+\frac{y+xy}{1-y}\right) \\ &= \frac{1+xy}{1-y(1+x+x^2)} \end{align*}

Update 2

From the g.f, we can also get the following formula:

\begin{align*} \mathbb{N}(m,n) &= \left(\sum_{k=\lfloor m/2 \rfloor}^m \binom{n-1}{k}\binom{k}{m-k-1} + \binom{n}{k}\binom{k}{m-k}\right)\cdot m! \cdot n! \end{align*}