Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this answer
Why should I divide by 4!? – Mistu4u Oct 1 '12 at 4:36

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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