I am just stuck with a problem and need your help. The question is:

A closet has 5 pairs of shoes. The number of ways in which 4 shoes can be chosen from it so that there will be no complete pair is a.80 b.160 c.200 d.none

I think the answer should be $\binom{10}{1}\cdot\binom{8}{1}\cdot\binom{6}{1}\cdot\binom{4}{1}$. But I seriously doubt this could be the answer. Please help me in solving this.


Hint: The four shoes must come from 4 different pairs.

For a specific set of 4 pairs, there are $2^4$ ways of choosing the shoes. There are 5 possible sets of 4 pairs. Hence there are $5*2^4$ ways in total.

Actually your idea is right, but you are counting the number of ordered sequences of four shoes. Divide by $4!$ and you get the answer you are looking for.

  • $\begingroup$ Why should I divide by 4!? $\endgroup$ – Mistu4u Oct 1 '12 at 4:36

We need to chose $4$ different color shoes from the five different pairs of shoes given. Therefore number of ways to select them is $\displaystyle \binom{5}{4}$. Now from a pair of two shoes we need to select only one shoe so that we don't get a complete pair of shoes in our four selected $4$ shoes. The number of ways to select them is $\displaystyle \binom{2}{1}$. We need to do this with $4$ different times Therefore their number of ways becomes $\displaystyle\binom{2}{1}^4$. Therefore the total number of ways to choose $4$ shoes will be $\displaystyle \binom{5}{4}\cdot\binom{2}{1}^4$ which is equal to $80$.


Since we have $5$ pairs of shoes, and we wish to choose $4$ shoes avoiding pairs of shoes, the answer is the number of independent $4$-sets of vertices of the graph:


I.e., it is the coefficient of $x^4$ in its independence polynomial.

We know that the independence polynomial of a disconnected graph is equal to the product of independence polynomials of its connected components. The independence polynomial of $K_2$ is $1+2x$, so the independence polynomial of the above graph is $$(1+2x)^5=32x^5+80x^4+80x^3+40x^2+10x+1.$$ Hence there are $80$ independent sets of size $4$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.