Krdytkyu

There are $12$ pairs of shoes in a cupboard. $4$ are drawn at random. What is the probability that there is at least one pair?

My first attempt: If we chose a pair at first and then draw any two at random from the rest, then there will be at least one pair.
We can choose one pair in ${12}choose 4$ ways and chose any $2$ from the rest in ${22}choose 2$ ways.
Therefore, the required probability= $frac{{12choose 4} times {22choose 2}}{{24choose 4}}$ = $frac{6}{23} =frac{42}{161}$

But the given answer is $frac{41}{161}$.

Another attempt: Each of the 4 shoes we choose, will come from one of the pairs. We can choose the four pairs in ${12choose 4}$ ways and can select a shoe from each of the pairs in $2$ ways so that no pair is obtained. Therefore, required probability =$1-$ $frac{{12choose 4} times 2^4}{{24choose 4}}$ = $frac{41}{161}$

What is wrong with the first attempt?

Just to build on Henry's answer, suppose we put the pairs of shoes in order, 1 through 12. By your method, you are over counting picking pair 1 and another pair 11 times. Similarly, you are over counting picking pair 2 with another pair (other than pair 1) 10 times. Continuing on, you are over counting by precisely 11th triangular number, $T_{11} = 66$. Correcting for this,
$$
frac{12cdot {22 choose 2}-66}{24choose 4} = frac{41}{161}
$$
as desired.

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{24cdot22cdot20cdot18}{24cdot23cdot22cdot21}$$

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.

Your first method may double-count the possibility of getting two pairs: when you "chose any $2$ from the rest in ${22 choose 2}$ ways", you may be choosing another pair and these two pairs are also counted when chosen in the other order.

In your second method of looking at $1-$ the probability of choosing from different pairs, a similar method is to say that each time you choose a shoe its pair becomes undesirable, making the result $$1-frac{24}{24}times frac{22}{23}times frac{20}{22}times frac{18}{21} =frac{41}{161}.$$

This might be a bit late.

I was reading Feller's vol 1 chp 4 and got into this question from a very similar exercise.

http://www.amazon.com/Introduction-Probability-Theory-Applications-Edition/dp/0471257087

The ways you can do it is of course various, and easiest way to think is to use

1 - Prob(0 pairs selected)

and this is just

$$1 - frac{{12choose 4} times 2^4} {{24 choose 4}} $$

The other way you are considering, of course is correct. This is from inclusion exclusion principle.

https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle

The way you calculation is done by:

$$P_1 = S_1 - S_2 + S_3 + - ldots $$

where $S_1 = sum_{i=0}^n p_i$, $S_2 = sum_{i,j=0}^n p_{ij}, ldots$ and $p_i = P(A_i)$, $p_{ij} = P(A_iA_j),ldots$

So, in this problem you are looking at:$S_1 = sum_{}p_i$ where $$p_i = frac{22choose 2}{24choose4}$$ because you are considering 2 slots are already picked, and the rest can go anywhere in the 22 shoes.

And this has ${12choose 1}$ number of ways happening for your first 2 slots.

Now consider $p_2$. This is calculated as

$$p_2 = frac{20choose 0}{24choose4} $$

This is because, once you set 2 pairs of shoes, you are left with 0 to pick from the rest 20.

And there are ${12choose2}$ in summation for $p_2$

In summary
$$P_1 = S_1 - S_2 = sum{}p_i - sum{}p_{ij}=frac{{12choose1}times{22choose2}-{12choose2}times{20choose0}}{24choose4}$$

In your first counting method you have two counting stages. In the first one you have $12$ different possible results: ${P_1, P_2,ldots,P_{12}}$, where $P_i$ is a particular pair. In the second stage you would have $binom{22}{2}$ results for each result or pair of your first stage. That gives you a total of $12binom{22}{2}$ possible results. Now, let's take a loot a two different results of the first stage, say $P_1$ and $P_9$. For $P_1$ in the first stage, is possible to have $P_9$ as a result in the second stage, and for $P_9$ in the first stage, it is possible to $P_1$ in the second stage, and since the final result $P_1P_9$ is the same as $P_9P_1$, you are effectively counting two times the same result.

To select a pair, the order is irrelevant.
1. Select one shoe
2. Select one shoe - chance this is a pair of first = 1/23 = .04
3. Select one shoe - chance this is a pair of first = 1/22 or chance this is pair of second = 1/21 = 1/22+1/21 = .09
4. Select one shoe - chance this is a pair of first = 1/21 or of second = 1/20, or of third = 1/19 = 1/21+1/20+1/19 = .15
After four selections, probability is .04+.09+.15=.28