Amount of all subsets of size $n$ in a set with $e$ elements

Question

How do I find the amount of subsets that have n elements in a set with e elements?

For example, if you had a set with 5 elements, and wanted all subsets with 3 elements, you would have 10 subsets.

Answer 1

What you are looking for are binomial coefficients. In your case, the quantity you want is $\binom{e}{n}$.

Using induction, you will find that $\binom{e}{n}=\frac{e!}{n!(e-n)!}$.

If you did not have previous knowledge of binomial coefficients, here is how you might find those values:

• you choose a first element (you have $e$ choices), $e-1$ elements remain

• you choose a second element (you have $e-1$ choices), $e-2$ remain

• you go on until you have chosen $n$ elements, you had $e\times (e-1) \times .... \times (e-n+1) = \frac{e!}{(e-n)!}$ ways of doing that

• what you now have is an ordered collection of elements, but you only want a subset of your initial set, that is, an unordered collection. To switch between the two, you must find how many ways you have to order the $n$ elements you extracted. That number is $n!$.

So in the end, you indeed have $\frac{e!}{n!(e-n)!}$ ways of extracting your subset.

Answer 2

The number of sets of size $n$ we can construct from a set of size $e$ is $\binom{e}{n}$ where $$ \binom{e}{n} = \frac{e!}{n!(e - n)!} = \frac{e \times (e-1) \times \cdots \times (e-n+1)}{n \times (n-1) \times \cdots \times 2 \times 1}$$ One way to prove this is to first consider choosing ordered lists of $n$ distinct elements from $e$. There are $e$ ways to choose the first element, then $e - 1$ ways to choose the second element, then $e - 2$ ways to choose the second element, and so on. Therefore there are $e \times (e - 1) \times \cdots \times (e - n + 1) = \frac{e!}{(e - n)!}$ ways to choose a list of $n$ distinct elements from a set of size $e$.

Then to get the number of sets, note every set of $n$ elements can be ordered in $n!$ different ways. So by counting ordered lists of distinct elements we overcount by a factor of $n!$, hence we divide by $n!$ to compensate. This gives the formula at the start.