Permutations & Combinations Master Reference Cheat Sheet

Key Facts

• The factorial of a positive integer is $n! = n(n - 1)(n - 2)\cdots 2\cdot 1$, and $0! = 1$.
• The multiplication principle says that if one choice has $a$ options and the next has $b$ options, then the total number of ordered outcomes is $a\cdot b$.
• The number of permutations of $n$ distinct objects taken $r$ at a time is $P(n,r) = \frac{n!}{(n-r)!}$.
• The number of combinations of $n$ distinct objects taken $r$ at a time is $C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$.
• If order matters and repetition is allowed, the number of length $r$ arrangements from $n$ choices is $n^r$.
• If order does not matter and repetition is allowed, the number of selections is $\binom{n+r-1}{r}$.
• The number of distinct arrangements of $n$ objects with repeated groups of sizes $a$, $b$, and $c$ is $\frac{n!}{a!b!c!}$.
• For combinations, symmetry gives $\binom{n}{r} = \binom{n}{n-r}$, so choosing $r$ items is equivalent to leaving out $n-r$ items.

Vocabulary

Factorial

A factorial, written $n!$, is the product of all positive integers from $n$ down to $1$, with $0! = 1$.

Permutation

A permutation is an arrangement where the order of the selected items matters.

Combination

A combination is a selection where the order of the selected items does not matter.

Repetition

Repetition means an item may be chosen more than once in the same counting process.

Multiplication Principle

The multiplication principle states that choices made in stages are counted by multiplying the number of options at each stage.

Binomial Coefficient

A binomial coefficient, written $\binom{n}{r}$, counts the number of ways to choose $r$ items from $n$ items without order.