Can Cinderella avoid dancing with her stepfamily?

Let me make a function to make this solution shorter.

Let $P(n)$ is the number of ways to get $2n$ people into $n$ pairs.

Put all the people into lines. $x_{1_{1}}, x_{1_{2}}, x_{2_{1}}, x_{2_{2}}, ..., x_{n_{1}}, x_{n_{2}}$ .

So $(x_{1_{1}}, x_{1_{2}})$ will dance together, and so on.

Ex: $(x_{32_{2}}) =$ Pair 32. Position 2.

• Switching $2n$ people in a line (fixed position), $(2n)!$ ways.

• In position $(x_{1_{1}}, x_{1_{2}})$ , they can switch together again, which is the same. Ex: $(x_{1_{1}}, x_{1_{2}})$ and $(x_{1_{2}}, x_{1_{1}})$ .

• There're $n$ pairs that can switch together, divide by $(2!)^{n}$ .

• In position $(x_{1}, x_{2})$ (pair 1 and 2), they can switch to another position, which is the same. Ex: $(x_{1}, x_{2})$ and $(x_{2}, x_{1})$

• There're $\frac{2n}{2} = n$ pairs that can switch to another position in a line, divide by $(n)!$ .

Therefore, $P(n) = \frac{(2n)!}{n!\times (2!)^{n}}$

Let's get back to the question.

Use complement principle to find the number of ways.

$|A'| = |U| - |A|$ . Where $A$ is the set of number of ways that Cinderella dances with any 3 villains.

• $|U|$ is the total ways to get 50 people into 25 pairs, total ways $= P(25)$ .

Finding $|A|$ .

• First, Cinderella dances with 3 villains, $3$ ways to choose.

• Then, there'll be 48 people left. Number of ways to get 48 people into 24 pairs $= P(24)$ .

• Therefore: $|A| = 3\times P(24)$ .

Therefore: Number of ways that Cinderella doesn't dance with any 3 villains

$= P(25) - 3\times P(24)$

$= \frac{50!}{25!\times (2!)^{25}} - 3\times \frac{48!}{24!\times (2!)^{24}}$

$= 54858136867623969682835751468750$ .

Answer: $\boxed{750}$ ~~~

Self Explanatory