6.2b Permutations

Permutation

A permutation is a sequence (i.e., an ordered list of elements from a set), where elements are not replaced. The total number of permutations of $k\le n$ elements from a set of $n$ elements is
$N=\frac{n!}{(n-k)!},$
where the denominator “cuts off” the arrangements of the $n-k$ elements that are not selected.

Permutation counting is used to count the number of ways to arrange distinct objects in a specific order, such as the number of ways to seat five different people around a table.

Intuition

The number of ways to rearrange a sequence is given as $n^k=n\cdot n\cdot \dots \cdot n$. This is valid when elements in the set of origin are not taken out of the set. However, given a starting amount of $n$ elements, which ARE taken out of the set, the total number of elements is $n\cdot (n-1)\cdot \dots \cdot 2\cdot 1$.

However, this formula only accounts for sequences where all elements in the set are used up. If we are trying to solve for a certain constrained length of a sequence $k\le n$, then we must “remove” any arrangements of the remaining $n-k$ elements, thereby deriving $\frac{n!}{(n-k)!}$.

Examples

Anagrams

Anagrams are rearrangements of a word’s letters.

How many anagrams of the word "COUNT" are there? $5!$.

Since all 5 letters are distinct, the total amount of anagrams in count is

How many anagrams of "BERKELEY" are there? $\left(\genfrac{}{}{0ex}{}{8}{3}\right)$, since we don't want to treat each E as a distinct letter. Then, we have 5 more empty slots that we could fill up with the other 5 distinct letters. Therefore, $N=\left(\genfrac{}{}{0ex}{}{8}{3}\right)\cdot 5!=8!/3!.$

We have 8 letters, but this time there are 3 E’s. Therefore, the number of positions where the E’s could go are

The Count