2 Permutations

How many ways can we arrange objects?

A permutation is an arrangement of objects in a specific order. We often are interested in the number of ways we can arrange objects, in other words, the number of permutations for a given set of objects.

Example{example}

How many ways can we arrange the letters in the word “cat”?

Solution{solution}

Let’s first list all possible arrangements that start with c:

cat, cta

Next, let’s list all possible arrangements that start with a:

act, atc

Finally, let’s list all possible arrangements that start with t:

tac, tca

Therefore, there are 6 possible arrangements of the letter “cat”: {cat, cta, act, atc, tac, tca}.

Example{example}

How many ways can we arrange the letters in the word “eel”?

Solution{solution}

Let’s first list all possible arrangements that start with e:

eel, ele

Next, let’s list all possible arrangements that start with l:

lee

Therefore, there are 3 possible arrangements of the letter “eel”: {eel, ele, lee}.

Orderings of distinct objects

Number of permutations of distinct objects{rule}

The number of orderings (permutations) of \(n\) distinct objects is given by the factorial of \(n\), denoted as \(n!\):

\[ n! = \underbrace{n}_{\text{Choices for} \atop \text{the first object}} * \underbrace{(n-1)}_{\text{Choices for the second object} \atop \text{given one has already been chosen}} * \underbrace{(n-2)}_{\text{Choices for the third object} \atop \text{given two have already been chosen}} * \dots * \underbrace{2}_{\text{Choices for the} \atop \text{second to last object}} \]

Example{example}

How many ways can you arrange any 3 distinct letters from the alphabet if each of the letters can only appear once?

Solution{solution}

There are 26 choices for the first letter, 25 choices for the second letter, and 24 choices for the third letter. Therefore, the number of ways to arrange 3 distinct letters from the alphabet is:

\(\frac{26!}{(26-3)!} = 26*25*24 = 15,600\).

Orderings of non-distinct objects

Now, consider some of the objects are non-distinct. For example, consider the set the ways to order 1, 1, 0, 0, 0:

First, just “force” the 1’s and 0’s to be distinct:

How many ways can we arrange

\(1_a, 1_b, 0_w, 0_x, 0_y\)?

There are \(5!\) ways to arrange these objects. Now, let’s consider how much we have overcounted:

Let’s consider for a given sequence, how many ways we can arrange the distinct objects to get the same indistinct sequence:

\(1_a, 1_b, 0_w, 0_x, 0_y\)

We can rearrange the 1’s:

\(1_b, 1_a, 0_w, 0_x, 0_y\)

or the 0’s:

\(1_a, 1_b, 0_w, 0_y, 0_y\)

\(1_a, 1_b, 0_x, 0_w, 0_y\)

\(1_a, 1_b, 0_x, 0_y, 0_w\)

\(1_a, 1_b, 0_y, 0_w, 0_x\)

\(1_a, 1_b, 0_y, 0_x, 0_w\)

So there are

\[ \underbrace{2!}_{\text{ways to arrange the 1's}} * \underbrace{3!}_{\text{ways to arrange the 0's}} = 12 \]

That means, we can just divide out the number of ways we overcounted to get the number of ways to arrange the indistinct objects:

The number of ways to arrange two 1’s and three 0’s is therefore:

\[ \frac{5!}{2!3!} = 10 \]

Number of permutations of partially non-distinct objects{rule}

The number of ways to arrange \(n\) objects where \(n_1\) are of (indistinguishable) type 1, \(n_2\) are of type 2, …, and \(n_k\) are of type \(k\) is (where \(n = \sum_{i=1}^{k} n_i\)):

\[ \frac{n!}{n_1!n_2!...n_k!} \]

Example{example}

How many ways can you arrange the letters in the word “MISSISSIPPI”?

Solution{solution}

There are 4 distinct letters in the word MISSISSIPPI: M, I, S, P. The number of ways to arrange the letters in the word MISSISSIPPI is:

M appears once, so \(n_1 = 1\) I appears four times, so \(n_2 = 4\) S appears four times, so \(n_3 = 4\) P appears twice, so \(n_4 = 2\)

Therefore, the number of ways to arrange the letters in the word MISSISSIPPI is:

\[ \frac{11!}{1!4!4!2!} = 34,650 \]