# Thread: Combinatorics - choosing exactly k pairs from n

1. ## 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 $\displaystyle n$ pairs of shoes in the closet.
$\displaystyle 2m$ shoes are chosen from it randomly. ($\displaystyle m<n$)
find the probability to get exactly $\displaystyle k$ pairs.

so this is what I'm thinking:

first of all: $\displaystyle |\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 $\displaystyle k$ pairs out of $\displaystyle n$.

at first I thought it would be $\displaystyle \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 $\displaystyle \frac{\binom{n}{k}\binom{n-k}{2m-2k}2^{2m-2k}}{\binom{2n}{2m}}$
I just couldn't figure out why...

2. ## Re: Combinatorics - choosing exactly k pairs from n

Originally Posted by Stormey
There are $\displaystyle n$ pairs of shoes in the closet.
$\displaystyle 2m$ shoes are chosen from it randomly. ($\displaystyle m<n$)
find the probability to get exactly $\displaystyle k$ pairs.
*edit
btw, acoording to what I found somwehre online, the answer is $\displaystyle \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 $\displaystyle \frac{\binom{n}{k}\binom{n-k}{m-k}2^{m-k}}{\binom{2n}{2m}}$

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

Does that help?

3. ## Re: Combinatorics - choosing exactly k pairs from n

Originally Posted by Plato
Here are my reasons. Suppose we want to choose $\displaystyle J$ of those shoes so that none match (no pairs).
Clearly $\displaystyle J\le n$. There are $\displaystyle \binom{n}{J}$ ways to choose $\displaystyle J$ pairs from the $\displaystyle n$ pairs
From those $\displaystyle J$ pairs there are $\displaystyle 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 $\displaystyle \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.