5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ If there are e.g. too many men relative to women, there would be no way to avoid adjacent chairs. $\endgroup$ – coffeemath May 24 '16 at 13:24
  • 1
    $\begingroup$ @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. $\endgroup$ – lulu May 24 '16 at 13:25
  • 1
    $\begingroup$ @coffeemath: It is allowed to have a man and a woman with an empty chair between them. $\endgroup$ – Henning Makholm May 24 '16 at 13:29
  • 1
    $\begingroup$ @coffeemath Since $N>M+W$ we have a category $E$ of empty chairs. $\endgroup$ – lulu May 24 '16 at 13:30
  • 1
    $\begingroup$ 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. $\endgroup$ – A---B May 24 '16 at 18:16
4
$\begingroup$

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


ADDED NOTE

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Steve Kass May 25 '16 at 0:51
  • $\begingroup$ 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$) $\endgroup$ – Steve Kass May 25 '16 at 1:36
  • $\begingroup$ @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. $\endgroup$ – true blue anil May 25 '16 at 2:31
  • $\begingroup$ 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$. $\endgroup$ – Steve Kass May 25 '16 at 2:58
  • $\begingroup$ 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. $\endgroup$ – Steve Kass May 25 '16 at 3:08
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.