2
$\begingroup$

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?

  • 0
    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.2012-03-07

2 Answers 2

1

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

  • 1
    @dtldarek: why don't you edit your answer to include joriki's correction, and I'll accept it?2012-03-07
1

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.

  • 1
    @Joe: I actually find dtlsdarek's answer slightly simpler, once the unnecessary complication from treating the ends separately is removed.2012-03-07