# Counting the Number of Subsets of a Finite Set

Consider the finite $3$-element set $A = \{ x_1, x_2, x_3 \}$. Suppose that we want to determine the total number of distinct subsets that can be formed from $A$. It's not too difficult to list these sets, and it turns out that the subsets$\emptyset, \{ x_1 \}, \{ x_2 \}, \{ x_3 \}, \{ x_1, x_2 \}, \{ x_1, x_3 \}, \{ x_2, x_3 \}, \{ x_1, x_2, x_3 \}$ are the only subsets of $A$ and that there are exactly $8$ of them.

In general, it might be convenient to know the total number of distinct subsets that can be formed from a finite $n$-element set $A$ such as:

(1)The following theorem uses The Binomial Theorem to show us that for any finite $n$-element set there are exactly $2^n$ distinct subsets of $A$.

Theorem 1: If $A$ is a finite $n$-element then there are exactly $2^n$ distinct subsets of $A$. |

**Proof:**Let $A = \{ x_1, x_2, ..., x_n \}$ be an $n$-element set. Then the total number of subsets containing zero elements is $\binom{n}{0}$, the total number of subsets containing one element is $\binom{n}{1}$, …, and the total number of subsets containing $n$ elements is $\binom{n}{n}$. By the addition principle we see that:

- Recall that for all $x, y \in \mathbb{R}$ and $n \in \{ 0, 1, 2, ... \}$ we have that the binomial expansion of $(x + y)^n$ is given by the formula:

- Setting $x = y = 1$ will give us:

- Therefore we have that:

For example, consider the five element set $D = \{ v, w, x, y, z \}$. From Theorem 1 above we see that there are $2^5 = 32$ distinct subsets of $D$ (try to list them all).