Summary: Counting Principles

Key Equations

number of permutations of n distinct objects taken r at a time P(n,r)=n!(nr)!
number of combinations of n distinct objects taken r at a time C(n,r)=n!r!(nr)!
number of permutations of n non-distinct objects n!r1!r2!rk!
Binomial Theorem (x+y)n=nk0(nk)xnkyk
(r+1)th term of a binomial expansion (nr)xnryr

Key Concepts

  • If one event can occur in m ways and a second event with no common outcomes can occur in n ways, then the first or second event can occur in m+n ways.
  • If one event can occur in m ways and a second event can occur in n ways after the first event has occurred, then the two events can occur in m×n ways.
  • A permutation is an ordering of n objects.
  • If we have a set of n objects and we want to choose r objects from the set in order, we write P(n,r).
  • Permutation problems can be solved using the Multiplication Principle or the formula for P(n,r).
  • A selection of objects where the order does not matter is a combination.
  • Given n distinct objects, the number of ways to select r objects from the set is C(n,r) and can be found using a formula.
  • A set containing n distinct objects has 2n subsets.
  • For counting problems involving non-distinct objects, we need to divide to avoid counting duplicate permutations.
  • (nr) is called a binomial coefficient and is equal to C(n,r).
  • The Binomial Theorem allows us to expand binomials without multiplying.
  • We can find a given term of a binomial expansion without fully expanding the binomial.

Glossary

Addition Principle if one event can occur in m ways and a second event with no common outcomes can occur in n ways, then the first or second event can occur in m+n ways

binomial coefficient the number of ways to choose r objects from n objects where order does not matter; equivalent to C(n,r), denoted (nr)

binomial expansion the result of expanding (x+y)n by multiplying

Binomial Theorem a formula that can be used to expand any binomial

combination a selection of objects in which order does not matter

Fundamental Counting Principle if one event can occur in m ways and a second event can occur in n ways after the first event has occurred, then the two events can occur in m×n ways; also known as the Multiplication Principle

Multiplication Principle if one event can occur in m ways and a second event can occur in n ways after the first event has occurred, then the two events can occur in m×n ways; also known as the Fundamental Counting Principle

permutation a selection of objects in which order matters