How many ways can $n$ adults, $k_1$ boys and $k_2$ girls be seated in a line such that no two children of the same sex sit next to each other?

It was shown in this question that the number of ways $n$ adults and $k$ children can be seated in a line such that no two children are sitting next to each other is: $$\binom{n+1}{k}n!k!.$$

Now let's say we have $n$ adults, $k_1$ boys and $k_2$ girls. No two boys can sit next to each other, and no two girls can sit next to each other, but boys can sit next to girls. What is the number of ways they can be seated now?

• Let us sit the boys first this is can be done in $k_1!$ ways, now we have $\binom{k_1+1}{k_2} \times k_2!$ ways of sitting the girls. Now we have to put $n$ adults in $k_1+k_2+1$ places where each position can have any number of adults. – Quixotic Mar 7 '12 at 11:18
• @Foool: You can have boys sitting next to each other then. – joriki Mar 7 '12 at 11:33
• I managed to derive a recurrence relation for $f(n,k_1,k_2)$. There are two ways to seat the last girl: a. first seat everyone except the last girl ($f(n,k_1,k_2-1)$ configurations), and then we have $n+k_1-k_2+2$ places to seat the last girl; b. choose two boys ($k_1(k_1-1)$ possible choices, their order matters), seat only them next to each other (it's like having one less boy, so $f(n,k_1-1,k_2-1)$ configurations), and then put the last girl between them. Putting it together we get: $f(n,k_1,k_2)=(n+k_1-k_2+2)f(n,k_1,k_2-1)+k_1(k_1-1)f(n,k_1-1,k_2-1)$. – Joe Mar 7 '12 at 11:56
• Naturally the initial condition of the recurrence is $f(n,k,1)=f(n,1,k)=\binom{n+2}{k}(n+1)!k!$, since this is like having only boys or only girls. – Joe Mar 7 '12 at 12:01

This formula is not short, but please bear it ;-). $n$ is number of adults, $a$ and $b$ number of boys and girls respectively, and finally $m$ the number of pairs (in the pair the girl always sits on right-hand side). For $m$ chosen pairs you can place them in the following order: put $(n+m)$ pairs and adults in any order $(n+m)!$, then place additional non-paired boys right of any adult $\binom{n}{a-m}$ and any non-paired girls left of any adult $\binom{n}{b-m}$. This does not account for additional boy you can place left of left-most adult (if there is no pair left of him) and additional girl you can place right of right-most adult (if there is no pair right of him). Adjusting we get: $$X_m = \\ (b-m)!\binom{n}{b-m}(n+m)!\binom{n}{a-m}(a-m)! \\ + 1_an(b-m)!\binom{n}{b-m}(n-1+m)!\binom{n}{a-1-m}(a-1-m)! \\ + (b-1-m)!\binom{n}{b-1-m}(n-1+m)!\binom{n}{a-m}(a-m)!n1_b\\ + 1_an(b-1-m)!\binom{n}{b-1-m}(n-2+m)!\binom{n}{a-1-m}(a-1-m)!(n-1)1_b$$ And then sum it up by possible number of pairs: $\sum_{m=0}^{\min(a,b)} X_m$ (right now I have no idea how to make it shorter).

Edit 1: corrected a little order mistake.

Edit 2: Joe wanted to include here jorki's simplification (see the comments), so here it is (the main idea is that you can place the boy at the end, and treating him as a teacher we have following expression; similarly for right-most girl): $$X_m=n!a!b!\binom{n+1}{a−m}\binom{n+1}{b−m}\binom{n+m}{n}$$.

• This approach is a great idea! I think your formula needs some corrections though. First of all, swapping $a$ and $b$ shouldn't matter, so we can assume WLOG $a \ge b$. Second of all, since we can always put a boy in the left most place in the line (whether there's an adult there or not), I think the expression for $X_m$ is simply: $\binom{n+1}{a-m}(n+m)!$. Third, It's not hard to see that there is a minimal number of pairs which might be greater than zero, so the summation should be $\sum_{m=\max{(0,a-n-1)}}^b$. – Joe Mar 7 '12 at 12:39
• If you assume that $a \geq b$ then you cannot always put a boy in the left most place in the line -- by the inequality boys and girls are now different. About the summation, it may be, but I guess that then some of the binomials will be equal to 0 (and this way the expression is simpler). Still I think this can be much much simpler if we forget the order first and multiply by $n!a!b!$ afterwards, i.e. first term of $X_m$ would be $\binom{n}{b-m}\binom{n+m}{n}\binom{n}{a-m}$. However that does not simplify further :-( – dtldarek Mar 7 '12 at 12:57
• But I think you can put a boy in the left most place in line. If there is an adult there he is next to the adult, and if there is no adult then there is a pair, and he is next to a girl. In both cases it is possible. Also, I don't see how a binomial can ever be equal to zero, since it is defined as a positive integer. – Joe Mar 7 '12 at 13:23
• I believe Joe is right. This is essentially the answer I was about to post, except you don't need the complication involving the ends since you can treat them as adults and use $n+1$ in the two binomials. But @Joe, why do you propose to include only $\binom{n+1}{a-m}$ and not $\binom{n+1}{b-m}$? I believe the correct value is $X_m=n!a!b!\binom{n+1}{a-m}\binom{n+1}{b-m}\binom{n+m}n$, just like dtldarek wrote in the comment except with $n$ replaced by $n+1$ for the ends. – joriki Mar 7 '12 at 13:42
• @dtldarek: why don't you edit your answer to include joriki's correction, and I'll accept it? – Joe Mar 7 '12 at 17:29

Assume to start with that within each group the people are indistinguishable.

Place $n$ adults, and then there are $n+1$ gaps into which to place the children. Each group of children is a string of the form b?(gb)*g?. Denote the number of groups with a left-most boy as $s_b$ and the number of groups with a right-most girl as $s_g$. Then we require $k_1 - s_b = k_2 - s_g$ (the pairs are pairs) and $s_b \le n+1$, $s_g \le n+1$ (we don't have more groups than there are groups).

Given valid $s_b$, $s_g$, we can place the pairs as in the original problem (although since we're considering them indistinguishable, we get $\binom{n+k_1-s_b-1}{k_1-s_b}$ placements). We then place the surplus boys in one of $\binom{n+1}{s_b}$ ways and the surplus girls in $\binom{n+1}{s_g}$ ways.

This leads to the result $$\sum_{s_b=0}^{k_1} \sum_{s_g=0}^{k_2} [k_1 - s_b = k_2 - s_g][s_b \le n+1][s_g \le n+1] \binom{n+k_1-s_b-1}{k_1-s_b} \binom{n+1}{s_b} \binom{n+1}{s_g}$$ $$= \sum_{s_b=0}^{\min(k_1, n+1)} [0 \le s_b + k_2 - k_1 \le \min(k_2, n+1)] \binom{n+k_1-s_b-1}{k_1-s_b} \binom{n+1}{s_b} \binom{n+1}{s_b + k_2 - k_1}$$ $$= \sum_{s_b=\max(0, k_1-k_2)}^{\min(k_1, n+1, n+1 + k_1 - k_2)} \binom{n+k_1-s_b-1}{k_1-s_b} \binom{n+1}{s_b} \binom{n+1}{s_b + k_2 - k_1}$$

Then post-multiply by $n!k_1!k_2!$ to account for the people being distinguishable within their types.

• Nice! This is a similar approach to @dtldarek's answer, only simpler. Though, after joriki's correction that answer becomes simple as well. – Joe Mar 7 '12 at 13:45
• @Joe: I actually find dtlsdarek's answer slightly simpler, once the unnecessary complication from treating the ends separately is removed. – joriki Mar 7 '12 at 13:51