1
$\begingroup$

The statement: There is 9-ways to 4 couple to dance with each other, when nobody can dance with his/her own partner.

Is true or not? And why? How can one calculate this?

This means 4 girl and 4 boy, every boy can dance with 3 girl, but repetition should be subtracted, isn't it?

Thanks for the help!

Edit: Is this question the same?

Edit2.: The accepted answer solves my question how I wanted to solve it, Ross Millikan provided the simplest and most convenient solution.

$\endgroup$
2
  • $\begingroup$ do you know what a derangement is? $\endgroup$ – Oria Gruber Feb 24 '15 at 22:56
  • $\begingroup$ No, the question you link to is not the same, because each husband eliminates two seats for his wife (unless he is on the end), while in your problem woman eliminates one spot for her partner $\endgroup$ – Ross Millikan Feb 24 '15 at 23:34
1
$\begingroup$

I would suggest solving this problem by inclusion-exclusion.

Assuming that we can label the couples $1,2,3,4$... Let $A_1$ be the set of all pairings where couple $1$ is matched up, $A_2$ be the set of all pairings where couple $2$ is matched up, and so on. Then, you can count the number of elements in $A_i$, $A_i \cap A_j$, $A_i \cap A_j \cap A_k$, and $A_1 \cap A_2 \cap A_3 \cap A_4$. Once you do that, you can use inclusion-exclusion to find out how many elements are in $A_1 \cup A_2 \cup A_3 \cup A_4$, which is the set of all pairings in which there is at least one couple dancing together. The complement is the set of all pairings in which there is no couple dancing together.

$\endgroup$
4
  • $\begingroup$ There is 4 pairings that should not dance with each other, the remaining is the all possible combination, and the couple 'Ai' equals 4 possible way? 4*4*4*4 - 4 - repetitions?? Should I calculate $A_1 \cup A_2, $A_2 \cup A_3, $A_3 \cup A_4, $A_1 \cup A_2 \cup A_3 ...etc to calculate this? .. cups $\endgroup$ – pokemarine Feb 24 '15 at 23:16
  • $\begingroup$ $\lvert A_1 \cup \cdots \cup A_4 \rvert = \sum \lvert A_i \rvert - \sum \lvert A_i \cap A_j \rvert + \sum \lvert A_i \cap A_j \cap A_k \rvert - \sum \lvert A_i \cap A_j \cap A_k \cap A_l \rvert$. $\endgroup$ – symmetricuser Feb 24 '15 at 23:17
  • $\begingroup$ Which comes out to $4 \times 3! - 6 \times 2! + 4 \times 1 - 1 \times 1 = 15$, and $4! - 15 = 9$, which is the desired answer. $\endgroup$ – symmetricuser Feb 24 '15 at 23:19
  • $\begingroup$ I needed to use this formula, thanks. Also, I am linking this: math.stackexchange.com/questions/688019/… $\endgroup$ – pokemarine Feb 24 '15 at 23:34
4
$\begingroup$

If you imagine lining the couples up, then you need to make a derangement of the men. The linked article shows there are the closest integer to $\frac {4!}e$ of those, which is $9$.

$\endgroup$
4
  • $\begingroup$ I don't know, the test that contained this should work only with integers and the exact number should be the answer or something else, but not a real number. $\endgroup$ – pokemarine Feb 24 '15 at 23:00
  • 1
    $\begingroup$ It is a natural number. It is just the easiest way to find it is to do the division by $e$ and round. $\endgroup$ – Ross Millikan Feb 24 '15 at 23:02
  • $\begingroup$ @pokemarine There's also a recurrence formula if you prefer that. Using $!n$ as the derangements of $n,$ $!1 = 0, !2 = 1$ and $!n = (n-1)(!(n-1)+!(n-2))$. $\endgroup$ – Joffan Feb 24 '15 at 23:10
  • $\begingroup$ Okay, so derangement is exactly for this. I didn't know. Still, I should have solved it without this knowledge. $\endgroup$ – pokemarine Feb 24 '15 at 23:21
1
$\begingroup$

You can walk through on cases - it's not too bad. We have partners $(a_i, b_i), i=1..4$ and allocating the $a_i$ :

$$ \begin{array}{c|c|c} a_1 \to b_2 & a_2 \to b_1 & a_3 \to b_4 * & a_4 \to b_3 \\ a_1 \to b_2 & a_2 \to b_3 & a_3 \to b_4 * & a_4 \to b_1 \\ a_1 \to b_2 & a_2 \to b_4 & a_3 \to b_1 * & a_4 \to b_3 \\ \end{array}$$

In each case the * indicates a forced choice to allow completion of the matching under the rules.

By symmetry on $a_1$'s allocation, there are $3\times 3 = 9$ possibilities.

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