Combinatorial Concepts

Permutations

Formally, a permutation on a sequence is a one-to-one function from the sequence into itself.

Intuitively, that means that a permutation is an ordering, or arrangement, of at least some of the terms of the sequence. The permutations are among all possible strings (codes) that can be formed from terms of the sequence. The strings that are permutations don't include any more repetition of elements than occurs in the sequence itself.

For example, here's a list of the permutations of length 4 of the numbers in the sequence 1, 2, 3, 4:

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2 2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1 3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1 4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

The list above was generated by the odometer method. Perhaps better for illustrating the nature of a permutation as a renaming is method that generates the list by switching adjacent elements in various ways:

1 2 3 4
2 1 4 3
2 4 1 3
4 2 3 1
4 3 2 1
3 4 1 2
3 1 4 2
1 3 2 4 3 1 2 4
1 3 4 2
1 4 3 2
4 1 2 3
4 2 1 3
2 4 3 1
2 3 4 1
3 2 1 4 2 3 1 4
3 2 4 1
3 4 2 1
4 3 1 2
4 1 3 2
1 4 2 3
1 2 4 3
2 1 3 4

Sometimes we wish to list arrangements that don't include all terms of the sequence—strings whose length is less than the number of terms in the sequence. For example, here's a list of all permutations of length 2 from the sequence 1, 2, 3, 4:

1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4

Counting permutations

The permutations themselves are not numbers; they are strings of symbols. But often you want to count the number of such strings.

One way to count all permutations of some sort is through listing them. But making a list takes time. The number of permutations on a sequence can be calculatedwithout this much hassle.

You can imagine making an arrangement of r terms in a sequence of n terms as the process of filling n slots. Then you can use the Fundamental Counting Principle (FCP) to calculate the number of ways of filling those slots.

There are n ways to fill thefirst slot. For each of these n choices, there are n –1 terms that can be placed into the second slot. The FCP says that there are(n)(n – 1) ways of filling these two slots. For eachpossible pair of pair of terms for these two slots, there are n– 2 terms that could go into the third slot. So by FCP there are(n)(n – 1)(n – 2) ways of filling thesethree slots. Continuing in this way, there are

(n)(n – 1)(n – 2). . . (n – r + 1)

length-r permutations of nterms.

If you want the number of permutations of all terms in the sequence, then r = n. The number is

(n)(n – 1)(n – 2). . . (1)

also known as nfactorial, written n!.

The number of length-r permutations of nterms is called the number of permutations ofn used r at a time. It's sometimes denoted by P(n,r) or by _nP_r. In these tours we use the commoncalculator notation of nPr, without subscripts.