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

10 Responses to “Derivation of the formula for a permutation”

  1. amk October 14, 2012 at 16:21 #

    great article… was looking for this!
    There are some minor mistakes … In equations 1 and 2 you have missed (n-1)

    • Byrne March 30, 2013 at 20:58 #

      Thank you for the feedback. (n-1) has been inserted into both equations.

  2. DAWOOD ABBAS February 5, 2013 at 09:37 #

    THIS HELPED ME A LOT TO UNDERSTAND THE CONCEPT OF PERMUTATION AND THE DERIVATION OF ITS FORMULA
    THANKS TO THE AUTHOR

    • Byrne March 30, 2013 at 20:59 #

      You are welcome

  3. Ra§ïkα November 20, 2013 at 12:52 #

    Thanks a lot! You explained the equation 4 numerator so well! 🙂

  4. Kotraiah D M December 1, 2013 at 21:43 #

    Its easy to understand by separating like equations, thank you

  5. Gambit February 22, 2014 at 20:55 #

    This is superbly good, it has helped me so much in my assignment. Thank you so much.

  6. Jayasimha K S May 18, 2014 at 12:14 #

    Excellent step by step derivation. Thank you

  7. Nige May 23, 2014 at 15:31 #

    Thanks for that. All the maths books I could find moved directly from nPr = n(n-1)(n-2)….(n-r+1) to nPr = n!/(n-r)! without explanation, and proving the identity was beyond me. All my books also explain how to get from the second permutation formula to nCr = n!/ (n-r)!r!.

    I wonder why a full explanation of the derevation you elucidate so well is hardly ever given?

  8. pEA June 11, 2015 at 23:29 #

    youre awesome!.. thanks a billion!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: