Sequences and Counting Reference

Permutations and Combinations

Permutations count ordered arrangements. Combinations count unordered groups. Most counting problems become easier once you decide whether changing order creates a new outcome.

Solved Examples

Jump directly to a worked example by counting type.

Fact Table

Question Type Order Matters? Use
Award places, passwords, lineups, schedules Yes. $ABC$ and $BAC$ are different. Permutation or slot multiplication.
Committees, teams, hands of cards, selected groups No. $\{A,B,C\}$ and $\{B,A,C\}$ are the same. Combination.
All distinct objects arranged in a line Yes. $n!$
Objects arranged around a circle Yes, but rotations repeat. $(n-1)!$
Repeated identical objects in a word or list Yes, but identical swaps repeat. Divide by repeated factorials.

Content Formulas

Permutation
$$\,^nP_r=\frac{n!}{(n-r)!}$$
Combination
$$\,^nC_r=\frac{n!}{r!(n-r)!}$$
Circular Arrangement
$$(n-1)!$$
Repeated Objects
$$\frac{n!}{a!b!c!\cdots}$$
Use permutations when positions or roles are different. Use combinations when the final group is all that matters.

Classic Examples

Award Places

Twelve finalists compete for first, second, and third place. How many results are possible?

Solution Steps
  1. Use a permutation because the places are ordered.
  2. Write the permutation formula.
  3. Expand the factorial quotient.
  4. State the number of results: $1320$.
$$\,^{12}P_3=\frac{12!}{(12-3)!}$$ $$\,^{12}P_3=\frac{12!}{9!}$$ $$\,^{12}P_3=12\cdot 11\cdot 10$$ $$\,^{12}P_3=1320$$

Lock Code

A four-digit lock uses digits 0 through 9. Digits may not repeat. How many codes are possible?

Solution Steps
  1. Count the choices for each slot without repetition.
  2. State the number of codes: $5040$.
$$N=10\cdot 9\cdot 8\cdot 7$$ $$N=5040$$

Committee

A club chooses 3 representatives from 12 members. There are no officer roles. How many committees are possible?

Solution Steps
  1. Use a combination because officer order does not matter.
  2. Write the combination formula.
  3. Simplify the factorial quotient.
  4. State the number of committees: $220$.
$$\,^{12}C_3=\frac{12!}{3!(12-3)!}$$ $$\,^{12}C_3=\frac{12!}{3!9!}$$ $$\,^{12}C_3=\frac{12\cdot 11\cdot 10}{3\cdot 2\cdot 1}$$ $$\,^{12}C_3=220$$

Grid Travel

A path crosses a 3-by-3 city grid from the lower-left corner to the upper-right corner, moving only right or up. How many shortest paths are possible?

Solution Steps
  1. Recognize that a shortest path has three right moves and three up moves.
  2. Choose the positions of one kind of move.
  3. State the number of paths: $20$.
$$N=\frac{6!}{3!3!}$$ $$N=\,^6C_3$$ $$N=20$$

Stars and Bars

Ten identical candies are shared among four children. A child may receive no candies. How many distributions are possible?

Solution Steps
  1. Use three dividers to create four labeled groups.
  2. Apply the stars-and-bars combination formula.
  3. State the number of distributions: $286$.
$$N=\,^{10+4-1}C_{4-1}$$ $$N=\,^{13}C_3$$ $$N=286$$

Circular Seating

Eight students sit around a round table. Rotations of the same seating count as the same arrangement.

Solution Steps
  1. Fix one person to remove rotational duplicates.
  2. Arrange the remaining seven students.
  3. State the number of arrangements: $5040$.
$$N=(8-1)!$$ $$N=7!$$ $$N=5040$$

Keyring

Eight unique keys go on a ring. The ring can be rotated or flipped over. How many keyrings are distinct?

Solution Steps
  1. Remove rotational duplicates.
  2. Divide by $2$ because flips are also equivalent.
  3. State the number of keyrings: $2520$.
$$N=\frac{(8-1)!}{2}$$ $$N=\frac{7!}{2}$$ $$N=2520$$

Repeated Letters

How many distinct arrangements can be made from the letters in LEVEL?

Solution Steps
  1. Arrange all letters and divide by the factorial for each repeated letter.
  2. Evaluate the quotient.
  3. State the number of arrangements: $30$.
$$N=\frac{5!}{2!2!}$$ $$N=\frac{120}{4}$$ $$N=30$$

Block Method

Six students line up for a photo. Ava and Ben must stand next to each other. How many lineups are possible?

Solution Steps
  1. Treat the adjacent pair as one block.
  2. Arrange the block internally in two ways.
  3. State the number of lineups: $240$.
$$N=5!\cdot 2!$$ $$N=120\cdot 2$$ $$N=240$$

At Least One Restriction

A 4-person committee is chosen from 6 teachers and 5 students. It must include at least 2 teachers.

Solution Steps
  1. Count the legal cases with exactly two, three, or four teachers.
  2. Add the three case counts.
  3. State the number of committees: $265$.
$$N=\,^6C_2\,^5C_2+\,^6C_3\,^5C_1+\,^6C_4\,^5C_0$$ $$N=15\cdot 10+20\cdot 5+15\cdot 1$$ $$N=265$$