# Combinatorics - choosing exactly k pairs from n

• November 18th 2013, 04:14 AM
Stormey
Combinatorics - choosing exactly k pairs from n
Hi.
I have the following combinatoric problem (well it's actually a probability problem that need to be resolved using combinatorics):

There are $n$ pairs of shoes in the closet.
$2m$ shoes are chosen from it randomly. ( $m)
find the probability to get exactly $k$ pairs.

so this is what I'm thinking:

first of all: $|\Omega |= \binom{2n}{2m}$ (the number of possibilities to choose 2m shoes from 2n).
but I just can't decide how many possibilities are there to choose exactly $k$ pairs out of $n$.

at first I thought it would be $\frac{\binom{n}{k}}{\binom{2n}{2m}}$, but that's not the right answer...
any help would be greatly appretiated.

*edit
btw, acoording to what I found somwehre online, the answer is $\frac{\binom{n}{k}\binom{n-k}{2m-2k}2^{2m-2k}}{\binom{2n}{2m}}$
I just couldn't figure out why...
• November 18th 2013, 06:46 AM
Plato
Re: Combinatorics - choosing exactly k pairs from n
Quote:

Originally Posted by Stormey
There are $n$ pairs of shoes in the closet.
$2m$ shoes are chosen from it randomly. ( $m)
find the probability to get exactly $k$ pairs.
*edit
btw, acoording to what I found somwehre online, the answer is $\frac{\binom{n}{k}\binom{n-k}{2m-2k}2^{2m-2k}}{\binom{2n}{2m}}$ I just couldn't figure out why...

I have a minor disagreement with the online answer you found.
I think it should be $\frac{\binom{n}{k}\binom{n-k}{m-k}2^{m-k}}{\binom{2n}{2m}}$

Here are my reasons. Suppose we want to choose $J$ of those shoes so that none match (no pairs).
Clearly $J\le n$. There are $\binom{n}{J}$ ways to choose $J$ pairs from the $n$ pairs
From those $J$ pairs there are $2^J$ ways to choose either the left or the right shoe from each pair.

Does that help?
• November 18th 2013, 11:49 AM
Stormey
Re: Combinatorics - choosing exactly k pairs from n
Quote:

Originally Posted by Plato
Here are my reasons. Suppose we want to choose $J$ of those shoes so that none match (no pairs).
Clearly $J\le n$. There are $\binom{n}{J}$ ways to choose $J$ pairs from the $n$ pairs
From those $J$ pairs there are $2^J$ ways to choose either the left or the right shoe from each pair.

Does that help?

Actually, that makes perfect sense to me, but I still don't see why is it $\frac{\binom{n}{k}\binom{n-k}{m-k}2^{m-k}}{\binom{2n}{2m}}$.

*edit
OK, now I see it.
I didn't notice that we actually choose m pairs of shoes, not just k.
Thank you very much my friend.