Selections and Binomial Coefficients

Section 4.4 Selections and Binomial Coefficients

In the previous sections of this chapter, we’ve learned how to count the number of possible outcomes to several types of processes. We began with simple, atomic processes like the roll of a die, the flip of a coin, or the selection of an entree off of a menu at a restaurant. From there, we encountered the Fundamental Principle of Counting, which allowed us to count the number of outcomes from more complex processes. These more complex processes consisted of several atomic processes, and we multiplied the number of ways to complete each subprocess together in order to find the total number of ways to complete the overall process. The most recent section showed us how to count the number of arrangements (or orderings) of a set of objects from a, perhaps larger, collection. In this section, we’ll learn how to count the number of possible selections of a set of objects from a, perhaps larger, collection but where the order of selection does not matter.

Subsection 4.4.1 Motivation

Some of the questions you answered in the last section asked about selecting individuals from a group to fill leadership roles in that group. What if, rather than selecting individuals for distinct roles (President, Vice President, etc.), we were simply building a leadership council where all selected individuals had identical roles and responsibilities. In this case, our tools for counting permutations no longer apply because being chosen first no longer corresponds to being "President", and being second no longer corresponds to being "Vice President".

Consider the following example which illustrates the overcounting associated with using permutations in these scenarios and also introduces a new counting method which removes the overcounting.

Example 4.4.1. Choosing a Governing Council.

Your local Computing Club has a membership consisting of 35 individual members. The club is choosing a governing council which will serve in a leadership capacity for the club. All members voted to the leadership council will have identical roles and responsibilities. In how many ways can a leadership council of five (5) club members be chosen?

Answer.

Your first instinct may be to use the approach we learned in the previous section. We’ll calculate the number of permutations of 5 elements from a collection of 35 total elements. In this case, we would estimate

\begin{gather*} _{35}P_{5} = \frac{35!}{\left(35 - 5\right)!} = 35\cdot\left(34\right)\cdot\left(33\right)\cdot\left(32\right)\cdot\left(31\right) = 38,955,840 \end{gather*}

distinct governing councils. The problem with this approach, however, is that it counts each collection of five people multiple times. For convenience, let’s say we have a governing council consisting of Jim, Sarah, Megan, Steve, and Melissa. In the calculation above, we count the governing council consisting of Melissa, Sarah, Steve, Jim, and Megan as a distinct governing council but, given the way that the governing council will function, these are identical councils.

In order to remove the overcounting, we’ll need to determine how many times each collection of five individuals is counted. Recognizing that this collection will be counted once for each ordering of the five selected individuals, we know that the collection will be counted \(_{5}P_{5} = 5\cdot\left(4\right)\cdot\left(3\right)\cdot\left(2\right)\cdot\left(1\right) = 120\) times. Since each distinct governing council is counted 120 times, we’ll take the overestimate of 38,955,840 and divide it by 120 to obtain the true number of unique governing councils. That is, there are \(\frac{38,955,840}{120} = \boxed{~324,632~}\) distinct governing councils that cound be created from the 35 person membership.

Subsection 4.4.2 Formalizing a Method

In the solution to the example above, we reasoned a method that would remove the overcounting and leave us with only the distinct selected governing councils. As with the other tools for counting we’ve encountered in this chapter, such a technique is so widely applicable that it is given a name.

Definition 4.4.2. Combinations.

The number of ways to choose a subset of size \(k\) from a collection of \(n\) distinct objects, where the order of selection does not matter is given by \(\frac{n!}{k!\left(n - k\right)!}\text{.}\) The formula above is sometimes referred to as counting the number of combinations of \(k\) items from a collection of \(n\text{,}\) and can be denoted as follows:

\begin{gather*} _{n}C_{k} = \binom{n}{k} = \frac{n!}{k!\left(n-k\right)!} \end{gather*}

The notations \(_{n}C_{k}\) and \(\choose{n}{k}\) are interchangeable and both are read "\(n\) choose \(k\)".

As one additional note, you might find resources referring to the quantity \(\choose{n}{k}\) as a binomial coefficient. This is because evaluating \(\choose{n}{k}\) allows you to obtain the coefficient of the \(x^ky^{n - k}\) term of \(\left(x + y\right)^n\text{.}\)

Let’s do one more example before you have a chance to practice on some embedded exercises. ...Exercise to be added...

Example 4.4.3. Inclusion in an Article.

A showcase was held for course projects and 17 students presented on their individual projects. A reporter from the school newspaper was present and plans to write an article highlighting four projects. In how many ways can the reporter select the four projects for inclusion in her write-up?

Answer.

Notice that the reporter is just selecting the projects for inclusion in her article. There is no importance assigned to the order in which she makes those selections. For this reason, we’ll use a combination, as described above. We have 17 student projects available and need to choose four for inclusion in the article.

\begin{align*} \binom{17}{4} &= \frac{17!}{4!\cdot13!}\\ &= \frac{17\cdot\left(16\right)\cdot\left(15\right)\cdot\left(14\right)}{4\cdot\left(3\right)\cdot\left(2\right)\cdot\left(1\right)}\\ &= \boxed{~2,380~} \end{align*}

There are 2,380 different combinations of student projects that the reporter could choose to write about in her article on the showcase.

Now, let’s move to the next section, where you’ll

Subsection 4.4.3 Examples to Try

In the exercises that follow, apply what you’ve learned over these last three sections. Be careful, as not every part of every question involves the techniques introduced here. You’ll need to identify opportunities to make use of basic counting techniques, the Fundamental Principle of Counting, Permutations, and Combinations.

Checkpoint 4.4.4. Organizing Bookshelves.

Checkpoint 4.4.5. Golfing Foursomes.

Checkpoint 4.4.6. Board of Directors.

Checkpoint 4.4.7. Pizza Menu.

Checkpoint 4.4.8. Drawing Quadrilaterals.

Checkpoint 4.4.9. Drawing Triangles.

Checkpoint 4.4.10. Arranging Letters.

Checkpoint 4.4.11. School Committee.

In this section you learned, and practiced with, another new tool for counting. In particular, the technique introduced here extended your ability to count the number of selections of a set of \(k\) items from a collection of \(n\text{,}\) where the order of selection did not matter. At the end of the section, you practiced with several examples that required you to idnetify whether to utilize permutations, combinations, or more basic counting techniques and also whether to apply the Fundamental Principle of Counting or not.

In the next section, we’ll connect our counting work back to computing. In particular, we’ll consider how we can count the number of operations being done in a worst-case application of a computer algorithm. Doing this counting allows us to describe the run-time complexity of the algorithm. Run-time complexity helps us understand how an algorithm will scale with larger and larger input arrays.

Prev Top Next