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

Question

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

The answer is supposedly $1,693,440 + 423,360 = 2,116,800$

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

This problem is tantamount to making the arrangements with consecutive boys sitting amongst girls. The total number of ways 3 boys and 7 girls could be arranged is 10! ways. Of these, the number of ways boys sit with girls can be broken down into three cases.

1. BBB and 7 girls
2. BB, B, and 7 girls
3. B,B,B and 7 girls.

We can consider the first cast to have two pairs, the second case to have one pair and the third case to have no pairs. The summation of the number of ways on all three cases should equal 10!. In the question asked, we do not want the first one because, there happens to be a two consecutive pairs of boys sitting violating the rule. What we do not want of the second are those that start with BBG and those that end with GBB.

BBG _ _ _ _ _ _ _. This could be arranged in ${3\choose2}{7\choose1}2!7!$

Similarly _ _ _ _ _ _ _GBB. This could be arranged in ${3\choose2}{7\choose1}2!7!$

Summing these two, we get $14*3!*7!$.

Atlast what we want is the third case when there are no pairs and each boy is sitting with girls Let us call $n_1$ = no of girls and $n_2$ = no of boys

Each pair must have a left-hand member, which we can choose from any of the boys except the last one : $\tbinom{n_2-1}{p}$. This will create $n_2-p$ blocks of boys, which we can distribute into the $n_1+1$ slots between and around the girls: $\tbinom{n_1+1}{n_2-p}$. Thus the number of ways with exactly $p$ pairs is $\tbinom{n_2-1}{p}\tbinom{n_1+1}{n_2-p}$.

For p = 2: $\tbinom{3-1}{2}\tbinom{7+1}{3-2} = 8$ and this you multiply by 3! to arrange boys and 7! ways to arrange girls.

We do not want any of the above.

For p = 1:$\tbinom{3-1}{1}\tbinom{7+1}{3-1} = 2*28*3!*7! = 56*3!*7!$

Now subtract what we do not want in one pair which is $14*3!7!$

What we want from p = 1 is $(56-14)*3!*7! = 42*3!*7!$

For p = 0:$\tbinom{3-1}{0}\tbinom{7+1}{3-0} = 56 = 56*3!*7!$

What we want from p = 0 is all and thus the number of ways $ = 56*3!*7! = 1693440$

The total number of ways such that all boys sit with atleast one girl $=(56+42)*3!*7! = 98*3!*7!$ = 2963520.

Answer 6

Answer: $7\times 6\times 5\times7!=1058400$

Proof: First I count, in how many ways we can form a set $\{g_ib_j,g_kb_l,g_mb_n\}$?. This is equal to the number of one-one maps form the set $\{B_1,B_2,B_3\}$ to the set $\{g_1,g_2,g_3,g_4,g_5,g_6,g_7\}$. It is equal to $7\times 6\times 5$.

And for each set $\{g_ib_j,g_kb_l,g_mb_n\}$, there are $7!$ arrangements such that each boy is sitting next to at least one girl. It follows from the fact that we have three elements $g_ib_j,g_kb_l,g_mb_n$ and $4$ remaining girls. Since there are $7\times 6\times 5$ sets of the form $\{g_ib_j,g_kb_l,g_mb_n\}$, total number of elements is equal to $7\times 6\times 5\times7!=1058400$

Please help me to count the elements which are escaping from my counting.