Suppose we have $2n$ people and we want to make $n$ ordered pairs of these $2n$ people. So we can chose $2$ people for the first pair in ${2n\choose2}$ ways, then we are left with $2n-2$ people and we can chose $2$ of them for the second pair in ${2n-2\choose2}$ ways and so on. So the number of ways of forming $n$ ordered pairs of $2n$ people is then $${2n\choose2}{2n-2\choose2}….{2\choose2}=\frac{(2n)!}{2^n}$$. But we can also proceed like this : We first choose $n$ people from those $2n$ people in ${2n\choose n}$ ways, then we get two groups of $n$ people each and then we can make pairs among them in $n!$ ways and so the total number of ways of forming $n$ ordered pairs of $2n$ people is $$\frac{(2n)!}{n!n!}n!=\frac{(2n)!}{n!}$$. But these two answers are different?
Ways to form pairs of 2n people
combinationscombinatoricspermutationsprobability
Related Solutions
Given $n$ people, where $n$ is even, you can choose the first pair of people ${n \choose 2}$ ways, where ${n \choose 2}=\frac{n!}{2!(n-2)!}$. The next pair can be chosen in ${n-2\choose 2}$ ways, etc... The end result will be $\frac{n}{2}$ pairs which can be arranged in $\left(\frac{n}{2}\right)!$ ways. So there are $$\frac{{n \choose 2}{n-2 \choose 2}\dots{2 \choose 2}}{\left(\frac{n}{2}\right)!}=\frac{n!}{\left(\frac{n}{2}\right)!\,2^{\left(\frac{n}{2}\right)}}$$ ways to arrange all $n$ people into sets of pairs.
So for 8 people there are $\frac{8!}{4!\,2^{4}}=105$ possible sets of pairs.
Now the question remains, how many sets are there that do not contain any pairs from the original set?
Let $$f(x)=\frac{x!}{\left(\frac{x}{2}\right)!\,2^{\frac{x}{2}}}$$
If $S=\left\{p_{1}, p_{2}, ..., p_{\frac{n}{2}}\right\}$ is our original set of pairs and $P_{k}$ is the set of all sets containing $p_{k}$, where $1\le k\le\frac{n}{2}$ then by the inclusion-exclusion principal the number of sets not containing any of the original pair is:
$$f(n)-\left(|P_{1}|+|P_{2}|+\dots+|P_{\frac{n}{2}}|\right)+\left(|P_{1}\cap P_{2}|+(|P_{1}\cap P_{3}|+\dots\right)-\dots$$
But for any $P_{k}$; $|P_{k}|=f(n-2)$ therefore, $|P_{1}|=|P_{2}|=\dots=|P_{\frac{n}{2}}|$and in general, given any $k$ where $1\le k\le \frac{n}{2}$, then $|P_{1}\cap P_{2}\cap\dots\cap P_{k}|=f(n-2k)-\dots$
So the number of sets not containing any of the original pair is:
$$f(n)-\left(f(n-2)+f(n-2)+\dots\right)+\left(f(n-4)+f(n-4)+\dots\right)-\dots$$
which equals:
$$f(n)-{\frac{n}{2}\choose 1}f(n-2)+{\frac{n}{2}\choose 2}f(n-4)-\dots$$
So in the case where $n=8$
$$f(8)-4f(6)+6f(4)-4f(2)+1f(0)=105-60+18-4+1=60$$
Calculate $1$ minus the probability of the complementary event:
The number of ways to choose $4$ out of $24$ shoes is:
- Choose the $1$st shoe out of $24$ shoes
- Choose the $2$nd shoe out of $23$ shoes
- Choose the $3$rd shoe out of $22$ shoes
- Choose the $4$th shoe out of $21$ shoes
The number of ways to choose $4$ out of $24$ shoes with no pairs is:
- Choose the $1$st shoe out of $24$ shoes
- Choose the $2$nd shoe out of $22$ shoes
- Choose the $3$rd shoe out of $20$ shoes
- Choose the $4$th shoe out of $18$ shoes
So the probability of choosing $4$ out of $24$ shoes with at least one pair is:
$$1-\frac{24\cdot22\cdot20\cdot18}{24\cdot23\cdot22\cdot21}$$
Please note that I've essentially taken into account the order of the shoes.
If I chose not to take it into account, then I would need to divide each result by $4!$.
But since this factor appears in both the numerator and the denominator, I can ignore it.
Best Answer
An example should make it clear:
Say $n=2$. The $2n$ things are $A,B,C,D$. For the first case, you get $6$ ways. These are
$AB,CD$
$AC,BD$
$AD,BC$
and
$CD,AB$
$BD,AC$
$BC,AD$. If you increase $n$, (for $n=3$, it's $90$ ways) you will observe that this method permutes the group of pairs, i.e, it counts $AB,CD$ and $CD,AB$ as different cases. However, it counts $AB,DC$ and $AB,CD$ as the same.
In the second case, you get $12$ cases. They are
$AC,BD$
$AD,BC$
$AB,CD$
$AD,CB$
$BA,CD$
$BD,CA$
$AC,DB$
$AB,DC$
$BA,DC$
$BC,DA$
$CB,DA$
$CA,DB$. If you increase $n$ (for $n=3$ there are $120$ ways) you will observe that this method does not permute the group pairs, i.e $AD,BC$ and $BC,AD$ are the same, but it counts $BC,AD$ and $BC,DA$ as different.
Now, can you see which formula is appropriate for you? Ordered pair means $AB,CD$ and $BA,DC$ are different. Your question has no mention of the order of the pairs, meaning $AB,CD$ and $CD,AB$ are same.
We can go from the formula of method 1 to that of method 2: