Pairs of shoes (combinatorics)

[ins-]

In a closet are put $n$ different pairs of shoes. In a random way are taken $2r$ shoes $(2r<n)$. Find the number of cases we have taken at least one pair of shoes (from the same kind).

[Gagarin1968]

I think we must start by calculating the number of cases when the selected shoes do not contain paired ones at all.

The pairs shown in our selection can be selected in $C_n^{2r}$ ways.

But from each selected pair we can choose both the right shoe and the left shoe. Or the whole pair. This we can do in $2^{2r}$ ways.

So we avoid a pair in our sample in $2^{2r}\cdot C_n^{2r}$ ways.

In total to choose $2r$ shoes among $n$ pairs we can in $C_{2n}^{2r}$ ways.

To sum up the required number of cases is $C_{2n}^{2r}-2^{2r}\cdot C_n^{2r}$

I suppose so.

[Gagarin1968]

I looked at this problem a second time, then a third ...
It seems to me that it is too simple for the olympiad. Standard combinatorial problem.
No?

[ins-]

I posted it as an olympiad problem, because it was given on a math olympiad (former second round, now first in the Bulgarian math olympiad). They have the same answer as your but I didn't undertstand the solution and tried to solve the problem in a different way.

What I did was - each different pair of shoes is an element of a set with $n$ elements. From the taken shoes is it is possible to have exactly $1$ pair of shoes (case $1$), exactly $2$ pairs of shoes (case $2$), ..., exactly $r$ pairs of shoes (case $r$). Summing the different cases gives $C_{n}^{1}+C_{n}^{2}+...+C_{n}^{r}$ as a final result.

Did I make a mistake? If no - is it possible the expression I found to be simplified further?

[nnosipov]

ins- в сообщении #1486544 писал(а):

is it possible the expression I found to be simplified further?

Yes, it is very easily. You may just use any computer algebra system (if you want to obtain the answer only and not anything else). The sums of binomial coefficients that you proposed can be evaluated by a standard algorithm.

[ins-]

I'm not sure if my answer is correct. I think in each of the cases I miss the fact that the remaining shoes are different and can be chosen in many different ways and a "corresponding sequences of different shoes" can be found. Because of this it is possible each of my combinations to be multiplied by another one. For example in the first case it is $C_n^1\cdot C_{n-1}^{2r-2}$. Is that correct?