Permutations

Consider a list of objects. Any arrangement of these objects by changing the order in the list is called a permutation. We are interested in the number of possible permutations that can be formed. For this discussion,we need to distinguish between the case where all the objects are different, and the case where some of the objects can be similar (no way to distinguish one object from the other).

All objects are different

We first discuss the case where all objects are different. For example, consider the word TEA (the objects are now the letters T, E, A). The number of possible permutations is $6$:

TEA, TAE, ETA, EAT, AET, ATE

One way to think about forming a new permutation of TEA is to repeatedly take a letter from TEA (without replacement) to form the a new word. So there are $3$ options for selecting the first letter, and for each of those three options there are two options for selecting the second letter, and for all those $3\cdot 2$ options there is $1$ option to select the last letter. So in total we have

or

possible ways to rearrange the word. Using a tree, we can represent this process in an elegant way:

Using the same argument for a word with $6$ different letters, we see that the number of possible words we can form is

or

To summarise:

Some objects are the same

If some of the objects in the list are identical, it is harder to find all the different arrangements, because some of the arrangements will be the same.

Consider, for example, the word TESS. If all letters were different, the number of possible permutations would be $4!=24$, but because some of the letters in the word are the same, some of these $24$ words will also be the same (e.g. switch the last two letters, you get twice the word TESS). In fact, the number of different words you can form is $12$:

TESS, TSES, TSSE, ETSS, ESTS, ESST, STES, STSE, SSTE, SSET, SETS, SEST

So how can we calculate this number? The formula is

The $4!$ in the numerator is the number of words we could form if all letters were different, and because every word is doubled (because of the two Ss), we have to divide by $2=2!$

Let's have a look at the word MISSISSIPPI. The number of different words is

because if all letters were different, there are $11!$ possible words we could form, but there are a factor of $4!\cdot 4!\cdot 2!$ to many words because there are $4$ S, $4$ I, and 2 P. It is not the intention here to prove this formula. But let's discuss in more detail the simplest case where the list contains two different kind of objects.

List with two types of objects

Consider the word

The number of different words we can form is

Let us try to understand why. We start by giving the letters labels, so that we can distinguish them:

The number of possible words we can form now is $7!$. We now form groups: all words which would form the same word if the labels were erased are put into a group. For example, the words

are in the same group, because they form the same word

while the words

are in another group and form the word

The question is now: how many words are there in each group? Well, there are $3!$ possibilities to rearrange the indices of the $A$s, and for each of those possibilities there are $4!$ possibilities to arrange the indices of the $B$s. So in total there must be $3!\cdot 4!$ words in each group. So if we get rid of the indices, each group has $3!\cdot 4!$ too many words. Thus, to eliminate the same words, we have to divide the $7!$ by the $3!\cdot 4!$. And the formula above follows.