1

Trying to work out this problem:

The answer is the summation from $k = 0$ to $n$ for $(-1)^k \binom {n} {k} (2n - k)! \ 2^k $

Widawensen
  • 8,172
Diante
  • 189
  • 2
    First, do you understand what inclusion-exclusion principle is? Second, do you understand why if there are $k$ couples who we specifically want to have spouses standing together there are $\binom{n}{k}$ ways to choose which spouses those are, and $(2n-k)!2^k$ ways to arrange the people in a line so that those spouses are standing together? – JMoravitz Mar 13 '17 at 02:32
  • 1
    Note that to rearrange $AaBbCcDdEe$ so that $A$ and $a$ are standing next to eachother, you can combine the two into one symbol, say $\overline{A}$. You then arrange $\overline{A}BbCcDdEe$. You then pick whether $A$ comes immediately before or immediately after $a$. Generalize this for an arbitrary number of total couples and an arbitrary number of couples who we wish to ensure stand with spouses. – JMoravitz Mar 13 '17 at 02:35
  • Thank you for the insight I think I'm making progress, suppose we pick 1 couple from n couples this is done (2n-1)!2 ways => (n choose 1)(2n-1)2, but if we pick k couples from the n couples, then would it be: (2n -2k + k)!2^k ( just figured out the power of k, since each of the k couple can be swapped). – Diante Mar 13 '17 at 02:57
  • 1
    If we label the couples in pairs, the males being $X_1,X_2,\dots,X_n$ and the females being $x_1,x_2,\dots,x_n$ and we specifically choose $k$ of them to specifically stand together... say for example the first $k$ couples... we wish to arrange $\overline{X_1X_2\dots X_k}X_{k+1}x_{k+1}X_{k+2}x_{k+2}\dots X_nx_n$. How many ways can that be done? Count how many letters there are to be arranged by way of counting how many fewer letters there are to be arranged than had we not combined any of the couples into one symbol... that explains the $(2n-k)!$ part. The $2^k$ is for male or female first – JMoravitz Mar 13 '17 at 03:01
  • 1
    The $\binom{n}{k}$ part comes from choosing which $k$ couples are the ones we force to stay spouses together. The $(-1)^k$ and the fact that we are doing a summation comes from inclusion-exclusion. – JMoravitz Mar 13 '17 at 03:04
  • Thank you, with reference to your comments and my notes I have made sense of the problem. – Diante Mar 13 '17 at 03:10

0 Answers0