2.3: Combinations

To motivate the topic of this section, we consider another variant on the officer election problem from Example 2.7. Suppose that instead of electing students to specific offices, the class is to elect an executive council of four students from the pool of 80 students. Each position on the executive council is equal, so there would be no difference between Alice winning the “first” seat on the executive council and her winning the “fourth” seat. In other words, we just want to pick four of the 80 students without any regard to order. We'll return to this question after introducing our next concept.

Let \(X\) be a finite set and let \(k\) be an integer with \(0 \leq k \leq |X|\). Then a \(k\)-element subset of \(X\) is also called a combination of size \(k\). When \(|X| = n\), the number of \(k\)-element subsets of \(X\) is denoted \(\binom{n}{k}\). Numbers of the form \(\binom{n}{k}\) are called binomial coefficients, and many combinatorists read \(\binom{n}{k}\) as “\(n\) choose \(k\).” When we need an in-line version, the preferred notation is \(C(n,k)\). Also, the quantity \(C(n,k)\) is referred to as the number of combinations of \(n\) things, taken \(k\) at a time.

Bob notes that with this notation, the number of ways a four-member executive council can be elected from the 80 interested students is \(C(80,4)\). However, he's puzzled about how to compute the value of \(C(80,4)\). Alice points out that it must be less than \(P(80,4)\), since each executive council could be turned into \(4!\) different slates of officers. Carlos agrees and says that Alice has really hit upon the key idea in finding a formula to compute \(C(n,k)\) in general.

Proposition 2.9

If \(n\) and \(k\) are integers with \(0 \leq k \leq n\), then

\(\dbinom{n}{k} = C(n,k) = \frac{P(n,k)}{k!} = \frac{n!}{k!(n-k)!}\)

Proof

If \(X\) is an \(n\)-element set, then \(P(n,k)\) counts the number of \(X\)-permutations of length \(k\). Each of the \(C(n,k)\) \(k\)-element subsets of \(X\) can be turned into \(k!\) permutations, and this accounts for each permutation exactly once. Therefore, \(k!C(n,k)=P(n,k)\) and dividing by \(k!\) gives the formula for the number of \(k\)-element subsets.

Using Proposition 2.9, we can now determine that \(C(80,4)=1581580\) is the number of ways a four-member executive council could be elected from the 80 interested students.

Our argument above illustrates a common combinatorial counting strategy. We counted one thing and determined that the objects we wanted to count were overcounted the same number of times each, so we divided by that number (\(k!\) in this case).

The following result is tantamount to saying that choosing elements to belong to a set (the executive council election winners) is the same as choosing those elements which are to be denied membership (the election losers).

Proposition 2.10

For all integers \(n\) and \(k\) with \(0 \leq k \leq n\),

\(\dbinom{n}{k} = \dbinom{n}{n-k}\)

Example 2.11

A Southern restaurant lists 21 items in the “vegetable” category of its menu. (Like any good Southern restaurant, macaroni and cheese is one of the vegetable options.) They sell a vegetable plate which gives the customer four different vegetables from the menu. Since there is no importance to the order the vegetables are placed on the plate, there are \(C(21,4)=5985\) different ways for a customer to order a vegetable plate at the restaurant.

Our next example introduces an important correspondence between sets and bit strings that we will repeatedly exploit in this text.

Example 2.12

Let \(n\) be a positive integer and let \(X\) be an \(n\)-element set. Then there is a natural one-to-one correspondence between subsets of \(X\) and bit strings of length \(n\). To be precise, let \(X = \{x_1,x_2,...,x_n\}\). Then a subset \(A \subseteq X\) corresponds to the string \(s\) where \(s(i) = 1\) if and only if \(i \in A\). For example, if \(X = \{a,b,c,d,e,f,g,h\}\), then the subset \(\{b,c,g\}\) corresponds to the bit string \(01100010\). There are \(C(8,3) = 56\) bit strings of length eight with precisely three 1's. Thinking about this correspondence, what is the total number of subsets of an \(n\)-element set?