Theorems on Permutation of Sets

Theorem 1

Suppose S be a set of n elements. Then the number of permutations possible in the set S is n!.

Proof : In constructing a permutation of the set S, we can select the first element in n ways, the second element in n-1 ways whatever the choice of the first element, ... and nth element in n-n+1 ways whatever the choice of the first n-1 elements. By Product Rule the number of permutations of the set S is given by,

n(n-1)(n-2)...1 = n!
[¯]

The above proof uses the product rule. This can also be proved via sum rule. The proof is as follows,
Let S = {a1, a2, ...., an} be a set of n elements . Let f(n) denote the number of permutation of the given n elements with the convention that f(0) = 1, Let Si denote the set of all permutations containing ai as the first element. Then clearly the cardinality of the set Si is f(n-1). Observe that the set of all permutations of the set S is the disjoint union of the sets Si's. So by sum rule we get,

f(n) = n f(n-1)

f(n) = n (n-1) f(n-2)

and proceeding this way and using the fact that f(0) = 1 we get,

f(n) = n!
Theorem 2

For n and r positive integers with r £ n,

P(n,r) = n(n-1)(n-2)...(n-r+1).

Proof : In constructing an r-permutation of an n-element set, we can choose the first item in n ways, the second item in n-1 ways whatever the choice of the first item, ... , and the rth item in n-(r-1) ways whatever the choice of the first r-1 items. By the product rule the r items can be chosen in n(n-1)(n-2)...(n-r+1) ways. [¯]

In the following example we illustrate the concept of permutations.

Example

The number of 4-letter ``words'' that can be formed using each of the letters a, b, c, d, e at most once equals P(5, 4) = 120. The number of 5-letter words equals P(5, 5) = 120.