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