I'm working on a general version of the problem linked here.
To quote the original:
Suppose =10 married couples are invited to a bridge party. Bridge partners are chosen at random, without regard to gender. What is the probability that no one will be paired with his or her spouse?
The approach that the original poster uses is the inclusion-exclusion principle which makes sense. However, I'm not really understanding how they end up at their final equation:
$P=\sum_{k=1}^{10}(-1)^{k+1}\binom{10}{k}\frac{(20-2k)!}{20!}\prod_{j=0}^{k-1}(20-j) = \sum_{k=1}^{10}(-1)^{k+1}\binom{10}{k}\frac{(20-2k)!}{20!}\frac{20!!}{(20-2k)!!}$
More specifically, how I'm thinking of modelling this problem is that you line up all the individuals in a given order. Index these people by their position in the line, starting at 1. Then the couples formed are (1,2), (3,4), (5,6), etc. There are $20!$ such orders.
Let $O$ be the set of all orderings. Let $ON$ be the set of permutations in which no spouses are together. Let $O_i$ be the set of all orders in which the $i^{th}$ couple are spouses. Then to find the number of orderings in which no couples are spouses, we can compute:
$|ON| = |O| - |\cup_{i=1}^{i=10}|$
Clearly $|O| = 20!$. Computing $|\cup_{i=1}^{i=10}|$ is where I need the inclusion exclusion principle:
$|\cup_{i=1}^{i=10}| = \sum_{i = 1}^{10}|A_i| - \sum_{1 \leq i < j \leq 10}|A_i \cap A_j| + ... + (-1)^{n-1}|\cap_{i=1}^{10}A_i|$
I agree with the original poster that the $n^{th}$ term/summation of the above equation should be computed as:
${10 \choose n}2^n\frac{10!}{(10-n)!}*(20-2n)!$
Here ${10 \choose n}$ is the number of different groups of $n$ couples we can fix to be spouses, $2^k$ is the ways each of these couples can be ordered, $\frac{10!}{(10-n)!}$ is the number of positions these couples can take among the $10$ couples, and the finally $(20-2n)!$ are the number of permutations of the other - not necessarily matched - couples. Then using the inclusion exclusion principle I would end up with the summation:
$|\cup_{i=1}^{i=10}| = (-1)^{n+1}\sum_{i = 1}^{10}{10 \choose n}2^n\frac{10!}{(10-n)!}*(20-2n)!$
However I'm lost as to how this is equivalent to the original poster's equation above, and it gets a very different numerical answer. Where am I going wrong here?