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

[__¯__]

The above proof uses the product
rule. This can also be proved via sum rule. The proof is as follows,

Let S = {a_{1}, a_{2},
...., a_{n}} 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 S_{i} denote the set of all permutations containing a_{i}
as the first element. Then clearly the cardinality of the set S_{i}
is f(n-1). Observe that the set of all permutations of the set S is the
disjoint union of the sets S_{i}'s. So by sum rule we
get,

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

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

*For n and r positive integers
with r £ n,*

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.