I came across an interesting question, in how many ways can we arrange n boys and m girls in a row such that no 3 boys are side by side (together).
Example : say n = 3, m = 2,
Then B G G B B is valid but B G B B B G is not a valid arrangement.
Note: Two arrangements are different if there is a boy in some position where there is a girl in the other arrangement. Basically, all boys are similar and all girls are similar.
For small n and m, I can draw the arrangements but I didn't find a pattern which helps me when n and m are large, say n = 100 m = 200. So I need your help, figuring out some relation or pattern.
Thanks.
Best Answer
The $m$ girls create $m+1$ slots in between them and at the ends where $0$, $1$, or $2$ boys can be placed. We can fill $r\in\{0,1,\ldots,\lfloor n/2\rfloor\}$ slots with $2$ boys. If $r$ is given we can choose these $r$ slots in ${m+1\choose r}$ ways. Then $m+1-r$ slots remain empty, and the $n-2r$ remaining boys have to be put into them. It follows that the number $N$ you are looking for is given by $$N=\sum_{r=0}^{\lfloor n/2\rfloor} {m+1\choose r}\>{m+1-r\choose n-2r}\ .$$ If $n>2(m+1)$ then this $N$ will be $=0$.