Permutations Intro
Simple overview of permutations.
Permutations Main Idea
Permutations count the number of ways we can arrange $r$ distinct objects into $r$ positions from a total set of $n$ distinct objects.
You’ll know you are working with permutations when the order of a result matters. In this video we go over two examples:
- who gets $1\text{st}$, $2\text{nd}$, and $3\text{rd}$ place in a pizza eating competition,
- who becomes president and who becomes vice president from a set of given candidates.
These are ordered outcomes. Switching the people that end up in first, second, or third place is associated with different outcome.
Watch this section: loose permutation definition at 0:00.
The Permutation Formula
The video uses the notation $nPr$.
The formula is
\[nPr = \frac{n!}{(n-r)!}.\]The same idea can also be read as a decreasing product:
\[nPr = n(n-1)(n-2)\cdots (n-r+1).\]This second version should look similar to $n!$, but it stops after $r$ positions are filled instead of ordering the entire set of $n$ distinct objects.
Watch this section: general permutation formula at 1:02.
Pizza Competition Example
The first example in the video counts possible $1\text{st}$, $2\text{nd}$, and $3\text{rd}$ place outcomes for $5$ competitors.
For the direct counting view:
- there are $5$ choices for $1\text{st}$ place,
- then $4$ choices for $2\text{nd}$ place,
- then $3$ choices for $3\text{rd}$ place.
So the number of ordered outcomes is
\[5\cdot 4\cdot 3 = 60.\]Using permutation notation, this is
\[5P3= \frac{5!}{(5-3)!}.\]Then
\[5P3 = \frac{5!}{2!} = \frac{5\cdot 4\cdot 3\cdot 2\cdot 1}{2\cdot 1} = 5\cdot 4\cdot 3 = 60.\]We get the same count if we walk through it directly like at the beginning of this section or using the formula for nPr.
Watch this section: pizza eating competition example at 0:05.
President And Vice President Example
The second example counts ways to choose a president and a vice president from $8$ students.
There are two different positions, so order matters. If Alice is president and Jordan is vice president, that is different from Jordan as president and Alice as vice president.
The direct counting view is:
\[8\cdot 7 = 56.\]There are $8$ choices for president. After one student is chosen, there are $7$ choices left for vice president.
Using the permutation formula,
\[8P2=\frac{8!}{(8-2)!}.\]Then
\[8P2=\frac{8!}{6!} = \frac{8\cdot 7\cdot 6!}{6!} = 8\cdot 7 = 56.\]We get the same result again from direct counting and the permutation formula.
Watch this section: president and vice president example at 2:07.
Why $nPn=n!$
What happens when we select all $n$ out of $n$ distinct objects. (What happens when $r=n$?)
If $r=n$, then
\[nPn = \frac{n!}{(n-n)!}.\]Since $n-n=0$ and $0!=1$,
\[nPn = \frac{n!}{0!}=\frac{n!}{1}=n!.\]So
\[nPn=n!.\]$nPn$ is equivalent to $n!$.
Watch this section: why $nPn=n!$ at 3:27.
Timestamp Guide
Related Combinatorics Work
For the factorial background behind the formula, use the companion guide for factorials and arrangements.
The video description also points to the JoeCMath combinatorics playlist: watch the playlist on YouTube.