1
$\begingroup$

At a ball there are $n$ men and $n$ women.

(a) In how many ways can the $n$ women choose male partners for the first dance?

(b) How many ways are there for the second dance if everyone has to change partners?

For part a, I got $nC1$, and for part b, I got $(n!)^2$. I am not sure whether my answers are correct.

$\endgroup$
  • 1
    $\begingroup$ Please indicate what you have tried and where you are stuck. $\endgroup$ – N. F. Taussig Sep 2 '16 at 9:40
  • $\begingroup$ for part a, i got nC1. and for part b, i got (n!)^2. i am not sure whether my answers are correct $\endgroup$ – jassie Sep 2 '16 at 9:41
1
$\begingroup$

The first woman who makes a choice has $n$ men from which to choose. The next woman to make a choice is left with $n - 1$ men from which to choose. The third woman to make a choice is left with $n - 2$ men from which to choose. The $k$th woman to make a choice has $n - k + 1$ men from which to choose, so the final woman has only one choice. Thus, the number of ways the women can choose their partners for the first dance is $n!$.

The number $\binom{n}{1} = n$ is the number of ways a woman can choose one of the $n$ men. More generally, the number $\binom{n}{k}$ is the number of subsets of size $k$ that can be selected from a set with $n$ elements. In this problem, the order of selection matters. If Alice makes the first choice and Brenda makes the second choice, Alice selecting Andrew as her dance partner and Brenda choosing Brian as her dance partner is different from Alice selecting Brian as her dance partner and Brenda choosing Andrew as her dance partner. Consequently, this is a permutation rather than a combination.

Since each woman must be paired with a different man for the second dance than she was in the first dance, the second question is about a derangement on $n$ people.

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