Key Concepts & Glossary

Key Equations

number of permutations of [latex]n[/latex] distinct objects taken [latex]r[/latex] at a time [latex]P\left(n,r\right)=\frac{n!}{\left(n-r\right)!}[/latex]
number of combinations of [latex]n[/latex] distinct objects taken [latex]r[/latex] at a time [latex]C\left(n,r\right)=\frac{n!}{r!\left(n-r\right)!}[/latex]
number of permutations of [latex]n[/latex] non-distinct objects [latex]\frac{n!}{{r}_{1}!{r}_{2}!\dots {r}_{k}!}[/latex]

Key Concepts

  • If one event can occur in [latex]m[/latex] ways and a second event with no common outcomes can occur in [latex]n[/latex] ways, then the first or second event can occur in [latex]m+n[/latex] ways.
  • If one event can occur in [latex]m[/latex] ways and a second event can occur in [latex]n[/latex] ways after the first event has occurred, then the two events can occur in [latex]m\times n[/latex] ways.
  • A permutation is an ordering of [latex]n[/latex] objects.
  • If we have a set of [latex]n[/latex] objects and we want to choose [latex]r[/latex] objects from the set in order, we write [latex]P\left(n,r\right)[/latex].
  • Permutation problems can be solved using the Multiplication Principle or the formula for [latex]P\left(n,r\right)[/latex].
  • A selection of objects where the order does not matter is a combination.
  • Given [latex]n[/latex] distinct objects, the number of ways to select [latex]r[/latex] objects from the set is [latex]\text{C}\left(n,r\right)[/latex] and can be found using a formula.
  • A set containing [latex]n[/latex] distinct objects has [latex]{2}^{n}[/latex] subsets.
  • For counting problems involving non-distinct objects, we need to divide to avoid counting duplicate permutations.

Glossary

Addition Principle
if one event can occur in [latex]m[/latex] ways and a second event with no common outcomes can occur in [latex]n[/latex] ways, then the first or second event can occur in [latex]m+n[/latex] ways
combination
a selection of objects in which order does not matter
Fundamental Counting Principle
if one event can occur in [latex]m[/latex] ways and a second event can occur in [latex]n[/latex] ways after the first event has occurred, then the two events can occur in [latex]m\times n[/latex] ways; also known as the Multiplication Principle
Multiplication Principle
if one event can occur in [latex]m[/latex] ways and a second event can occur in [latex]n[/latex] ways after the first event has occurred, then the two events can occur in [latex]m\times n[/latex] ways; also known as the Fundamental Counting Principle
permutation
a selection of objects in which order matters