13.5 Counting Principles

Counting Principles

Counting principles give you systematic ways to figure out how many possible outcomes exist in a given scenario. Whether you're calculating how many different passwords are possible or how many ways to arrange a committee, these tools are the foundation for probability and combinatorics problems.

This section covers the addition and multiplication rules, permutations (where order matters), combinations (where it doesn't), subsets, and permutations with repeated elements.

Counting Principles

Addition principle in counting

The addition principle applies when you're choosing between mutually exclusive options (you pick one or the other, not both).

If there are $n_1$ ways to do one thing and $n_2$ ways to do a different thing, and these two things can't happen at the same time, then there are $n_1 + n_2$ total ways to choose.

This extends naturally: for $k$ mutually exclusive events with $n_1, n_2, \ldots, n_k$ options, the total number of choices is $n_1 + n_2 + \ldots + n_k$.

Example: A restaurant offers 5 appetizers and 8 main courses. If you're ordering just one dish (either an appetizer or a main course), you have $5 + 8 = 13$ options.

The key word that signals the addition principle is "or." If you're choosing between separate categories, you add.

Multiplication principle applications

The multiplication principle (also called the fundamental counting principle) applies when events happen together or in sequence.

If one event can occur in $m$ ways and a second independent event can occur in $n$ ways, then the two events can occur together in $m \times n$ ways.

For $k$ sequential events with $n_1, n_2, \ldots, n_k$ options respectively, the total number of combined outcomes is $n_1 \times n_2 \times \ldots \times n_k$.

Example: A sandwich shop offers 3 types of bread and 5 fillings. The total number of different sandwiches is $3 \times 5 = 15$.

The key word here is "and." If you're making one choice and then another, you multiply.

Permutations of distinct objects

A permutation is an arrangement where order matters. Rearranging the same objects into a different sequence counts as a different permutation.

The number of ways to arrange all $n$ distinct objects is:

$n! = n \times (n-1) \times (n-2) \times \ldots \times 2 \times 1$

For example, $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$. By convention, $0! = 1$.

When you're arranging only $r$ objects chosen from $n$ distinct objects, use:

$P(n,r) = \frac{n!}{(n-r)!}$

Example: How many ways can you award 1st, 2nd, and 3rd place among 10 runners?

$P(10,3) = \frac{10!}{7!} = 10 \times 9 \times 8 = 720$

You multiply 10 choices for 1st, then 9 remaining for 2nd, then 8 for 3rd.

Combinations in counting problems

A combination is a selection where order does not matter. Picking persons A, B, C for a committee is the same as picking B, C, A.

The number of ways to choose $r$ objects from $n$ distinct objects is:

$C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$

Notice the relationship: $C(n,r) = \frac{P(n,r)}{r!}$. You're dividing out the $r!$ arrangements because order no longer matters.

Example: How many ways can you choose a 3-person committee from 10 people?

$C(10,3) = \frac{10!}{3! \times 7!} = \frac{720}{6} = 120$

Number of subsets calculation

A subset is any selection of elements from a set, including selecting none of them (the empty set) or all of them.

• A set with $n$ elements has exactly $2^n$ total subsets.
• The number of subsets containing exactly $r$ elements equals $C(n,r)$.

Example: A pizza menu has 6 toppings. The total number of topping combinations (including a plain pizza with no toppings) is $2^6 = 64$.

Why $2^n$? For each element, you have 2 choices: include it or don't. By the multiplication principle, that's $2 \times 2 \times \ldots \times 2 = 2^n$.

Permutations with repeated elements

When some objects are identical, swapping identical items doesn't create a new arrangement. This reduces the total count.

If you have $n$ objects total, with $n_1$ identical of one type, $n_2$ of another, through $n_k$ of the $k$-th type, the number of distinct permutations is:

$\frac{n!}{n_1! \times n_2! \times \ldots \times n_k!}$

You divide by each group's factorial to remove the overcounting from rearranging identical items within each group.

Example: How many distinct arrangements of the letters in MISSISSIPPI?

The word has 11 letters: 1 M, 4 I's, 4 S's, 2 P's.

$\frac{11!}{1! \times 4! \times 4! \times 2!} = \frac{39916800}{1 \times 24 \times 24 \times 2} = 34{,}650$

Probability and Set Theory in Counting

These counting principles connect directly to probability. Probability measures the likelihood of an event and is calculated as:

$P(\text{event}) = \frac{\text{number of favorable outcomes}}{\text{total number of outcomes in the sample space}}$

The sample space is the set of all possible outcomes. Counting principles are how you determine both the numerator and denominator in that fraction.

Tree diagrams are a visual tool for listing all outcomes of sequential events. Each branch represents a choice, and following a path from start to end gives one complete outcome. They're especially helpful when the number of options changes at each stage or when events aren't independent.

Set theory provides the language for organizing outcomes. Unions correspond to the addition principle, and intersections relate to combined events counted by the multiplication principle.