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

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

Let $G = \{g_1,g_2,g_3\}$, $B = \{b_1,\ldots,b_7\}$, and let $X$ be the set of all permutations of $G\cup B$. Now for $1\le i\le 8$ let $A_i$ be the set of permutations $\pi\in X$ s.t. $\pi(i), \pi(i+2)\in G$ and $\pi(i+1)\in B$.

We need to find $|X\setminus\bigcup_i A_i|$, which, by the Inclusion-Exclusion Principle, is equal to $$\sum_{j\ge 0}(-1)^j S_j,$$ where $S_j = \sum_{i_1,\ldots,i_j} |A_{i_1}\cap\cdots\cap A_{i_j}|$.

$S_0$ is simply $|X| = 10!$, $|A_i| = 3\cdot 2\cdot 7\cdot 7! = 42\cdot 7!$ (pick a girl at position $i$, then another girl at position $i+2$, then a boy at position $i+1$, then place the remaining children in arbitrary way), so $S_1 = 8\cdot 42\cdot 7!$.

Similarily, $|A_i\cap A_{i+1}| = 0$, $|A_i\cap A_{i+2}| = 3\cdot 2\cdot 1\cdot 7\cdot 6\cdot 5! = 6\cdot 7!$, $|A_i\cap A_{i+r}| = 0$ for $r>2$, so $S_2 = 6\cdot 6\cdot 7!$ and $S_j = 0$ for $j\ge 3$.

Finally, the answer is $10!-S_1+S_2 = 2116800$.

Answer 4

Using the same logic as @Fimpellizieri, the problem can also be solved by elementary techniques. Any problematic arrangement looks like $$S \, GBG \, S \, G \, S $$ or $$S \, G \, S \, GBG \, S $$ where the $S$ parts are (possibly non-empty) sequences of boys. Now, for both the cases, the problem is reduced to a problem of putting $6$ boys into $3$ places, which using stars-and-bars algorithm, can be easily solved. The number turns out to be ${6+3-1 \choose 6}={8 \choose 6}=28$. Since the boys and girls can be shuffled amongst themselves in all the cases, the total number is $28 \times 7! \times 3!=846720$.

Combining two cases, the total number of invalid cases is $2 \times 846720=1693440$. Note that we are counting the cases of the form $$S \, GBGBG \, S $$ twice. Using a similar algorithm as before, the total number of such cases is ${5+2-1 \choose 5}\times 7! \times 3!=6 \times 7! \times 3! = 181440$.

Hence, the total number of permitted arrangements is $10!-1693440+181440=2116800$.

(I started to calculate it before @Fimpellizieri 's answer was posted. Since my approach is much more elementary and simple to understand, I decided to post it anyway.)

Calculations corrected thanks to flaw spotted by @leonbloy.

Answer 5

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

Answer 6

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.

Answer 7

There are many simpler methods already here so I have opted to use a more long-winded approach. However it does include a $2$-variable generating function and general formula.

The problem is equivalent to counting strings using alphabet $\{b,g\}$ with the property that no $b$ is directly adjacent to two $g$'s. This is given by the regular expression:

$$(1+bg)g^*(b^2b^*gg^*)^*b^*\tag{Regular Expression}$$

$(1+bg)g^*$ starts the sequence with a (possibly empty) sequence of $g$'s or a $b$ followed by a sequence of at least 1 $g$.

$(b^2b^*gg^*)^*$ takes the sequence of at least $2$ $b$'s followed by a sequence of at least $1$ $g$ and then constructs a sequence of these sequences.

$b^*$ ends the sequence with a (possibly empty) sequence of $b$'s.

This translates to the ogf in the usual way:

$$\begin{align}f(b,g)&=(1+bg)\cdot \frac{1}{1-g}\cdot\frac{1}{1-\frac{b^2}{1-b}\frac{g}{1-g}}\cdot\frac{1}{1-b}\\[1ex]&=\frac{1+bg}{1-b-g+bg-b^2g}\\&=\frac{1+bg}{(1-b)(1+bg)-g}\\\end{align}$$

$$f(b,g)=\frac{1}{1-\left(b+\frac{g}{1+bg}\right)}\tag{ogf} $$

In general we may express this as a summation:

$$\begin{align}f(b,g)&=\frac{1}{1-\left(b+\frac{g}{1+bg}\right)}\\[1ex] &=\sum_{n\ge 0}\left(b+\frac{g}{1+bg}\right)^n\\[1ex] &=\sum_{n\ge 0}\sum_{k=0}^{n}\binom{n}{k}b^k\frac{g^{n-k}}{(1+bg)^{n-k}}\\[1ex] &=\sum_{n\ge 0}\sum_{k=0}^{n}\binom{n}{k}b^kg^{n-k}\sum_{r\ge 0}\binom{r+n-k-1}{n-k-1}(-bg)^r\\[1ex] &=\sum_{n,k,r}(-1)^r\binom{n}{k}\binom{r+n-k-1}{n-k-1}b^{k+r}g^{n-k+r}\, .\end{align}$$

Call $t=n-k+r$, then

$$f(b,g)=\sum_{t}g^{t}\sum_{n,r}(-1)^r\binom{n}{t-r}\binom{t-1}{t-r-1}b^{n-t+2r}\, .$$

Call $s=n-t+2r$ so $r=(s+t-n)/2$ is a non-negative integer:

$$f(b,g)=\sum_{t,s}g^{t}b^{s}\sum_{n}(-1)^{(s+t-n)/2}\binom{n}{\tfrac{1}{2}(t-s+n)}\binom{t-1}{\tfrac{1}{2}(t-s+n)-1}\, .$$

Hence we may take the coefficient of $g^tb^s$ in $f(b,g)$ to give a general result:

$$[g^tb^s]f(b,g)=\sum_{n}(-1)^{(s+t-n)/2}\binom{n}{\tfrac{1}{2}(t-s+n)}\binom{t-1}{\tfrac{1}{2}(t-s+n)-1}\, .$$

Where the sum takes place over the range of $n$ values that gives integer $(s+t-n)/2$ and binomials are defined such that $\binom{p}{q}=0$ for $p-q\lt 0$ and $p-q\gt p$.

In our case $t=3$, $s=7$:

$$[g^3b^7]f(b,g)=(-1)^{2}\binom{6}{1}\binom{2}{0}+(-1)^{1}\binom{8}{2}\binom{2}{1}+(-1)^0\binom{10}{3}\binom{2}{2}=70\, .$$

Then since the $3$ girls and $7$ boys are distinct we have:

$$70\cdot 3!7!=2\,116\,800\tag{Answer}$$

arrangements.