There are 4 boys and 4 girls. In how many ways can they sit in a row such that no two girls sit together. I tried this for a long time but im not getting there, not even close. So far I tried finding out the total number of ways you could sit these boys and girls if there were no restriction, that came out to be 40320.
EDIT
Now I found out the number of ways you could seat 2 girls together ( fixing the place of a boy beside them to ensure that 3 girls and 4 girls are not counted). So 2(for no. Of ways you could arrange them eg BGG or GGB)
4 for no. Of ways you could select 1 boy from the four boys to be Next to the two girls
12 for no. Of ways you could arrange the two girls out of 4
6- for no. Of positions they could be in ( _ _ _ _ _ B G G. )
And lastly 5! Ways you could have one row.
Next I found out the number of ways you could seat 3 girls together. Similarly This came out to be 3840.
Next I found out the number of ways you could seat 4 girls together. Similarly This came out to ne 2880
Adding this all yields something higher than 40320 which is impossible. Please tell me where I went wrong. This same reasoning works for 3 girls and 2 boys but not for this could there be some Possible reason behind that?
Best Answer
Generically, I know of two distinct approaches to the problem: Stars and Bars (Method 1 in this response) and Inclusion-Exclusion (Method 2 in this response).
$\underline{\text{Where You Went Wrong}}$
You tried an informal approach to Inclusion-Exclusion, where you attempted to manually prevent over-counting specific situations and also attempted to not overlook any specific situations. Such an informal approach to Inclusion-Exclusion generally leads to trouble. See Method 2, below, for a formal approach to Inclusion-Exclusion.
$\underline{\text{Method 1 : Stars and Bars}}$
For Stars and Bars theory, see this article and this article.
Temporarily, assume (wrongly) that the girls are indistinguishable from each other and that the boys are indistinguishable from each other, and obtain an intermediate computation. Then, you will simply multiply this computation by $~4! \times 4!~$ to compensate for the girls and boys each actually being distinguishable.
When the $~4~$ girls (which analogize to bars) are placed in the row, they will form $~5~$ islands (before the 1st girl, and after each of the girls). The boys will then be placed (in some order) in the $~5~$ islands.
So, continuing to pretend that the boys and girls are actually indistinguishable, the placement of both the boys and the girls is completely determined by the size of the $~5~$ islands.
For example, consider enumerating the number of solutions to
$x_1 + x_2 + x_3 + x_4 + x_5 = 4.$
$x_1, ~x_2, ~x_3, ~x_4 \in \Bbb{Z_{\geq 0}}.$
Per Stars and Bars theory, the number of solutions is $~\displaystyle \binom{4 + [5-1]}{5-1} = \binom{8}{4},~$ which corresponds to what your intuition would suggest, for the number of ways of selecting $~4~$ positions out of $~8~$ to place the $~4~$ boys.
So, within Method 1, the problem is reduced to determining how to refine the constraints so as to perfectly dovetail with the requirement that no two girls can sit together.
Note that if $~x_1 = 0,~$ this exactly corresponds to the first person in the row being a girl. Similarly, if $~x_5 = 0,~$ this exactly corresponds to the last person in the row being a girl. Both of these situations are permitted by the problem.
However, if any of $~x_2, ~x_3,~$ or $~x_4~$ are equal to $~0,~$ this exactly corresponds to there being no seats between girl-$n~$ and girl-$(n+1),~$ where $~n \in \{1,2,3\}.$ So the refinement to the original bullet pointed constraints above is to add the constraint that $~x_2, ~x_3,~$ and $~x_4~$ are each $~\geq 1.$
This presents a minor challenge, because basic Stars and Bars theory is based on the presumption that each of the variables, $~x_1, ~\cdots, ~x_k~$ is permitted to be any non-negative integer. The fix is to implement a partial change of variables.
For $~i \in \{2,3,4\},~$ let $~y_i = x_i - 1.$
Then, you will have that $~y_i \in \Bbb{Z_{\geq 0}} \iff x_i \in \Bbb{Z_{\geq 1}}.$
You will also have that
$$x_1 + x_2 + x_3 + x_4 + x_5 = 4 \iff x_1 + {\color{red}{y_2 + y_3 + y_4}} + x_5 = 4-3 = 1.$$
Per Stars and Bars theory, the number of solutions to the refined problem is $~\displaystyle \binom{1 + [5-1]}{5-1} = \binom{5}{4} = 5.~$
Therefore, the final answer is
$$5 \times 4! \times 4!.$$
$\underline{\text{Method 2 : Inclusion-Exclusion}}$
For this particular problem, this approach is do-able, but not recommended. This portion of the answer is included to illustrate where the original poster went wrong.
See this article for an introduction to Inclusion-Exclusion. Then, see this answer for an explanation of and justification for the Inclusion-Exclusion formula.
This section of the answer will adopt the syntax from the second link in the previous paragraph.
Let $~S~$ denote the collection of distributions of the $~4~$ distinguishable girls and $~4~$ distinguishable boys, where the prohibition against two girls being together is ignored.
Note that there are $~\displaystyle \binom{4}{2} = 6~$ ways that a violation could occur, because that is how many ways there are of selecting a distinct pair of girls to be in violation. Here, violation signifies that a specific pair of girls are seated together.
Let:
Then, the entire problem reduces to computing
$$|S| - |S_1 \cup S_2 \cup \cdots \cup S_6|.$$
Let $~T_0~$ denote $~|S|.~$
Let $~T_1~$ denote $~\displaystyle \sum_{k=1}^6 |S_k|.$
For $~r \in \{2,3,4,5,6\},~$
let $~T_r~$ denote $~\displaystyle \sum_{1 \leq i_1 < i_2 < i_3 < \cdots < i_r \leq 6} |S_{i_1} \cap S_{i_2} \cap \cdots \cap S_{i_r}|.$
That is, $~T_r~$ represents the summation of $~\displaystyle \binom{6}{r}~$ terms.
Then, in accordance with Inclusion-Exclusion theory, the final answer will be
$$\sum_{r=0}^6 (-1)^{r+1} T_r.$$
So, the entire problem is reduced to the computation of each of $~T_0, ~T_1, ~\cdots, ~T_6.$
$\underline{\text{Computation of} ~T_0}$
Since the boys and girls are each distinguishable,
$$T_0 = |S| = 8!.$$
$\underline{\text{Computation of} ~T_1}$
First consider $~S_1~$ which represents that Girl-1 and Girl-2 are together. Then, you can assume that Girl-1, Girl-2 form a fused unit. So now, instead of having $~8~$ units to permute, you only have $~7~$ units to permute.
Further, the fused unit, [Girl-1 : Girl-2] can be internally permuted in $~2!$ ways. That is, Girl-1 might come either immediately before, or immediately after Girl-2.
So, $~|S_1| = 2! \times 7!.~$
By considerations of symmetry, you have that
$$|S_1| = |S_2| = \cdots = |S_6|.$$
Therefore,
$$T_1 = \binom{6}{1} \times 2! \times 7! = 12 \times 7!.$$
$\underline{\text{Computation of} ~T_2}$
This computation is somewhat different from the computation of $~T_1,~$ because the considerations of symmetry will not be so convenient.
The $~\displaystyle \binom{6}{2} = 15~$ ways of selecting $~i_1, i_2,~$ such that $~1 \leq i_1 < i_2 \leq 6,~$ will fall into two patterns:
The pair represented by $~S_{i_1}~$ does not intersect the pair represented by $~S_{i_2}.$
Of the $~15~$ terms (i.e. intersections) involved in the computation of $~T_2,~$ exactly three of them will fall into this pattern. These three are $~S_1 \cap S_6, ~S_2 \cap S_5, S_3 \cap S_4.~$
To compute $~|S_1 \cap S_6|,~$ note that Girl-1 and Girl-2 are fused together and Girl-3 and Girl-4 are fused together. Therefore, you have $~6~$ units to permute, with each of the two fused units internally permutable in $~2!~$ ways (i.e. Girl-1 can come immediately before or immediately after Girl-2).
Therefore, $~|S_1 \cap S_6| = 2! \times 2! \times 6!.$ Therefore, by symmetrical considerations, the partial enumeration of $~T_2~$ that is represented by this particular bullet point is
$~3 \times 2! \times 2! \times 6!.$
The pair represented by $~S_{i_1}~$ does intersect the pair represented by $~S_{i_2}.$
From the previous bullet point, you can surmise that this must be represented by exactly $~(15 - 3 = 12)~$ pair intersections. Alternatively, you can reason as follows:
Consider the specific set $~S_1 \cap S_2,~$ which intersects with Girl-1, and excludes Girl-4. Because Girl-1 must be next to both Girl-2 and Girl-3, Girl-1 must be in the middle of the fused unit formed by Girl-2, Girl-1, Girl-3.
Then, there are $~4~$ ways of choosing the odd girl out, which in the $~S_1 \cap S_2~$ example is represented by Girl-4. Once the odd girl out is chosen, there are then $~3~$ ways of determining which of the $~3~$ remaining girls will be the girl in the middle.
To compute $~|S_1 \cap S_2|,~$ consider that you now have $~6~$ units to permute, and the Girl-2,Girl-1,Girl-3 fused unit allows exactly 2! internal permutations, since Girl-1 is now fixed as the girl in the middle.
Therefore, $~|S_1 \cap S_2| = 2! \times 6!.$ Therefore, by symmetrical considerations, the partial enumeration of $~T_2~$ that is represented by this particular bullet point is
$~12 \times 2! \times 6!.$
Therefore,
$$T_2 = (3 \times 2! \times 2! \times 6!) + (12 \times 2! \times 6!) = 36 \times 6!.$$
$\underline{\text{Computation of} ~T_3}$
The $~\displaystyle \binom{6}{3} = 20~$ ways of selecting $~i_1, i_2,i_3~$ such that $~1 \leq i_1 < i_2 < i_3 \leq 6,~$ will fall into three patterns:
The pairs represented by $~S_{i_1}, S_{i_2},~$ and $~S_{i_3}~$ involve exactly $~3~$ of the $~4~$ girls.
Of the $~20~$ terms (i.e. intersections) involved in the computation of $~T_3,~$ exactly four of them will fall into this pattern. These four are $~S_1 \cap S_2 \cap S_4, ~S_1 \cap ~S_3 \cap S_5, ~S_2 \cap S_3 \cap S_6, ~S_4 \cap S_5 \cap S_6].~$
To compute $~|S_1 \cap S_2 \cap S_4|,~$ note that :
$~S_1 \cap S_2~$ requires that Girl-1 be the girl in the middle. This specifically requires that on the immediate left and immediate right of Girl-1 will be Girl-2 and Girl-3, in some order.
$~S_1 \cap S_4~$ requires that Girl-2 be the girl in the middle.
This specifically requires that on the immediate left and immediate right of Girl-2 will be Girl-1 and Girl-3, in some order.
So, the $~S_1 \cap S_2 \cap S_4$ intersection requires that Girl-1, Girl-2, and Girl-3 are fused into a single unit with both Girl-1 and Girl-2 required to be the girl in the middle. This is impossible.
Therefore, the partial sum for the $~4~$ intersections represented by this pattern is $0.$
There is one specific girl that occurs in all three pairs represented by $~S_{i_1}, S_{i_2},~$ and $~S_{i_3}.~$
Of the $~20~$ terms (i.e. intersections) involved in the computation of $~T_3,~$ exactly four of them will fall into this pattern. These four are $~S_1 \cap S_2 \cap S_3, ~S_1 \cap ~S_4 \cap S_5, ~S_2 \cap S_4 \cap S_6, ~S_3 \cap S_5 \cap S_6.~$
To compute $~|S_1 \cap S_2 \cap S_3|,~$ note that :
Girl-1 is required to have, as immediate neighbors, all three of Girl-2, Girl-3, and Girl-4. This is impossible.
Therefore, the partial sum for the $~4~$ intersections represented by this pattern is $0.$
The remaining $~12~$ (out of the $~20$) intersections of three sets involve all four girls, with no girl occurring in more than $~2~$ of the three intersections. The specific set $~S_1 \cap S_4 \cap S_6~$ is representative.
To compute $~|S_1 \cap S_4 \cap S_6|,~$ note that Girl-2 and Girl-3 must be immediate neighbors, Girl-2 must also have Girl-1 as an immediate neighbor, and Girl-3 must also have Girl-4 as an immediate neighbor. There are only two possible satisfying arrangements here:
[Girl-1 : Girl-2 : Girl-3 : Girl-4] or [Girl-4 : Girl-3 : Girl-2 : Girl-1].
In both arrangements above, the four girls have been fused into one unit, so that there are now $~5~$ units to permute. Therefore, $~|S_1 \cap S_4 \cap S_6| = 2 \times 5!.$
So, since there are $~12~$ (of the $~20$) intersections that follow this pattern, the partial sum for this pattern is
$12 \times 2 \times 5! = 24 \times 5!.$
Adding the three partial sums above gives
$$T_3 = 0 + 0 + (24 \times 5!).$$
$\underline{\text{Computation of} ~T_r ~: ~r \geq 4}$
The following analysis indicates that for $~r \geq 4,~$ you have that $~T_r = 0.$
Without loss of generality, you can assume that one of the pairs is $~S_1~$ which involves Girl-1 and Girl-2. Then, either $~S_6~$ (which involves Girl-3 and Girl-4) is also one of the four pairs or it isn't.
Suppose that $S_6$ is one of the four pairs.
Now, a third pair must be chosen from one of the remaining four pairs. This third pair must repeat two of the girls, so that each of the two girls will now be appearing in two of the three pairs chosen so far.
Without loss of generality, you can assume that the third pair is $~S_2,~$ which involves Girl-1 and Girl-3.
Then, of the three remaining pairs, the fourth pair selected must not include either Girl-1 or Girl-3, since that would then require that either Girl-1 or Girl-3 have three distinct neighbors, which is impossible.
So, the fourth pair chosen would have to be $~S_5,~$ which involves Girl-2 and Girl-4.
However, examination of the set $~S_1 \cap S_6 \cap S_2 \cap S_4~$ indicates that it is the empty set.
Suppose that $S_6$ is not one of the four pairs.
Then, the second pair chosen will either also involve Girl-1, or also involve Girl-2. Without loss of generalization, assume that the second pair chosen is $~S_2,~$ which involves Girl-1 and Girl-3.
At this point, two more pairs must be selected, and $~S_6~$ must not be included. Also, since Girl-1 has occurred in both of the (so far) chosen pairs $~S_1~$ and $~S_2,~$ you can not have $~S_3~$ also chosen. This is because this would then force Girl-1 to have three distinct immediate neighbors, which is impossible.
So, the only possibility left to explore is $~S_1 \cap S_2 \cap S_4 \cap S_5.~$ This particular set is also seen to be the empty set because it forces Girl-2 to have three distinct immediate neighbors, which is impossible.
$\underline{\text{Final Computation}}$
$$\sum_{r=0}^6 (-1)^{r+1} T_r = T_0 - T_1 + T_2 - T_3$$
$$= (T_0 + T_2) - (T_1 + T_3)$$
$$= [8! + (36 \times 6!)] - [(12 \times 7!) + (24 \times 5!)]$$
$$= 6! \times \left\{ ~[56 + 36] - [84 + 4] ~\right\}$$
$$= 6! \times 4 = (30 \times 4!) \times 4 = 120 \times 4! = 5 \times 4! \times 4!.$$
$\underline{\text{Addendum}}$
In crafting the Inclusion-Exclusion section, I initially considered defining the subsets $~S_1, S_2, \cdots, S_k~$ differently, so as to streamline the approach. That is, for $~k \in \{1,2,3,4\},~$ I considered having $~S_k~$ represent the subset of $~S~$ where Girl-k had at least one other girl as one of her two immediate neighbors.
The difficulty with this alternative formulation of the subsets $~S_k~$ is that it significantly compounded the analysis of (for example) $~S_1 \cap S_2.~$
That is, if Girl-1 is next to a girl, and Girl-2 is next to a girl, you could simply have Girl-1 and Girl-2 next to each other (in some order).
Alternatively, Girl-1 and Girl-2 could each have (for example) Girl-3 as a common immediate neighbor, so that Girl-3 is the girl in the middle.
Or, (for example) Girl-1 and Girl-4 could be immediate neighbors and Girl-2 and Girl-3 could be immediate neighbors.
In my opinion, this way lies madness.