6.5: Counting Subsets

How many $k$-element subsets of an $n$-element set are there? This question arises all the time in various guises:

• In how many ways can I select 5 books from my collection of 100 to bring on vacation?
• How many different 13-card bridge hands can be dealt from a 52-card deck?
• In how many ways can I select 5 toppings for my pizza if there are 14 available toppings?

This number comes up so often that there is a special notation for it:

$$\nonumber {n \choose k} ::= \text{the number of } k \text{-element subsets of an } n \text{-element set.}$$

The expression ${n \choose k}$ is read "$n$ choose $k$." Now we can immediately express the answers to all three questions above:

I can select 5 books from 100 in ${100 \choose 5}$ ways.

There are ${52 \choose 13}$ different bridge hands.

There are ${14 \choose 5}$ different 5-topping pizzas, if 14 toppings are available.

The Subset Rule

We can derive a simple formula for the $n$ choose $k$ number using the Division Rule. We do this by mapping any permutation of an $n$-element set $\{a_1, \ldots, a_n\}$ into a $k$-element subset simply by taking the first k elements of the permutation. That is, the permutation $a_1 a_2\ldots a_n$ will map to the set $\{a_1, a_2, \ldots, a_n\}$.

Notice that any other permutation with the same first $k$ elements $a_1, \ldots, a_n$ in any order and the same remaining elements $n - k$ elements in any order will also map to this set. What’s more, a permutation can only map to $\{a_1, a_2, \ldots, a_n\}$ if its first $k$ elements are the elements $a_1, \ldots, a_n$ in some order. Since there are $k!$ possible permutations of the first $k$ elements and $(n-k)!$ permutations of the remaining elements, we conclude from the Product Rule that exactly $k!(n-k)!$ permutations of the $n$-element set map to the particular subset, $S$. In other words, the mapping from permutations to $k$-element subsets is $k!(n-k)!$-to-1.

But we know there are $n!$ permutations of an $n$-element set, so by the Division Rule, we conclude that

$$\nonumber n! = k! (n-k)! {n \choose k}$$

which proves:

Rule 14.5.1 (Subset Rule). The number of $k$-element subsets of an $n$-element set is

$$\nonumber {n \choose k} = \dfrac{n!}{k!(n-k)!}.$$

Notice that this works even for 0-element subsets: $n! / 0!n! = 1$. Here we use the fact that $0!$ is a product of 0 terms, which by convention² equals 1.

Bit Sequences

How many $n$-bit sequences contain exactly $k$ ones? We’ve already seen the straightforward bijection between subsets of an n-element set and $n$-bit sequences. For example, here is a 3-element subset of $\{x_1, x_2, \ldots, x_8\}$ and the associated 8-bit sequence:

$$\nonumber \begin{array}{l} \{x_1, \quad x_4, x_5 \quad \quad\} \\ (1, 0, 0, 1, 1, 0, 0, 0) \end{array}$$

Notice that this sequence has exactly 3 ones, each corresponding to an element of the 3-element subset. More generally, the $n$-bit sequences corresponding to a $k$-element subset will have exactly $k$ ones. So by the Bijection Rule,

Corollary 14.5.2. The number of $n$-bit sequences with exactly $k$ ones is ${n \choose k}$.

Also, the bijection between selections of flavored donuts and bit sequences of Lemma 14.1.1 now implies,

Corollary 14.5.3. The number of ways to select $n$ donuts when $k$ flavors are available is

$$\nonumber {n + (k - 1) \choose n}.$$

²We don’t use it here, but a sum of zero terms equals 0.