Permutation is defined as “All possible arrangement of a collection of things, where the order is important”.
p(n,r) = n!/(n - r)!
I got introduced to this concept in 9th grade and I happily memorized the definition and the formula. I never really understood what is behind this formula.
Later in my life I came across this amazing book ‘Poor Charlie’s Almanack‘ which contained the speech given by Charlie Munger on ‘A Lesson on Elementary, Worldly Wisdom As It Relates To Investment Management & Business’. Excerpt from this book
First there’s mathematics. Obviously, you’ve got to be able to handle numbers and quantities-basic arithmetic. And the great useful model, after compound interest, is the elementary math of permutations and combinations. And that was taught in my day in sophomore year in high school. I suppose by now in great private schools, it’s probably down to the eighth grade or so.
One of the advantages of a fellow like Buffett, whom I’ve worked all these years, is that he automatically thinks in terms of decision trees and the elementary math of permutations and combinations…
If you don’t get this elementary, but mildly unnatural, mathematics of elementary probability into your repertoire, then you go through a long life like a one legged in an ass kicking contest. You’re giving a huge advantage to everybody else.
After reading the above lines I decided to really understand Permutations. I purchased the book “Introduction to Counting and Probability“. Let us do a simple problem now to understand this. Imagine you have 4 Friends(Alice,Bob,Carole and Dan) and you need to invite 2 of them to a party. How many possible ways you can invite them.
|1st Person||2nd Person|
If you add the total number of names in the 2nd Person column it comes to 12 possible ways. Remember from the definition of permutations that order is important. Hence Alice – Bob is different from Bob – Alice and hence they are counted as 2 instead of 1.
To chose the 1st person there are 4 possibilities and for the 2nd person there 3 possibilities. Hence there are 4 * 3 = 12 possibilities
This was easy but still the formula for Permutations looked weird to me.
p(n,r) = n!/(n - r)!
n refers to the number of things to chose from. In our example it is 4.
r refers to how many you can chose from n. In our example it is 2.
n possibilites for the 1st person n - 1 possibilities for the 2nd person . . . (n - r + 1) possibilities for the rth person p(n,r) = n * (n - 1) * (n - 2) * ... * (n - r + 1) p(4,2) = 4 * (4 - 2 + 1) = 4 * 3 = 12
Ok the above formula makes sense but it how is this equal to the one given in the definition.
p(n,r) = n!/(n - r)! n! = n * (n - 1) * ... * (n - r + 1) * (n - r) * (n - r - 1) * ... * 2 * 1 (n - r)! = (n - r) * (n - r - 1) * (n - r - 2) * ... * 2 * 1 p(n,r) = n * (n - 1) * ... * (n -r + 1) *
(n - r) * (n - r - 1) * ... * 2 * 1/ (n - r) * (n - r - 1) * (n - r - 2) * ... * 2 * 1p(n,r) = n * (n - 1) * ... * (n - r + 1)
Aha! They are the same. I do not know why we choose one formula over the other and I do not care as they are the same.
The chapter on Permutations ended with the line