Counting Principles (D3)

Section 3.3 Counting Principles (D3)

In this section, we explore counting principles for ordered and unordered selection.

Subsection 3.3.1 Ordered Counting

Exploration 3.3.1. Breakfast Choices.

Suppose you were eating breakfast, and you could choose from eggs, sausage or pancakes to eat, and coffee and juice to drink.

(a)

List all of the possible food-beverage choices you could make. (Assume you can't skip either, and can only have one food idea and one beverage.)

(b)

How many different choices could you make?

Activity 3.3.2.

One of the most useful counting tools in mathematics is the multiplication principle. This principle is used when all the items to be counted come from a sequence of choices. If each item is made by making a choice from \(a\) things, then a choice from \(b\) things, then a choice from \(c\) things, and so on, then the total number of items is given by the product:

\begin{equation*} a\cdot b\cdot c\cdot \cdots \end{equation*}

(a)

Suppose for a fancy dinner you are given four options as an appetizer, six options as an entree, three options as a beverage, and two options as a dessert. How many different dinners are possible?

(b)

Suppose you could choose an appetizer or a dessert, but not both. How many different dinners are possible in that scenario?

(c)

What if instead you consider the choice to skip any part of the meal, holding the appetizer, entree, beverage, and/or dessert. How many dinners are possible in that case?

(d)

What is the size of the sample space for the experiment of rolling a six sided die, then flipping a coin, then drawing a card from a shuffled 52-card deck?

Activity 3.3.3. Letter Arrangements.

Suppose you had the five tiles with A, B, C, D, E written on them.

(a)

How many ways can you select two tiles and put them in a row? (Use the multiplication principle, how many choices do you have for the first tile? The second?)

(b)

How many ways can you select three tiles and put them in a row?

(c)

How many ways can you select four tiles and put them in a row?

(d)

How many ways can you select all five tiles and put them in a row?

(e)

Run the following code to display all the possible ways to select k=2 tiles out of A, B, C, D, E and arrange them:

How does this compare to what you found in (a)?

(f)

Adjust the above code to let k be 3, 4 and 5. How does the outputs compare to what you found in (b), (c), and (d)?

Definition 3.3.1.

A permutation is an ordered arrangement of objects. In partcular, a \(r\) permutation on an \(n\) element set is a selection of \(r \) objects from this set and arranged.

The number of \(r\) permutations on an \(n\) element set would be computed

\begin{equation*} P(n,r)=\overbrace{n\cdot (n-1)\cdots(n-r+1)}^r. \end{equation*}

Remark 3.3.2.

We note that \(n!\) denotes \(n!=\overbrace{n\cdot (n-1)\cdots 1}^{n}\) where we let \(0!=1\text{.}\)

Notice that

\begin{equation*} P(n,n)=\overbrace{n\cdot (n-1)\cdots 1}^{n}=n!. \end{equation*}

Also notice that more generally

\begin{equation*} P(n,r)=\overbrace{n\cdot (n-1)\cdots (n-r+1)}^{r}=\frac{n\cdot (n-1)\cdots (n-r+1)\cdot \color{blue}{(n-r)\cdots 1}}{\color{blue}{(n-r)\cdots 1}}=\frac{n!}{(n-r)!}. \end{equation*}

Activity 3.3.4. Permutations.

(a)

If a driver had to make 6 deliveries, how many ways could they pick an order to do so?

(b)

If a class of 30 had to select 4 students to be class president, vice president, secretary and treasurer, how many ways could you do this?

(c)

If you have 10 books, how many ways can you select 6 of them to arrange on a shelf?

Subsection 3.3.2 Unordered Counting

Exploration 3.3.5. Combinations.

Suppose you had 4 tiles with letters W, X Y and Z written on them. We know from Definition 3.3.1 that there the number of ways to select 3 out of these 4 tiles and arrange them is \(P(4,3)=\frac{4!}{(4-3)!}=24\text{.}\)

(a)

Write out all 24 arrangements, grouping together the arrangemnets that use the same letters. For example WXY and WYX would be in the same group along with other possible arrangements of the same letters.

(b)

How many different groups do you have?

(c)

How many arrangements are in each group?

(d)

How many ways could we select 3 out of 4 tiles if we were unconcerned about the order in which we selected them?

(e)

Run the following code to display all the possible ways to select k=3 tiles out of W, X, Y, Z without arranging them:

How does this compare to what you've done above?

Definition 3.3.3. Combination.

Given \(n\) objects, the number of ways to select \(k\) of them without order, also called a combination is:

\begin{equation*} C(n,k)=\frac{P(n,k)}{k!}=\frac{n!}{k!(n-k)!}. \end{equation*}

This is also commonly denoted \({n\choose k}\text{,}\) which we will avoid to prevent confusion with fractions.

Activity 3.3.6. Combinations.

(a)

If a class of 30 had to select 4 students to be class representatives, how many ways could you do this?

(b)

If you have 10 books, how many ways can you select 6 of them to give away?

(c)

If you have 10 books, how many ways can you select 4 of them to keep?

(d)

How do the questions (b) and (c), and their answers compare?

Remark 3.3.4.

Here are some useful facts about combinations.

\(C(n,n)=1\text{.}\) There is only one way to pick \(n\) of \(n\) objects. Pick them all.
\(C(n,r)=C(n,n-r)\text{.}\) Picking \(r\) objects is the same as selecting \(n-r\) objects to not pick.
\(C(n,0)=1\text{.}\) Combine the above facts. Alternatively, the only selection of no objects is the empty selection.

Activity 3.3.7. Permutation or Combination.

For each of the following determine if the problem describes a permutation (order matters) or a combination (order doesn't matter) and find the answer.

(a)

Out of 20 shirts, how many can I pick to wear for each day of the week Sunday through Saturday?

(b)

How many ways can I pick 3 out of 25 ice cream flavors to buy?

(c)

How many 5 card hands out of a 52 card deck are there?

(d)

If I deal 5 cards from a 52 card deck, one to each of 5 people, how many ways could this happen?