Permutations


This lesson will establish some notations and formulas which will be frequently used in problems related to counting.

Factorial

The factorial of a natural number n is the product of all natural numbers from 1 to n, that is, the product 1 x 2 x 3 x … x n. This product is denoted as n! (i.e. the number followed by an exclamation mark).

For example 4! = 1 x 2 x 3 x 4 = 24, and 7! = 1 x 2 x 3 x 4 x 5 x 6 x 7 = 5040.

As a convention, zero factorial (0!) is defined to be 1. (I’ll come back to this later). And you needn’t worry about factorial of negative numbers or fractions.

Note that n! = n x (n – 1)! For example 5! can be written as 5 x (4 x 3 x 2 x 1) which equals 5 x 4!

Okay, moving on.

Permutations

The term permutations is used to indicate ordered arrangements of objects. For example, the permutations of the three letters Q, W and E (in a row) are QWE, QEW, WEQ, WQE, EWQ and EQW.

The number of such permutations will be 3 x 2 x 1 = 3! = 6 (We’ve already seen the method of calculation in a previous lesson)

Similarly if we had four objects to be arranged in a row, for example, forming 4-digit numbers (without repetition) using 4, 6, 7, and 9, the number of permutations will be 4 x 3 x 2 x 1 or 4!

This number permutations of objects, taken all at a time (without repetition) is denoted as \( {}^{n}P_n \) or P(n, n). As you can see, this number comes out to be n! (n-factorial)

In case we want the number of 4-digit numbers (without repetition of digits) using the digits 1 to 9, this will be 9 x 8 x 7 x 6.

This number is same as the number of permutations of 9 objects, taken 4 at a time. This is denoted as \( {}^{9}P_4 \) or P(9, 4), which equals 9 x 8 x 7 x 6. The number can be expressed using factorials. If we multiply and divide it by 5 x 4 x 3 x 2 x 1, we get P(9, 4) = (9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1)/(5 x 4 x 3 x 2 x 1) = 9!/5! or 9!/(9 – 4)!. Neat.

We can arrive at a formula now. If we have n different objects, and we have to arrange them in a row, taking r objects at a time, then the number of ways obtained will be n x (n – 1) x (n – 2) x … x (n – r + 1).

This will be equal to n!/(n – r)!, obtained by multiplying and dividing the expression by (n – r)!

The final expression obtained is denoted by \( {}^{n}P_r \) or P(n, r). That is \( {}^{n}P_r \) = n!/(n – r)!

Lesson Summary

  1. The factorial of a natural number n, denoted by n! is equal to 1 x 2 x 3 x … x n. Zero factorial or 0! is defined as equal to 1.
  2. The number of permutations or arrangements of n different objects in a row, taken r at a time is denoted by \( {}^{n}P_r \) which equals n!/(n – r)!

Well, that’s it. Things will get better when you go through examples, which I’ll cover next. See you there.


Leave a comment

One thought on “Permutations