From the free course College Algebra on Lykke
9.5 Counting Principles
Key concepts: Addition Principle · Multiplication Principle · Permutations of distinct objects · Permutation notation and formulas · Counting arrangements with restrictions · Combinations · Counting subsets · Permutations involving non-distinct objects
By the end of this section the student can: Solve counting problems using the Addition Principle; Solve counting problems using the Multiplication Principle; Solve counting problems using permutations involving n distinct objects; Solve counting problems using combinations; Find the number of subsets of a given set; Solve counting problems using permutations involving n non-distinct objects
9.5 Counting Principles
A customizable phone case can be produced in many different ways because each decision multiplies or adds to the available choices. Counting principles provide a systematic way to determine how many outcomes are possible without listing every outcome individually.
The Addition Principle
Use the Addition Principle when a choice can happen in one way or another way, and the alternatives are mutually exclusive, meaning that no outcome belongs to both categories.
Addition Principle: If one event can occur in $m$ ways and a mutually exclusive event can occur in $n$ ways, then either event can occur in $$m+n$$ ways.
For example, suppose a restaurant offers $3$ vegetarian entrées and $5$ meat entrées. A customer chooses one entrée, not both. Therefore, the choices are mutually exclusive:
$$3+5=8$$
There are $8$ possible entrées.
Worked example: using the Addition Principle
A bookstore sells $6$ different mathematics books and $4$ different science books. If a student chooses exactly one book, how many choices are possible?
The student chooses a mathematics book or a science book. These choices do not overlap, so add:
$$ \begin{aligned} \text{total choices} &=\text{mathematics choices}+\text{science choices}\ &=6+4\ &=10. \end{aligned} $$
There are $10$ possible choices.
A common mistake is to multiply $6$ and $4$. Multiplication is appropriate when the student chooses one mathematics book and one science book. Since only one book is selected here, addition is correct.
The Multiplication Principle
Use the Multiplication Principle when an outcome is produced by a sequence of successive choices. Multiply the number of options available at each stage.
Multiplication Principle: If one choice can be made in $m$ ways and a second choice can be made in $n$ ways for each first choice, then the two choices can be made in $$m\cdot n$$ ways.
The number of choices at a later stage may depend on what happened earlier. The multiplication principle still applies, but the number of options must be updated at each stage.
Worked example: choosing an outfit
Diane has $2$ skirts and $4$ blouses. She may also choose whether or not to wear a sweater. How many outfits are possible?
There are three successive decisions:
- Choose one of $2$ skirts.
- Choose one of $4$ blouses.
- Choose whether to wear the sweater or not, giving $2$ choices.
Therefore,
$$ \begin{aligned} \text{number of outfits} &=(\text{skirt choices})(\text{blouse choices})(\text{sweater choices})\ &=2\cdot 4\cdot 2\ &=16. \end{aligned} $$
Diane can create $16$ different outfits.
The key distinction is simple: use addition for separate alternatives and multiplication for stages that occur together. Choosing a vegetarian or meat entrée uses addition; choosing a skirt, blouse, and sweater option uses multiplication.
Permutations of Distinct Objects
A permutation is an arrangement of objects in which order matters. For example, the arrangements $ABC$ and $BAC$ are different permutations because the positions of the objects have changed.
If $n$ distinct objects are all arranged, the number of permutations is $$n!=n(n-1)(n-2)\cdots 3\cdot 2\cdot 1.$$
The symbol $n!$, read “$n$ factorial,” represents the product of all positive integers from $n$ down to $1$. By definition,
$$0!=1.$$
Worked example: arranging all objects
How many ways can $9$ swimmers line up?
There are $9$ choices for the first position. After one swimmer is placed, $8$ remain for the second position, then $7$ remain for the third, and so on:
$$ \begin{aligned} \text{number of arrangements} &=9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1\ &=9!\ &=362{,}880. \end{aligned} $$
Thus, the $9$ swimmers can line up in $362{,}880$ ways.
Worked example: a restriction on first place
Ariel must win first place in a swimming competition with $9$ swimmers. In how many ways can first, second, and third place be assigned?
Ariel’s first-place position is already fixed, so there is only $1$ choice for first place. After Ariel wins, $8$ swimmers remain for second place and $7$ remain for third place:
$$ \begin{aligned} \text{number of assignments} &=1\cdot 8\cdot 7\ &=56. \end{aligned} $$
There are $56$ possible assignments of first, second, and third place under this restriction.
Permutations of $r$ Objects Chosen from $n$
Often, only part of a collection is arranged. If $n$ distinct objects are available and $r$ of them are arranged in order, the number of permutations is written as
$$ {}_nP_r $$
or sometimes as $nP_r$.
Permutation formula: $$ {}_nP_r=\frac{n!}{(n-r)!}. $$
This formula follows from the Multiplication Principle. The first position has $n$ choices, the second has $n-1$ choices, and the final selected position has $n-r+1$ choices.
Worked example: selecting and ranking objects
How many ways can $3$ swimmers be assigned first, second, and third place from $9$ swimmers?
Because the positions are ordered, use permutations:
$$ \begin{aligned} {}_9P_3 &=\frac{9!}{(9-3)!}\ &=\frac{9!}{6!}\ &=\frac{9\cdot 8\cdot 7\cdot 6!}{6!}\ &=9\cdot 8\cdot 7\ &=504. \end{aligned} $$
There are $504$ possible assignments.
When $r=n$, every object is used, and the formula becomes
$$ {}_nP_n=\frac{n!}{(n-n)!} =\frac{n!}{0!} =\frac{n!}{1} =n!. $$
Thus, the formula for arranging all objects is a special case of the permutation formula.
Counting Arrangements with Restrictions
Restrictions should be handled before multiplying. A condition may fix one position, reduce the number of available choices, or force certain objects to occupy particular positions.
Worked example: parents at the ends
A family of $6$ people lines up for a portrait. The two parents must stand at the two ends. How many arrangements are possible?
First arrange the parents at the two ends. There are $2$ choices for which parent stands on the left; the other parent must stand on the right:
$$ 2\text{ choices}. $$
The remaining $4$ family members can be arranged in the $4$ middle positions in
$$ 4!=4\cdot 3\cdot 2\cdot 1=24 $$
ways. By the Multiplication Principle,
$$ \begin{aligned} \text{number of arrangements} &=2\cdot 4!\ &=2\cdot 24\ &=48. \end{aligned} $$
There are $48$ valid arrangements.
The phrase “parents must stand on the ends” does not mean there is only one arrangement for the parents. Their order can be reversed, which is why the factor $2$ is necessary.
Combinations
A combination is a selection in which order does not matter. Choosing Alice, Ben, and Carlos for a committee is the same selection as choosing Carlos, Alice, and Ben. The group is identical even though the listing order changes.
The number of combinations of $r$ objects selected from $n$ distinct objects is $$ {}_nC_r=\frac{n!}{r!(n-r)!}. $$
Permutations count ordered selections; combinations count unordered selections. The factor $r!$ in the combination formula removes the repeated counting caused by the $r!$ possible orders of the same selected group.
Worked example: selecting a committee
How many committees of $3$ students can be selected from a class of $8$ students?
Because the order of committee members does not matter, use combinations:
$$ \begin{aligned} {}_8C_3 &=\frac{8!}{3!(8-3)!}\ &=\frac{8!}{3!5!}\ &=\frac{8\cdot 7\cdot 6\cdot 5!}{(3\cdot 2\cdot 1)5!}\ &=\frac{8\cdot 7\cdot 6}{6}\ &=8\cdot 7\ &=56. \end{aligned} $$
There are $56$ possible committees.
If the three students were assigned president, vice president, and secretary, order would matter, so the correct count would be
$$ {}_8P_3=8\cdot 7\cdot 6=336. $$
The same $3$ students appear in $3!=6$ different leadership orders, explaining why
$$ {}_8P_3=3!({}_8C_3). $$
Counting Subsets
A subset is a collection formed by selecting elements from a set, with no regard to order. For each element, there are exactly two possibilities: include it in the subset or leave it out.
A set with $n$ elements has $$ 2^n $$ subsets.
Worked example: subsets of a set
How many subsets does a set with $5$ elements have?
Each of the $5$ elements has $2$ choices, so the Multiplication Principle gives
$$ \begin{aligned} \text{number of subsets} &=2\cdot 2\cdot 2\cdot 2\cdot 2\ &=2^5\ &=32. \end{aligned} $$
The set has $32$ subsets, including the empty set and the entire set.
Repeated or Non-Distinct Objects
The factorial formula $n!$ assumes that all objects are distinct. If some objects are identical, directly using $n!$ counts arrangements repeatedly. To correct this, divide by the factorial of the number of repetitions for each repeated object.
If $n$ objects contain repeated groups of sizes $a$, $b$, and so on, the number of distinct arrangements is $$ \frac{n!}{a!b!\cdots}. $$
Worked example: rearranging repeated letters
How many distinct rearrangements can be made from the letters in the word $\text{CARRIER}$?
The word $\text{CARRIER}$ has $7$ letters. The letter $R$ occurs $3$ times, while the other letters are distinct. If the three $R$’s were temporarily labeled, $R_1$, $R_2$, and $R_3$, then $7!$ arrangements would be counted. But the labels do not create different visible words, so divide by $3!$:
$$ \begin{aligned} \text{number of rearrangements} &=\frac{7!}{3!}\ &=\frac{7\cdot 6\cdot 5\cdot 4\cdot 3!}{3!}\ &=7\cdot 6\cdot 5\cdot 4\ &=840. \end{aligned} $$
There are $840$ distinct rearrangements.
Practice Problems
Solve each problem using the principle that matches the structure of the choices.
-
A café offers $4$ hot drinks and $6$ cold drinks. If a customer chooses one drink, how many choices are possible?
-
How many ways can $4$ people be arranged in a row?
-
How many $3$-person committees can be selected from $7$ people?
Answers:
-
The choices are mutually exclusive: $$ 4+6=10. $$
-
All $4$ people are arranged: $$ 4!=4\cdot 3\cdot 2\cdot 1=24. $$
-
Order does not matter: $$ {}_7C_3=\frac{7!}{3!4!}=35. $$
The central question is always whether order matters and whether choices occur as alternatives or as successive stages. Alternatives are added, successive choices are multiplied, ordered selections use permutations, and unordered selections use combinations.
Content adapted from OpenStax College Algebra 2e by Jay Abramson et al., licensed CC BY 4.0.
Source Materials
Study College Algebra on Lykke
This course page is free to open: signed out, you can read its first two sections, and signing in, on any plan, opens the rest. The free Lykke Chrome extension syncs your own Canvas courses, so ChatGPT, Claude and Muse can answer from your classes and deadlines. It only reads Canvas.
Add the free extensionSign in to open every section