Math Home

Given a set \(\{a_1, a_2, \dots, a_n\},\) a permutation of the set is a particular arrangement of the set.

Example: There are \(6\) permutations of the set \(\{a,b,c\}\) on a line:

- \(a,b,c\)
- \(a,c,b\)
- \(b,a,c\)
- \(b,c,a\)
- \(c,a,b\)
- \(c,b,a\)

Claim: If a set \(A\) has \(n\) elements, then there are \(n!\) permutations of the elements in the set.

▼ Proof:

Let \(x_1, x_2, \dots, x_n\) represent a permutation. We can create a particular permutation by first assigning one element of \(A\) to \(x_1.\) Then assign an element in \(A\) not assigned to \(x_1\) to \(x_2.\) Then assign an element in \(A\) not assigned to \(x_1\) or \(x_2\) to \(x_3,\) and so on.

Each assignment of a value from \(A\) to one of the \(x_i\) will be an experiment. This is a total of \(n\) experiments:

Example to help understand the proof:

Let \(A = \{a,b,c\}.\) The first experiment is to assign a value to \(x_1.\) There are \(3\) possible outcomes: \(x_1 = a,\) \(x_1 = b,\) or \(x_1 = c.\) For this example, suppose \(x_1 = b.\)

The next experiment is to assign a value to \(x_2.\) Since \(x_1 = b,\) there are only \(2\) possible outcomes: \(x_2 = a,\) \(x_2 = c.\) Suppose \(x_2 = c.\)

The last experiment is to assign a value to \(x_3.\) Since \(x_1 = b\) and \(x_2 = c,\) the only possible outcomes is \(x_3 = a.\) The permutation is \(b, c, a.\)

There are always \(3\) possible outcomes for \(x_1,\) \(2\) possible outcomes for \(x_2,\) and \(1\) possible outcome for \(x_1.\) By the multiplication rule, the total number of possible outcomes is \(3 \cdot 2 \cdot 1 = 6 = 3!.\)

Since \(A\) as \(3\) elements, there are \(3!\) possible permutations of the elements of \(A.\)

Each assignment of a value from \(A\) to one of the \(x_i\) will be an experiment. This is a total of \(n\) experiments:

- Assign a value to \(x_1\)
- Assign a value not assigned to \(x_1\) to \(x_2\)
- Assign a value not assigned to \(x_1\) or \(x_2\) to \(x_3\) \(\vdots\)
- Assign a value not assigned to \(x_1, x_2, \dots, x_{n-2}\) or \(x_{n-1}\) to \(x_n.\)

- There are \(n\) values that can be assigned to \(x_1\) so the first experiment has \(n\) possible outcomes.
- No matter which value is assigned to \(x_1,\) there will be \(n-1\) numbers left to assign to \(x_2.\) The second experiment has \(n-1\) possible outcomes.
- No matter which values are assigned to \(x_1\) and \(x_2,\) there are \(n-2\) numbers left to assign to \(x_3.\) The third experiment has \(n-2\) possible outcomes. \(\vdots\)
- After all the other \(n-1\) values are assigned, there is only \(1\) value left to assign to \(x_n.\) The last experiment will only have \(1\) possible outcome.

Example to help understand the proof:

Let \(A = \{a,b,c\}.\) The first experiment is to assign a value to \(x_1.\) There are \(3\) possible outcomes: \(x_1 = a,\) \(x_1 = b,\) or \(x_1 = c.\) For this example, suppose \(x_1 = b.\)

The next experiment is to assign a value to \(x_2.\) Since \(x_1 = b,\) there are only \(2\) possible outcomes: \(x_2 = a,\) \(x_2 = c.\) Suppose \(x_2 = c.\)

The last experiment is to assign a value to \(x_3.\) Since \(x_1 = b\) and \(x_2 = c,\) the only possible outcomes is \(x_3 = a.\) The permutation is \(b, c, a.\)

There are always \(3\) possible outcomes for \(x_1,\) \(2\) possible outcomes for \(x_2,\) and \(1\) possible outcome for \(x_1.\) By the multiplication rule, the total number of possible outcomes is \(3 \cdot 2 \cdot 1 = 6 = 3!.\)

Since \(A\) as \(3\) elements, there are \(3!\) possible permutations of the elements of \(A.\)

There are \(3! = 6\) permutations of a set with \(3\) elements, \(4! = 24\) permutations of a set with \(4\) elements, \(5! = 120\) permutations of a set with \(5\) elements, \(6! = 720\) permutations of a set with \(6\) elements, and so on. These numbers grow very fast!

If you are permuting a set of elements with identical elements, then you must cancel the repetition. For example, the following lists all permutations of the letters in the word "BALL":

BALL

BLAL

BLLA

ABLL

BLAL

BLLA

ABLL

LBAL

LBLA

ALBL

LABL

LBLA

ALBL

LABL

LLBA

ALLB

LALB

LLAB

ALLB

LALB

LLAB

Claim: You have \(n\) elements, some of which are identitical. We well call the identical elements a type. If there are \(n_1\) elements of type \(a_1\), \(n_2\) elements of type \(a_2,\) and so on to \(n_k\) elements of type \(a_k,\) then the number of permutations is \[\frac{n!}{n_1!n_2!\dots n_k!}\]

▼ Proof:

Number the elements in of each type \(a_i\) as elements \(1\) to \(n_i.\) This way, for every \(i\) the \(n_i\) elements of type \(a_i\) can be distinguished, since they will each have a different number. Since all \(n\) elements can be distinguished, there are \(n!\) permutations.

For a given permutation and a fixed \(i,\) every permutation of the \(n_i\) elements of type \(a_i\) will result in a permutation that will look identical without the numbers. There are \(n_i!\) permutations of the \(n_i\) elements of type \(a_i,\) so the same permutation will be duplicated \(n_i!\) times. Divide by \(n_i!\) to cancel the duplication. This is necessary for every \(i\) from \(1\) to \(k.\)

Example to help understand the proof:

Consider the permutations of the letters \(AABBB.\) There are \(2\) type \(A\) elements and \(3\) type \(B\) elements.

As the proof describes above, we can number the elements so that they can be distinguished: \(A_1A_2B_1B_2B_3.\) There are \(5!\) distinct permutations of \(A_1A_2B_1B_2B_3.\) For example, on such permutation is \[B_1B_3A_2B_2A_1\] Since there \(3\) elements in class \(B,\) there are \(6\) ways the \(B\) elements can be permutated that will result in the same permutation of the original letters.

Similarly, for each permutations of the \(B\) elements, there are \(2!\) permutations of the \(A\) elements. So, there will be \(2!\) duplicates due to the repetition of the \(A\) elements.

Cancel the duplicates to find the total number of permutations: \[\frac{5!}{2!3!} = 10\]

For a given permutation and a fixed \(i,\) every permutation of the \(n_i\) elements of type \(a_i\) will result in a permutation that will look identical without the numbers. There are \(n_i!\) permutations of the \(n_i\) elements of type \(a_i,\) so the same permutation will be duplicated \(n_i!\) times. Divide by \(n_i!\) to cancel the duplication. This is necessary for every \(i\) from \(1\) to \(k.\)

Example to help understand the proof:

Consider the permutations of the letters \(AABBB.\) There are \(2\) type \(A\) elements and \(3\) type \(B\) elements.

As the proof describes above, we can number the elements so that they can be distinguished: \(A_1A_2B_1B_2B_3.\) There are \(5!\) distinct permutations of \(A_1A_2B_1B_2B_3.\) For example, on such permutation is \[B_1B_3A_2B_2A_1\] Since there \(3\) elements in class \(B,\) there are \(6\) ways the \(B\) elements can be permutated that will result in the same permutation of the original letters.

- \(B_1B_3A_2B_2A_1\)
- \(B_1B_2A_2B_3A_1\)
- \(B_3B_1A_2B_2A_1\)
- \(B_3B_2A_2B_1A_1\)
- \(B_2B_1A_2B_3A_1\)
- \(B_2B_3A_2B_1A_1\)

Similarly, for each permutations of the \(B\) elements, there are \(2!\) permutations of the \(A\) elements. So, there will be \(2!\) duplicates due to the repetition of the \(A\) elements.

Cancel the duplicates to find the total number of permutations: \[\frac{5!}{2!3!} = 10\]

Question: If you have \(3\) red balls, \(4\) blue balls, and \(6\) yellow balls, how many ways can you put them in order?

▼ Solution:

The total number of balls is \(3 + 4 + 6 = 13.\)

There are \(3\) classes, red, blue, and yellow, with \(3,\) \(4,\) and \(6\) elements respectively.

Using the formula, the number of ways to put the balls in order is \[\frac{13!}{3!4!6!} = 60,060\]

There are \(3\) classes, red, blue, and yellow, with \(3,\) \(4,\) and \(6\) elements respectively.

Using the formula, the number of ways to put the balls in order is \[\frac{13!}{3!4!6!} = 60,060\]

What are all the permutations of the letters w, x, y, z?

How many ways are there to permute the following letters? \[BANANA\]

How many ways are there to permute the following letters? \[BANANA\]