seating arrangements : How many seating arrangements there is such that between every two men there is an even number of women

Question

How many seating arrangements on a table there is such that between every two men there is an even number of women ( Note : there is an equal number of women and men such that the number of men is n and the number of women is also n and there is 2n seats around the table )

Answer 1

Obviously $2|n$ for any such arrangement to be possible. Let the seats "marked" for men to be $m_1,m_2,\cdots m_n$. Let the number of seats between $m_1,m_2=x_1; m_2,m_3=x_2;\cdots , m_n,m_1=x_n$. Note that $\sum_{i=1}^{n}x_i=n$. Also, all $x_i$s are even. Then using generating functions, $Z$=possible values of $x_i=$ Coeff. of $z^n$ in: $$(z^0+z^2+\cdots+z^n)(z^0+z^2+\cdots+z^n)\cdots(z^0+z^2+\cdots+z^n)\ \ (n\ times) $$ $$=(1+z^2+z^4+\cdots upto\ \infty)^n$$ $$=(1-z^2)^{-n}$$ $$=\binom{3n/2-1}{n/2}$$ Note that I took it to infinity because the terms with power $>n$ won't affect the coeff. of $z^n$. Since it will be a circular permutation, men can sit in $(n-1)!$ ways. After that, women will sit in $n!$ ways. Answer, Total ways$=Z*(n-1)!*(n!)$

Answer 2

(I assume the table isn't round. A similar argument reduces the problem either way) Perhaps we're familiar with how many ways $n$ men and $m$ women could be arranged, a brief review if not: we need to pick $m$ spots from the $n+m$ seats for the women. This can be done in $\binom{n+m} m$ ways.

Now in this problem, we have a restriction, so we'll use a trick to convert this problem into the above: instead of placing each women separately, we place them in pairs. We have $n$ men and $w = n/2$ pairs of women (round down, we'll deal with the remainder in a moment). By the above, we then have $$\binom{n+w}{ n}$$ ways of arranging them.

Now what happens if $n$ is odd? In this case we must have a woman at the start or end of our table! To see why, note that if a man is at the beginning and end then every woman will be placed between 2 men, and hence should be able to be 'paired' together. In fact, we must have an odd number of women starting or ending the table. So when $n$ is odd, we have an extra choice of placing the last woman at the start or end of the table (if she goes in between some men, we break the rule), and so the total number of arrangments for $n$ odd is: $$2 \binom{n+w} n$$

Once we've decided where to seat the men and women, multiply by $(n!)^2$ to get the number of seat assignments for the guests.

Answer 3

Write the number of women as $n=\sum_{i=1}^{n-1} b_{i}$ where $b_{i}$ is the number of women between man $i$ and man $i+1$. If all the $b_{i}$ are to be even, so must $n$. Therefore the answer is $0$ for odd $n$.

Supposing then that $n=2k$ is even, first imagine arranging the $n$ women in a circle. Label the women $1,2,...,n$. If a man sits with woman $1$ on his left and woman $2$ on his right, then every man must sit with an odd-numbered woman on his left. Once we choose "odd" or "even", there are $n/2$ permissible locations for each man to sit. Therefore we can place them in $(n/2)^{n}$ ways (this assumes that we can have strings of men sitting sitting next to one another i.e. some of the $b_{i}$ above may equal $0$).

There are $n!$ orderings for each the men and the women. Therefore the number of total arrangements is $(n!)^{2}(n/2)^{n}$