Combinations

To motivate the topic of this section, we consider another variant on the officer election problem from . 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\le k\le |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}\).\(\binom{n}{k}\)binomial coefficient 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)\)\(C(n,k)\)binomial coefficient (inline). 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.

Using , 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).

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.