**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 |

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 |

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 *n*terms.

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 *n*factorial, written *n*!.

The number of length-*r* permutations of *n*terms is called the *number of permutations of n used r at a time.* It's sometimes denoted by P(

Copyright © 1999-2000 SciMathMn