Permutations with constraint

Question

Q. Find the number of different ways that $6$ boys and $4$ girls can stand in a line if

(i) all $6$ boys stand next to each other,

(ii) no girl stands next to another girl.

A. (i) There are $5$ "patterns", because I can start with $0$ to $4$ Gs, then put $6$ Bs, and then the remaining $4$ to $0$ Gs. For each pattern, $6!$ orders of B and $4!$ of G, so the answer is $5.6!.4! = 86400$.

(ii) As before, the answer is $k.6!.4!$, but it is not so easy to find $k$, the number of patterns. I can enumerate them as xGBxGBxGBxGx where each x represents $0$ to $3$ Bs, and the total of the xs is $3$. With some work, I find $k=35$. But there should be an easier way, I think.

Answer 1

(ii)

You must find the number of sums $b_1+b_2+b_3+b_4+b_5=6$ where $b_1,b_5$ are nonnegative integers and $b_2,b_3,b_4$ are positive integers.

Here $b_1$ stands for the number of boys utmost left, $b_5$ for the number of boys utmost right and e.g. $b_2$ for the number of boys between the first and the second girl on the left.

Finding this number comes to the same as finding the number of sums $a_1+a_2+a_3+a_4+a_5=3$ where then $a_i$ are nonnegative numbers.

This arises if we substitute $b_1=a_1, b_5=a_5$ and $b_i=a_i+1$ for $i=2,3,4$.

Then with stars and bars we find $\binom{3+4}4=35$ possibilities for that.

So the final number of possibilities equals $35\times4!\times6!$.

Answer 2

The answers you have found are correct but there is simpler way to approach this.

(i) Consider the 6 boys to be a single person. Now the number of permutations will be $5!$. However the boys themselves can be arranged in $6!$ ways. So, by principle of multiplication, the number of permutations if all the 6 boys stand together is $5!.6!=86400$

(ii) You need to visualize this in a different way to make things simpler.

Consider 6 boys standing with spaces between them i.e.

$ \text{ X B X B X B X B X B X B X}$

where the $\text{X}$s denote the empty spaces.

We need to place the girls in place of $\text{X}$ which is the same as "no girl stands next to another girl".

This can be done in $P(7,4)$ or $\binom{7}{4}.4!$ ways as there are 7 empty spaces or $\text{X}$s and 4 girls.

Also, the boys themselves can be arranged in $6!$ ways.

Therefore, by principle of multiplication, the number of permutations that no girl stands next to another girl is $6!.\binom{7}{4}.4!=604800$