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

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 $$


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!$$


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.