7.1: The Fundamental Principle of Counting

Last updated
Save as PDF

Page ID: 40933

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

Combinatorics is a major area of what is generally known as "Discrete Mathematics." The word discrete refers to quantities that are individual, separate or distinct. This creates a major division in mathematics between "continuous mathematics" and "discrete mathematics." The difference between these two areas is that continuous mathematics considers and uses all parts of the number line whole numbers, rational numbers (fractions), irrational numbers and so forth. Discrete mathematics typically uses only the whole numbers.

Rather than limiting the possibilities in mathematics, this restriction actually opens amazing new areas of consideration. The binary codes that computers use are generally controlled and kept (mostly) error free through the use of discrete mathematics. Computer security for the simplest (checking your on-line bank balance) and the most complex (high level classified data) digital information is handled through encryption that relies on the concepts of discrete mathematics.

Any type of application in the sciences that involves choices and possibilities often uses the concepts of combinatorics. Combinatorial chemistry explores the results when a series of different chemical groups are added to the same basic chemical structure to investigate the qualities of the resulting compound. In addition, combinatorics is very important to the study of probability. In order to calculate the probability of an event, it is often necessary to calculate how many

different ways something can happen.
The first major idea of combinatorics is the fundamental principle of counting. This is the idea that if two events occur in succession and there are $m$ ways to do the first one and $n$ ways to do the second (after the first has occurred), then there are $m * n$ ways to complete the two tasks in succession.

For example, in throwing two six-sided dice, there are 36 possibilities - six possibilities from the first die and six from the second. These possibilities are listed below:
$clipboard_e186c4a32a665b07b79f1269ff2426ae7.png$
If we were to throw a six-sided die and an eight sided-sided die, then there would be $6 * 8=48$ different possibilities.

Often the creation of a tree diagram can help us to visualize the possibilities. Suppose that a three-digit code using the numbers 0,1 and 2 is created so that repetition of the numbers is allowed. There would 3 possibilities for the first number, three for the second number and three for the third number meaning that there would be a total of $3 * 3 * 3=27$ different possible codes.
The tree diagram to illustrate this is shown on the next page.
$clipboard_ec71ce7e5d3909ab5b777c86a60e13345.png$

All of the possibilities are listed out and can be constructed from the tree diagram.
Here are some sample problems for using the fundamental principle of counting (also known as the multiplication principle).

Example:
An ice cream shop offers Vanilla, Chocolate, Strawberry, Boysenberry and Rocky Road ice cream. The ice cream comes with either a waffle cone, a sugar cone or a wafer cone and can be plain or with sprinkles. How many different ways are there to order a single scoop of ice cream?

With 5 different types of ice cream, 3 different cones and 2 choices for sprinkles, there would be $5 * 3 * 2=30$ different possibilities.

Example:
In many states the license plates for automobiles consist of three letters followed three numbers.
How many different possibilities are there:
if repetition of letters and numbers is allowed?
if repetition of letters and numbers is not allowed?
There are six positions for letters and numbers that make up the license plate.
The first three are to be letters and the second three numbers.
There are 26 choices for the first three and 10 choices for the second three, so there are $26 * 26 * 26 * 10 * 10 * 10=17,576,000$ possible license plates if repetition is allowed.

If repetition is not allowed then we have to discount whichever letter or number is chosen for a particular position. So, for the first letter there are 26 possibilities, but then only 25 for the second letter and 24 for the third. Likewise, with the numbers there are 10 choices initially, then 9 choices and then 8
So, the solution without repetition would be $26 * 25 * 24 * 10 * 9 * 8=11,232,000$

4) $\quad$ A coin is flipped five times and the result each time is recorded. How many different possible outcomes are there?
5) $\quad$ A coin is flipped and a six-sided die is rolled and the results are recorded. If this is done three times, how many possible outcomes are there?
6) $\quad$ Two cards are chosen from a deck of 52 cards. If the first card is not replaced before the second card is chosen, how many ways are there to choose:
a) $\quad$ A spade first and a heart second?
b) $\quad$ Two spades?
7) $\quad$ A company has 3000 employees. They plan to implement an employee ID numbering system that would consist of a letter followed by two digits. Is it possible to give each employee a different ID code under this plan?
8) $\quad$ A baseball team has 7 pitchers and 3 catchers. How many different batteries (pitcher - catcher combinations) are possible?
9) $\quad$ A string of five letters is created using the letters $\mathrm{A}, \mathrm{B}, \mathrm{C}, \mathrm{D}$ and E. How many of these letter strings are possible if:
$\quad$ a) $\quad$ No conditions are imposed
$\quad$ b) Repetition of the letter $A$ is not allowed
$\quad$ c) Each letter string must begin with $C$
$\quad$ d) $\quad$ B must be the middle letter
$\quad$ e) $\quad$ $A, B$ and $C$ must be the middle letters in any order with no repetition
For Part (e) please list all possibilities.
10) (\quad\) A combination lock is numbered from 0 to 30. Each combination consists of three numbers in succession. Successive numbers must be different, but the first and third can be the same. How many different combinations are possible?