# How many ways are there for W women and M men to sit on N chairs, if no man can sit next to woman?

So, we have:

W - count of women
M - count of men
N - count of chairs standing in a row (N > M + W)


Each person sits on her chair, and only two men or two women can sit on adjacent chairs. How many possibilities are there for them to sit?

• If there are e.g. too many men relative to women, there would be no way to avoid adjacent chairs. – coffeemath May 24 '16 at 13:24
• @coffeemath I think that's covered by $N>M+W$, no? After all, you can just put all the men on the left and all the women on the right. – lulu May 24 '16 at 13:25
• @coffeemath: It is allowed to have a man and a woman with an empty chair between them. – Henning Makholm May 24 '16 at 13:29
• @coffeemath Since $N>M+W$ we have a category $E$ of empty chairs. – lulu May 24 '16 at 13:30
• Sorry, i was wrong, i worked on this on question for one or two hour, I am sure somebody will get a solution to this question or a proof that there is no solution to it. Lets see who does it. – A---B May 24 '16 at 18:16

We shall be using both Theorem 1 and Theorem 2 of stars and bars

Let us put number of empty chairs as $E = N-(W+M)$, with $W,M,E >0$

These $E$ chairs act as bars (dividers) in the stars and bars approach, making $(E+1)$ boxes in which to put women and men, treated as just categories for the moment.

We can place the women in $A$ boxes, $1\le A \le E$, using Theorem $1$ in $\binom{W-1}{A-1}$ ways,
choosing the $A$ boxes in $\binom{E+1}{A}$ ways

$(E+1-A)$ boxes now remain, and we can place the men using Theorem $2$ in $\binom{M+E-A}{E-A}$ ways

If each person is treated as distinct, we shall, of course, have to multiply by $W!M!$

Putting the pieces together, # of ways = $$W!M!\sum_{A=1}^E\binom{E+1}{A}\binom{W-1}{A-1}\binom{M+E-A}{E-A}$$

I have put the condition $W,M,E>0$ to exclude trivialities.

• The analysis is right, but there are typos. First, the $N$ in the sum should be an $E$, from the explanation. Second, the upper limit of the sum should be $E+1$. Third, the middle binomial coefficient within the sum should be $W+A-1\choose A-1$. I think that's it. If so, the answer is $$W!M!\sum_{A=1}^{E+1}\binom{E+1}{A}\binom{W+A-1}{A-1}\binom{M+E-A}{E-A}$$, which seems to address your observations. – Steve Kass May 25 '16 at 0:51
• Ah, not quite. The middle binomial coefficient was correct. Women are placed into exactly $A$ groups with at least one woman in each group. But the answer with this correction is not quite right, because the stars-and-bars formula for partitioning $n$ into $k$ parts only apply when $n$ and $k$ are positive. So perhaps we could write the answer as $W!M!\sum_{A=1}^{E+1}\binom{E+1}{A}{\binom{W-1}{A-1}}^*{\binom{M+E-A}{E-A}}^o$ where the “starred” and “circled” binomial coefficients mean stars-and-bars problem answers for positive parts (*) and nonnegative parts ($\circ$) – Steve Kass May 25 '16 at 1:36
• @SteveKass: If the upper limit is $E+1$, there will be no boxes left for men. And Theorem $1$ and $2$ (as given by Wiki) both are treated under stars and bars combinatorics. – true blue anil May 25 '16 at 2:31
• If there are 0 men, the $A=E+1$ term is important. Let $W=2, M=0, N=3$. If you don’t let $A$ go to $E+1=2$, you’ll only count arrangements with the women together (in the same “box”); you’ll miss arrangements with an empty chair between the women. As for stars-and-bars, I’m not sure what you’re saying. The Theorems in Wikipedia are correct, but they only apply when $n$ and $k$ are positive. Let $M=3, W=0, N=5$ and look at the $A=1$ term. It uses $-1\choose0$ for the number of ways to put 0 women into 1 group with no empty group. But there are no ways, yet $-1\choose0=1$. – Steve Kass May 25 '16 at 2:58
• Oh, and one more thing. The sum has to start at $A=0$, not $A=1$. If there are no women, then there are no ways to put them into a positive number of “boxes”, and you’ll miss arrangements with no empty chairs at either end of the row of chairs and men. – Steve Kass May 25 '16 at 3:08

Let $F(N,M,W)$ be the answer. We have boundary conditions \eqalign{F(N,0,W) &= {N \choose W} \ \text{for}\ W \le N\cr F(N,M,0) &= {N \choose M} \ \text{for}\ M \le N\cr F(N,M,W) &= 0 \ \text{for}\ M, W > 0,\; N \le M+W\cr } Otherwise consider the possibilities for the first empty chair. If the first empty chair is in position $j+1$, then the first $j$ positions are either all men or all women. $$F(N,M,W) = F(N-1,M,W) + \sum_{j=1}^{M} F(N-j-1, M-j,W) + \sum_{j=1}^{W} F(N-j-1,M,W-j)$$

Hmm. It looks like $F(2i+n,i,i)$ is the coordination sequence for the lattice $A_n$: see e.g. OEIS sequence A005901. This has generating function

$$\sum_{k=0}^n {n \choose k}^2 z^k/(1-z)^n = P_n\left( \dfrac{1+z}{1-z}\right)$$ where $P_n$ is the $n$'th Legendre polynomial.

And more generally, $F(n+2i+j,i+j,j)$ (for fixed $n$ and $j\ge 0$) seems to have generating function $$\sum_{k=0}^n {n-j \choose k}{n+j \choose n-k} z^k/(1-z)^n$$