What is the Derangements Math Problem for Dance Competition?

[cragar]

Homework Statement

Twenty five men and twenty five women attend a dance competition. The com-
petition rules are: There are n dance events, and each dancer must participate in
all n events. In each event each man must be partnered with a woman for that
dance. In each subsequent event, no man may partner with a woman with whom
he was partnered during an earlier event.
(b) If n=3, how many different ways are there to form new man-woman pairs for
the third dance event in such a way that the competition rules are not violated?

The Attempt at a Solution

for the first dance their should be 25! ways to arrange the first dance. Then for the second dance we use the derangement formula to subtract away the bad ones, but for the 3rd dance it gets quite tough. I tried doing inclusion exclusion but weird exceptions keep showing up,I tried looking for patterns but nothing seemed to work. I tried doing it for smaller groups of people. Does anyone know what its called when we have n=3, would that be the 3rd permutation or is it called something else, If anyone could provide any info or where I should read more about it or what it is called. I would really appreciate it.

 

[awkward]

Hi cragar,

I haven't worked the problem out in detail, but here is an approach which I think might work.

Let's say N is the number of acceptable ways that partners can be assigned for the first two dances. (You seem to know how to compute N.) Given an acceptable arrangement, then, each woman has danced with exactly two men.

If we ignore the requirement that a woman must not duplicate a previous partner, we can have N \cdot n! arrangements in which the first two dances are acceptable but the third dance is possibly unacceptable. Let's say the assignment of partners for the third dance "has property i" if the ith woman duplicates one of her two previous partners. Then maybe you can use PIE to find the number of the N \cdot n! arrangements which have none of the n properties.

[edit]It's not clear to me, from the problem statement, whether you are supposed to count the total number of arrangements for all three dances or just the number of ways to assign partners for the third dance, given that the first two are OK. If the latter, then try applying PIE to the n! ways that partners could potentially be assigned in the third dance-- i.e., subtract the bad arrangements from n! instead of N n!.[/edit]

 

[tiny-tim]

hi cragar!

(this problem looks unusually difficult …

is it from a book, or have you made it up yourself?)

have you noticed that you can break down each arrangement of the first two dances into cycles …

try getting everyone to shake left hands with the person they danced with first, and right hands with the person they danced with second …

what happens? ​

 

[cragar]

So i thought about how at dance 3 they would have 2 less choices for their last dance to pick from. And when you try to make them shake hands you get people that have danced with the same person but from different dances.
Thanks for your help.