Permutation Formula Proof

If you have n distinct objects, the number of ways to arrange r of them is,

nPr = n!/(n - r)!

Most people memorize this formula, which is fine, there is nothing wrong with memorizing things, but most books do not prove this.

Let's prove it!


We have n distinct objects, and we want to arrange r of them, hence by the multiplication rule this can be done in,

n*(n-1)*(n-2)*...*(n - (r-1)) ways.

Notice we stopped at r-1 instead of r. To see think of it backwards
n corresponds to 0
n -1 corresponds to 1
n-2 corresponds to 2
.
.
.
n - (r-1) correspoends to r -1

There are exactly r numbers here: 0, 1, 2, 3, ..., r-1.


Ok so now we just need to show that what we have above is the same as n!/(n-r)!.

We can "complete the factorial" if that's a real thing, I think it is, if it's not it should be:)

n*(n-1)*(n-2)*...*(n - (r-1)) =
n*(n-1)*(n-2)*...*(n - r + 1) =
n*(n-1)*(n-2)*...*(n - r + 1)) *[(n- r) * (n - r - 1)) *. . . *3*2*1]/ [(n- r) * (n - r - 1)) *. . . *3*2*1]=
n!/(n-r)!

That's it, we did it!

Hope this has helped someone out there in the world!