2. Counting: Arithmetic Techniques

This chapter was last updated on February 2, 2025.
Contents locked until 11:59 p.m. Pacific Standard Time on May 23, 2025.

You probably learned how to count objects one by one when you were a child. You may have counted up to 5 on the fingers on one hand, or up to 10 on the fingers of two hands, or up to 20 on fingers and toes - that is, you paired the objects (fingers and/or toes) with number names to create a one-to-one correspondence. You may have counted all the way up to 100.

However, many problems in computer science or mathematics require you to count the number of elements in sets that contain millions of elements, or billions of elements, or even more elements, so counting one by one is inefficient or impossible. Starting with this chapter, and continuing later in the Set Theory and Counting: Permutations and Combinations chapters, you will study ways to quickly and efficiently count the number of elements of any set no matter the size of the set.

Key terms and concepts covered in this chapter:

  • Counting arguments

    • Sum Rule

    • Product Rule

    • Division Rule (also called the Rule Of Quotient)

    • Subtraction Rule (also called the Principle of Inclusion-Exclusion for two sets)

  • The pigeonhole principle

2.1. Some Foundational Counting Principles

Each of the four arithmetic operations corresponds to a rule we can use to count quickly.

2.1.1. The Sum Rule

The sum rule, also called the addition principle or the rule of sum, describes the number of possible choices of one element from a union of two sets that share no common elements (Such sets are called disjoint sets ).

The Sum Rule

Suppose that we have a procedure that consists of completing one step, and that the step can be chosen from either a first set of j possible ways to complete the step or from a second set of k possible ways to complete the step, and that no way of completing the step is in both the first and second sets. Then there are \(j+k\) ways to complete the procedure.

This is called the sum rule for counting because it involves adding to find a total. The sum rule can also be extended to more than two sets, as long as every pair of the sets have no elements in common.

Example 1

A student in a Capstone course can choose a project from three different professors. The professors have 3, 7, and 4 possible projects, and no project is on more than one professor’s list. How many possible projects can the student choose?

Solution

The student can pick out a project by choosing from the first professor, the second professor, or the third professor. Since no project is on more than one list, the sum rules says that there are \(3 + 7 + 4 = 14\) projects to choose from.

set-of-playing-card_CROPPED
You Try

A card will be drawn from a standard 52-card deck.
How many ways can the card be an even number or a king?
Image credit: This is a cropped version of "Set Of Playing Card" . George Hodan has released this “Set Of Playing Card” image under Public Domain license (CC0 Public Domain) .

2.1.2. The Subtraction Rule

The subtraction rule describes the number of possible choices of one element from a union of two sets that do share one or more common elements.

The Subtraction Rule

Suppose that we have a procedure that consists of completing one step, and that the step can be chosen from either a first set of j possible ways to complete the step or from a second set of k possible ways to complete the step, but that there are m possible ways of completing the step that are in both the first and second sets. Then there are \(j+k-m\) ways to complete the procedure.

The subtraction rule is a special case of the inclusion-exclusion principle that involves only two sets. The inclusion-exclusion principle is discussed in more detail in the Set Theory and Proofs: Mathematical Induction chapters.

Example 2

In a group of students, 17 are enrolled in discrete mathematics, 13 are enrolled in probability, and 6 are enrolled in both discrete mathematics and probability.
How many students are in the group?

Solution

There are 17 students enrolled in discrete mathematics, but 6 of these students are enrolled in both discrete mathematics and probability. Likewise, there are 13 enrolled in probability, but 6 of these students are enrolled in both discrete mathematics and probability.
If we applied the addition rule by computing \(17+13 = 30\), this counts the 6 students who are enrolled in both discrete mathematics and probability twice, once as a student enrolled in discrete mathematics and then again as a student enrolled in probability. We can repair the count by subtracting 6 from the sum of 17 and 13; this will count each of the students exactly once. That is, the number of students in the group is \(17+13-6=24.\)
Alternative solution
First form three sets that have no students in common: Subtract 6 from each of 17 and 13 to find that there are \(17-6=11\) students in the set of students who are are enrolled in discrete mathematics but not probability, \(13-6=7\) students in the set of students who are enrolled in probability but not discrete mathematics, and 6 students in the set of students who are enrolled in both discrete mathematics and probability. Notice that the Sum Rule can be used because no student can be in two (or more) of the sets: There are \((17-6)+(13-6)+6 = 24\) students, which is the correct count.
Also note that \((17-6)+(13-6)+6 = 17+(-6)+13+(-6)+6 = 17 + 13 -6 =24,\) which is the computation used in first solution.

Example 3

A tech company has 200 applicants for a position. Of the applicants, 150 were computer science majors, 43 were business majors, and 25 were double majors in both computer science and business.
How many applicants did not major in either computer science or business?

Solution

By the subtraction rule, there are \(150 + 43 - 25 = 168\) applicants that majored in computer science or business (or both). The number of applicants who did not major in either computer science or business is \(200 - 168 = 32.\)

Video Example

The following video example features Dr. Joshua Roberts, Associate Professor of Mathematics at Georgia Gwinnett College.

Notice that Dr. Roberts uses a Venn diagram to represent the sets in this video. Venn diagrams are covered in the Set Theory chapter of the Remix.

2.1.3. The Product Rule

The product rule, also called the multiplication principle or the rule of product, describes the number of possible choices of two successive elements where the first element comes from one set and the second from another set (which could be the same set as the first set).

To find the total number of outcomes for two or more successive events where both events must occur, multiply the number of outcomes for each event together. For instance, if you want to find the number of outcomes possible when you roll a die and toss a coin, you could use the product rule. It is important to note that the events must be independent, meaning one doesn’t effect the other.

The Product Rule

Suppose that we have a procedure that consists of completing two steps, that there are k possible ways to complete the first step, and for each possible way of completing the first step, there are m possible ways to complete the second step. Then there are k⋅m ways to complete the procedure.

Example 4

Suppose there are 27 computers in a computer center and each computer has 15 ports. How many different ways are there to choose a specific port?

Solution

Choosing a port means you first choose a computer and then a port on that computer. Since there are 27 computers and 15 ways to choose a port on a computer, there are \((27)(15) = 405\) ways to choose a port.

You Try

How many functions are there from a set \(A\) with \(m\) elements to a set \(B\) with \(n\) elements?
Click on "Hint" to reveal the hidden text.

Hint
Try working out an example where \(m\) and \(n\) are small natural numbers. For example, how many functions are there from the set \(\{ 1, 2, 3, 4 \}\) to the set \(\{ \text{"red"},\,\text{"green"},\,\text{"blue"} \}\)?

Video Example

The following video example features Dr. Joshua Roberts, Associate Professor of Mathematics at Georgia Gwinnett College.

Example 5
Example 6

You can use more than one of the rules to solve a problem.

How many bitstrings of length four start with 1 or end with 00?

Solution

First, a bitstring of length four that starts with 1 will be of the form \(1~*~*~*\), where there are two choices for each \(*\), either 0 or 1. Use the product rule to compute that there are \((1)(2)(2)(2) = 2^3 = 8\) bitstrings of this form.

Secondly, a bitstring of length four that ends with 00 will be of the form \(*~*~0~0\), so there are \((2)(2)(1)(1) = 2^2 = 4\) bitstrings of this form.

Thirdly, a bitstring of length four that starts with 1 and ends with 00 will be of the form \(1~*~0~0\), so there are \((1)(2)(1)(1) = 2\) bitstrings of this form.

Now use the subtraction rule to compute the number of bitstrings of length four that start with 1 or end with 00 (or both): \(8 + 4 - 2 =10.\)

You Try

If a card is drawn from a standard 52-card deck, how many ways can the card be black or a face card (that is, either a Jack or a Queen or a King)?

2.1.4. The Division Rule

This rule is used when there are \(n\) ways to complete a procedure, but each of those ways is equivalent to \(d\) ways (including the way itself.) That is, every possible outcome of the procedure can be done in \(d\) different ways

The Division Rule

Suppose that we have a procedure that can be completed in n possible ways, but that for each way of completing the procedure there are d possible ways with the same outcome. Then there are \(\frac{n}{d}\) ways to complete the procedure.

The next example uses both the product and division rules.

DivisionRuleCircularTableImage
Example 7

Four students will sit around a circular table, but two seatings are considered "not different" whenever each student has the same left neighbor and right neighbor. How many different seatings are there?

Solution

First use the product rule to find that there are (4)(3)(2)(1) = 24 possible ways for the 4 students to sit (For example, there are 4 choices for the "North," then 3 choices remaining for the "East," then 2 choices remaining for the "South," and 1 choice remaining for the "West.") Next, notice that if all the students shifted one chair to the left once, twice, or thrice, they would all have the same neighbors that they originally had. This means that for each of the 24 ways the students can sit, 4 of those ways are not considered different.
Therefore, there are \(\frac{24}{4}\) or 6 different seatings.

2.2. The Pigeonhole Principle

A suprising number of counting problems can be solved with the so-called pigeonhole principle.

Pigeonhole Principle

If \(k+1\) pigeons are roosting in \(k\) pigeonholes then at least one pigeonhole must contain more than one pigeon.

NOTE: The Pigeonhole Principle is often attributed to Peter Gustav Lejeune Dirichlet, who called it the Schubfachprinzip. The remixer is willing to speculate that this principle has been known for at least as long as humans have kept birds such as pigeons.

Click here to see a photoshopped image that illustrates this principle.

Example

In a group of 367 people at least two will have the same birthday because there are only 366 possible birthdays (counting February 29).

You Try

How many people, with English names, must be in a room for at least two of the people to have first names that starts with the same letter?

2.3. Exercises

  1. There are 67 mathematics majors and 124 computer science majors at a college. There is no student who is both a mathematics major and a computer science major.

    1. In how many ways can two representatives be picked so that one is a mathematics major and one is a computer science major?

    2. In how many ways can one representative be picked who is either a mathematics major or a computer science major?

  2. A multiple-choice test contains 20 questions, and each question has four choices.

    1. In how many ways can a student answer all of the questions on the test if each question must be answered?

    2. In how many ways can a student answer all of the questions if the student is allowed to not answer one or more questions?

  3. How many different three-letter initials, using uppercase English letters, are there?

  4. How many different three-letter initials, using uppercase English letters, end with "R"?

  5. How many bit strings are there of length five?

  6. How many bit strings are there of length five that begin and end with 1?

  7. How many bit strings are there of length less than \(n\), where \(n\) is a positive integer, that start and end with 1?

  8. How many license plates can be made using three digits followed by four uppercase English letters if:

    1. Digits and letters can be repeated?

    2. Digits and letters cannot be repeated?

  9. Each student in a Discrete Mathematics class is a mathematics major, a computer science major, or a double major in both mathematics and computer science. If the class has 5 mathematics majors (including double majors), 23 computer science majors (including double majors), and 7 double majors, how many students are in the class?

  10. Suppose a computer system requires a password of length no less than 7 and no more than 10 characters, and each character must be an English lowercase letter, an English uppercase letter, a digit, or one of six special characters (*, >, <, !, +, =).

    1. How many different passwords are available?

    2. Suppose a hacker can check a potential password once every nanosecond (1 nanosecond is \(1 \times 10^{-9}\) seconds). How long will it take the hacker to check every potential password?

  11. Suppose that there are 29 students in a class, all of whose last names use only English letters. Explain why at least 2 students in the class have last names that begin with the same letter.

  12. Show that in any set of 5 integers, there are at least two of them that have the same remainder when divided by 4.

  13. A bag contains 8 red balls and 7 blue balls.

    1. How many balls must be chosen to be sure of choosing 3 of the same color?

    2. How many must be chosen to be sure of choosing 3 red balls?

  14. Someone cleaning out their attic finds a box containing 12 rock CDs and 12 country CDs. What is the minimum number of CDs they can take out to guarantee at least one of each type?

  15. Give an argument that there are at least two people in California with the same number of hairs on their head.