11.5 Counting Principles

Fundamental Counting Principles

Counting principles give you systematic ways to figure out how many outcomes are possible in a given scenario. They form the foundation for probability, combinatorics, and many real-world applications in fields like cryptography and genetics.

more resources to help you study

practice questions

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 another, and these two things cannot happen simultaneously, then there are $n_1 + n_2$ total ways to choose.

This extends naturally: for any number of mutually exclusive events, just add up all the individual counts.

Example: You're picking one item of clothing to buy. A store has 5 different shirts and 3 different pairs of pants. Since you're choosing one item (shirt or pants, not both), there are $5 + 3 = 8$ possible choices.

Multiplication principle applications

The multiplication principle applies when you're making multiple independent choices (you do one and the other).

If there are $n_1$ ways to do one thing and $n_2$ ways to do another, then there are $n_1 \times n_2$ ways to do both. This extends to any number of independent events by multiplying all the individual counts together.

Example: You're building an outfit by choosing a shirt and pants. With 5 shirt colors and 3 pant styles, you get $5 \times 3 = 15$ possible outfits.

The key distinction between these two principles comes down to "or" vs. "and." Addition handles "or" (mutually exclusive choices). Multiplication handles "and" (independent sequential choices). Many complex problems require both principles together, and drawing a probability tree can help you visualize all the branches of outcomes.

Permutations and Combinations

The core question here: does the order of your selection matter? If yes, you want a permutation. If no, you want a combination.

Permutations of distinct objects

A permutation is an arrangement of objects in a specific order. Changing the order creates a different permutation.

• The number of ways to arrange all $n$ distinct objects is $n!$ (read "$n$ factorial"):

$n! = n \times (n-1) \times (n-2) \times \cdots \times 3 \times 2 \times 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 arrange 3 books on a shelf from a collection of 10 distinct books? $P(10,3) = \frac{10!}{(10-3)!} = \frac{10!}{7!} = 10 \times 9 \times 8 = 720$

Notice how the formula cancels out everything below the $r$-th factor. You're left multiplying the top $r$ values descending from $n$.

Combinations for group selection

A combination is a selection of objects where order does not matter. Picking {A, B, C} is the same as picking {C, A, B}.

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

The relationship between permutations and combinations is straightforward: every combination of $r$ items can be rearranged $r!$ ways to produce permutations. So:

$P(n,r) = r! \times C(n,r)$

This means combinations are always smaller than (or equal to) permutations for the same $n$ and $r$, since you're dividing out the redundant orderings.

Example: Choosing 3 pizza toppings from 10 options (order doesn't matter): $C(10,3) = \frac{10!}{3! \times 7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$

Combinations can also be read off Pascal's triangle, where each entry equals the sum of the two entries directly above it. The entry in row $n$, position $r$ (both starting from 0) gives $\binom{n}{r}$.

Subset counting with empty set

Every element in a set is either included or excluded from a subset. That's 2 independent choices per element, so a set with $n$ elements has:

$2^n \text{ total subsets}$

This count includes the empty set (no elements chosen) and the full set itself (all elements chosen). The empty set is a subset of every set.

Example: The set $\{apple, banana, orange, pear\}$ has $2^4 = 16$ subsets, ranging from $\emptyset$ to the full set of all 4 fruits.

This connects directly to combinations: the total number of subsets equals $\sum_{r=0}^{n} \binom{n}{r} = 2^n$.

Permutations with repeated elements

When some objects in your set are identical, swapping identical items doesn't produce a new arrangement. You need to divide out those redundant swaps.

For $n$ total elements where there are $n_1$ of one kind, $n_2$ of another, and so on up to $n_k$ of the $k$-th kind:

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

Example: How many distinct ways can you arrange the letters in BOOKKEEPER?

BOOKKEEPER has 10 letters: 1 B, 2 O's, 2 K's, 2 E's, 1 P, 1 R.

$\frac{10!}{1! \times 2! \times 2! \times 2! \times 1! \times 1!} = \frac{3{,}628{,}800}{8} = 453{,}600$

Without accounting for repeats, you'd overcount by treating the two O's (for instance) as distinguishable when they're not.

Sampling Methods

How you sample from a population affects the number of possible outcomes and the probabilities involved.

Sampling with replacement

Each item is returned to the population before the next selection. This means:

• The pool of choices stays the same size every time you draw.
• The probability of selecting any particular item remains constant across draws.
• Draws are independent of each other.

If you're selecting $r$ items from a population of $n$ with replacement, there are $n^r$ possible outcomes (multiplication principle, since each draw has $n$ options).

Sampling without replacement

Once an item is selected, it's removed from the population. This means:

• The pool shrinks by one after each draw.
• The probability of selecting any remaining item changes after each selection.
• Draws are not independent.

If you're selecting $r$ items from $n$ without replacement and order matters, the count is $P(n,r)$. If order doesn't matter, it's $C(n,r)$. Most real-world sampling scenarios (like drawing cards from a deck or selecting people for a committee) use sampling without replacement.