The Basic Counting Principles

Section 2.1 The Basic Counting Principles

Objectives

State the Sum Rule and the Product Rule, and explain how the Product Rule derives from the Sum Rule.
Given a counting problem, partition the objects being counted into subsets that facilitate the use of the Sum Rule.
Given a counting problem, describe the steps necessary to form the object or scenario being counted, and apply the Product Rule.

Video: Introduction to Counting

In this section (and chapter) we will develop techniques for counting! When you hear the word count you probably think about listing or enumerating objects. For example:

How many siblings do you have?
Count the number of students enrolled in MAT202 this term.
How many buildings are there on the UTM campus?

Often we are also interested in counting the number of different ways some given scenario or condition can happen. For instance, consider the following example:

Example 2.1.1. First Counting Example.

Three friends Ana, Mark, and Olivia are working together on a group project and they are trying to delegate the writing among themselves based on sections: introduction, literature review, and conclusion (everyone will work on the analysis).

How many possible ways can the tasks be assigned to the three friends?

Solution

Let's abbreviate their names as A, M, and O. We can just list all possibilities to find that there are 6 ways:

Introduction	A	A	M	M	O	O
Lit Review	M	O	A	O	A	M
Conclusion	O	M	O	A	M	A

Example 2.1.1 is small enough that we can count the number of possibilities by listing them. Can you do the same for the following exercise? What do you notice about your answer to part (a)?

Checkpoint 2.1.2. Concert Seating.

Three friends (Mina, Lisa, and Wendy) were able to get three seats together in a row at a Coldplay concert.

How many ways can they choose to sit?
How many ways can they sit if Lisa insists on sitting in the middle?

Answer

a. 6; b. 2

The techniques we will develop will help us count when the number of possibilities is too large that we can't simply list them all! For instance, the next example is one where listing all possibilities seems like a bad idea.

Example 2.1.3. Dog Adoption.

There are 10 dogs up for adoption at your local animal shelter. You and 9 other friends decide to adopt one dog each. How many ways can you assign dogs to people?

Solution (but not really) If we first fix you and your friends in some specified order (human 1, human 2, human 3, and so on) and name the dogs A, B, C, up to J, then each adoption arrangement corresponds to an ordering of the letters A to J in a list, where the position of each letter corresponds to the person adopting that dog.

For example, the arrangement

J	I	H	G	F	E	D	C	B	A
\(\uparrow\)	\(\uparrow\)	\(\uparrow\)	\(\uparrow\)	\(\uparrow\)	\(\uparrow\)	\(\uparrow\)	\(\uparrow\)	\(\uparrow\)	\(\uparrow\)
1	2	3	4	5	6	7	8	9	10

means that dog J is assigned to human 1, dog I is assigned to human 2, and so on, while the arrangement DJABECIHGF means dog D is assigned to human 1, dog J to human 2, and so on…

You should quickly realize there are too many combinations to list!

When possible, it is a good idea to exploit the structure of what we are counting! Two rules for counting will help us get started: the Sum Rule and the Product Rule. Think about the following exercises:

Checkpoint 2.1.4. Socks!

You plan to move to a new apartment by the end of the month, and while packing your clothes, you note that you have 3 pairs of black socks, 4 pairs of white socks, and 2 pairs of blue socks.

How many pairs of socks do you have in total?

Answer

Checkpoint 2.1.5. Exam Counts.

After an in-person term test or final exam, the course instructor and TAs get together and first verify that the number of papers handed in matches the number of students who wrote the test.

Five piles of test papers on a brown desk.

Can you think of an efficient way to count the papers?

Hint

You wouldn't just count them one by one…

In Checkpoint 2.1.4 the problem of counting the total number of pairs of socks had a straightforward solution. Since the socks were already separated by colour, and you knew how many of each colour you had, you just had to add the number of pairs for each colour to get the total.

For the test papers in Checkpoint 2.1.5 there are certainly multiple ways to do this. One method that TAs use is to form piles of ten, and count how many piles are produced. This is actually more similar to the socks example than you might think. Separating the huge pile of papers into groups of 10 has the same goal as separating socks by colour: one just has to add the numbers in each pile together in the end (which, if all piles have 10, is an easy calculation).

This is the Sum Rule in action.

Video: The Sum Rule and Partitions

Definition 2.1.6. Partition.

Let \(A\) be a finite set. We say that \(B_1,B_2,\ldots,B_m\) form a partition of \(A\) if

\(B_i \cap B_j = \varnothing\) for all \(i \ne j\text{,}\) and
\(B_1 \cup B_2 \cup \cdots \cup B_m = A\text{.}\)

Principle 2.1.7. Sum Rule.

If \(B_1,B_2,\ldots,B_m\) form a partition of \(A\text{,}\) then

\begin{equation*} |A| = \sum_{i=1}^m |B_i| = |B_1| + |B_2| + \cdots + |B_m|\text{.} \end{equation*}

The Sum Rule essentially tells us that in order to count a set of objects, we can break these objects up into disjoint cases, count each case separately, then add them all together in the end. Sounds reasonable!

Checkpoint 2.1.8. Twitter Followers.

TJ is an avid Twitter user, where he manages the following accounts:

A personal account with 200 followers;
A K-pop stan Twitter account with 2500 followers;
A third account with 12000 followers that tweets a picture of a puppy every hour.

Can you determine the total number of unique followers TJ has? Explain whether or not the Sum Rule is applicable to this problem.

Hint

To apply the Sum Rule, one needs to have a partition.

When we need to count objects that are constructed by performing successive steps or operations that are independent, we use the Product Rule.

Video: The Product Rule

Principle 2.1.9. Product Rule.

If a certain operation takes \(k\) steps to accomplish, and if there are:

\(r_1\) ways of performing step 1,
\(r_2\) ways of performing step 2 (regardless of how step 1 was performed),
\(r_3\) ways of performing step 3 (regardless of how step 2 was performed),
and so on…

Then, there are

\begin{equation*} \prod_{i=1}^k r_i = r_1 \cdot r_2 \cdot \ldots \cdot r_k \end{equation*}

ways of performing steps 1 to \(k\text{.}\)

Checkpoint 2.1.10. Counting Outfits.

You are deciding what outfit to wear to your Zoom class today. You have been putting off doing laundry, so you only have 3 clean shirts and 3 clean pairs of pants. Also, you have 8 pairs of socks to choose from. How many different outfits can you wear to school today? (Assume you cannot go to school shirtless, but you can go pantless or barefoot—no one will see!)

Checkpoint 2.1.11. Proof of the Product Rule.

Use the Sum Rule to prove the Product Rule.

Hint 1

Induction on \(k\text{.}\)

Hint 2

Induction hypothesis: Assume the statement holds for all operations that take \(k-1\) steps to accomplish. Now consider an operation that takes \(k\) steps (\(r_1,r_2,\ldots,r_k\)) to accomplish. By the IH, there are

\begin{equation*} \prod_{i=1}^{k-1} r_i = r_1 \cdot r_2 \cdot \ldots \cdot r_{k-1} \end{equation*}

ways of performing steps 1 to \(k-1\text{.}\) Now take cases on the \(k\)th step.

Example 2.1.12. Multiple Choice Exam.

A multiple-choice exam has 20 questions and four choices for each question. How many possible combinations of responses are there?

Multiple-choice bubble sheet with five questions and four boxes each for choices A, B, C, D.

Solution

Answering the whole test takes 20 individual, independent steps: picking one answer to each question. If we assume each question needs to have one answer, then in the statement of the Product Rule, \(r_1 = 4\text{,}\) \(r_2 = 4\text{,}\) and so on until \(r_{20} = 4\text{,}\) giving a total of

\begin{equation*} \underbrace{4 \times 4 \times \cdots \times 4}_{\text{20 times}} = 4^{20}=1099511627776 \end{equation*}

possible answer combinations.

In other words, pure guessing as a strategy will on average result in a perfect score once every one trillion tries. In comparison, the odds of matching six numbers in Lotto 6/49 is much better: one in 14 million.

If we allow questions to be left unanswered, then there are \(5^{20}=95367431640625\text{,}\) around 96 trillion possible ways to answer the test.

Checkpoint 2.1.13. Concert Seating with \(n\) people.

Apply the Product Rule to answer (a) and (b) of Checkpoint 2.1.2, then generalize this method to count the number of ways to sit \(n\) people in a row of \(n\) seats.

Because the following operation frequently turns up in counting problems, we have a special name for it.

Definition 2.1.14. Factorial.

For integer \(n \geq 0\text{,}\) the factorial of \(n\text{,}\) denoted by \(n!\text{,}\) is

\begin{equation*} n! = \prod_{i=1}^n i = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 2 \cdot 1\text{.} \end{equation*}

By convention we define \(0! = 1\text{.}\)

Remark 2.1.15.

For problems where the answer involves a factorial, it is fine to leave the factorial in your answer without computing the actual value.

Example 2.1.16. Dog Adoption, again.

Example 2.1.3 had too many combinations to list, but using the Product Rule we see that there are a total of

\begin{equation*} 10! = 10 \times 9 \times 8 \times \cdots \times 1 = 3628800 \text{ combinations}\text{.} \end{equation*}

Checkpoint 2.1.17. Trip Planning.

Four friends (Erin, Jagmeet, Yves-François, and Annamie) are planning a trip to Ottawa, and they need to assign tasks (booking flights, booking hotel rooms, and making an itinerary) to three people. Erin cannot be trusted to make an itinerary; also, either Jagmeet or Annamie must book hotel rooms. How many ways can they assign tasks?

Think carefully about which counting principle(s) to apply here. Explain your method of calculation properly.

Hint

A diagram would be useful.

Answer

Solutions Solutions to Selected Checkpoints