0
$\begingroup$

In how many ways you can sit $n$ men and $n$ women so that :

a) Every man sits near his wife.
b) None of the men can sit next to their wives.

I think the answer for $a)$ is $2(n-1)!$
I'm not sure if it's true or how to even start $b).$

Thanks in advance !

$\endgroup$
  • 1
    $\begingroup$ For the first, imagine putting the $n$ couples in a circle. How many ways to do that? Then each couple can have either the husband or wife on the left.... $\endgroup$ – Ross Millikan Jan 29 '15 at 16:04
  • 1
    $\begingroup$ The Question statement is a bit confusing. Probably you are asking two separate questions, as Ross interpreted it. However you should state it more clearly. Does "near his wife" mean next to his wife? Are the husbands and wives seated in alternation (husband-wife-husband-wife...)? $\endgroup$ – hardmath Jan 29 '15 at 16:08
3
$\begingroup$

$\textbf{a)}$ I will assume that "near" means "next to", in which case (as Ross Millikan suggests) we can arrange

the n couples in a circle in $(n-1)!$ ways, and then each of the n couples can be ordered in 2 ways;

so there are $2^n(n-1)!$ possible arrangements in this case.

$\textbf{b)}$ Let S be the set of all possible arrangements, and let $A_i$ be the set of arrangements in which couple $i$ sits next to each other, for $1\le i\le n$.

Then $\displaystyle |A_1^c\cap\cdots\cap A_n^c|=|S|-\sum|A_i|+\sum|A_i\cap A_j|-\sum|A_i\cap A_j\cap A_k|+\cdots$

$\;\;\displaystyle=(2n-1)!-\binom{n}{1}\cdot2\cdot(2n-2)!+\binom{n}{2}\cdot2^2\cdot(2n-3)!-\binom{n}{3}\cdot2^3\cdot (2n-4)!+\cdots$

$\displaystyle \hspace{.3 in}+(-1)^j\binom{n}{j}\cdot2^j(2n-j-1)!+\cdots(-1)^n \binom{n}{n}\cdot2^n\cdot(n-1)!.$

$\endgroup$
1
$\begingroup$

There are a total of $2n$ people. The total number of ways in which they all can be arranged in a circle is $(2n-1)!$

Now, since the husband must be seated next to wife, we assume $n$ couples. Thus, the number of ways in which $n$ couples can be arranged in a circle is $(n-1)!$. However, we can place the wife either to the left or to the right of her husband. Thus, each wife can be arranged in $2!=2$ ways. Thus, the total number of ways in which every man sits near his wife is $2(n-1)!$

Now, since the above answer contains the number of ways in which each man sits with his wife, the remaining permutations must be the number of ways in which none of the men sits with his wife. So, the answer to the second part would be $(2n-1)!-2(n-1)!$

I assumed that husband and wife don't necessarily sit alternatively. Otherwise, we would have to make a different case.

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