Archive | May, 2012

Derivation of the formula for a permutation

21 May

I had a hard time trying to convince myself of the derivation of the formula
nPr = P(n, r) = n!/(n-r)!
After reading and re-reading the read work, here we are:

Since a permutation involves selecting r distinct items without replacement from n items and order is important,

P (n, r) = n.(n-1).(n-2). (n-3) …. (n-r+1)——————————– (1)

Notice the numbers reducing from n until they reach the number (n-r+1). This last term (n-r+1) avoids a zero in case n=r.

Since (n-r)! / (n-r)! = 1, multiplying the right hand side of
Equation (1) by (n-r)! / (n-r)! results in:

P (n, r) = [n.(n-1).(n-2).(n-3)…. (n-r+1)] X (n-r)! / (n-r)!———– (2)

Since (n-r)! = (n-r).(n-r-1)….(3)(2)(1)————————–(3)
Equation (2) becomes:

P (n, r)=[n .(n-1).(n-2)…. (n-r+1)] X [(n-r).(n-r-1)….(3)(2)(1) / (n-r).(n-r-1)….(3)(2)(1)]————————————(4)

A closer look at the numerator of Equation (4) shows that the numbers are reducing from n to 1. Here is the numerator again:
[n .(n-1).(n-2)…. (n-r+1)] X [(n-r).(n-r-1)….(3)(2)(1)

n-1 is 1 less than n and (n-r) is one less than (n-r+1) and so on until 1 which is less than 2 by one.

We can safely conclude therefore that the numerator = n! Since n! =n. (n-1).(n-2)…..(3).(2).(1)

Equation (4)’s denominator (n-r).(n-r-1)….(3)(2)(1) is in effect Equation (3) which equals (n-r)!.

Hence the numerator is n! and the denominator is (n-r)!
Meaning:

nPr = P(n, r) = n!/(n-r)!
Proved

Books I read to arrive at this:

Statistics for Business and Economics- Paul Newbold
Statistics for Business and Economics-Frank Tailoka

Advertisements
%d bloggers like this: