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*}

I think I've got an answer. Please tell me if you see any fault with it.

A method of subtracting the impossible cases seemed to be the best but I no longer think so. However. The answer they gave seems wrong either way.

So working with the cases that are possible it's either

B B B

G G G G G G G

OR

BB B

G G G G G G G

In the first case, all the boys are separated. They must fill one slot either between two girls or on the end each. All of these cases are valid

$7! \times {^8\mathrm{P}_3} = 1 693 440$

In the second case, there is a group of 2 boys and one boy on its own that need to be sorted. The group of 2 CANNOT be on either end so only the spaces in between the girls is valid where the last boy can occupy any space including the ones on the end EXCEPT the one where the group of two occupied a space

$7! \times {^3\mathrm{P}_2} \times {^6\mathrm{P}_1} \times {^7\mathrm{P}_1} = 1 270 080$

$\begin{align}\operatorname{n}(S) &= 1 693 440 + 1 270 080 \\ & = 2 963 520\end{align}$

                        --------------->

Please tell me if you think I've made a false assumption or worked something out incorrectly