Task number: 3489

There are \(n\) couples at a ball. How many ways are there to divide everyone into pairs such that no couple dances together?

  • Solution

    Dividing everyone into pairs corresponds to a bijective mapping \(f\) from \(\{1,…,n\}\) to the same set (e.g. the woman from the \(i\)-th couple will dance with the man from the \(f(i)\)-th couple).

    We are interested in the mappings without a fixed point; this corresponds to the hat-matching problem from the lecture.

Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Cs translation
Send comment on task by email