Numeracy #4: Permutations

Charlie Munger, vice chairman of Berkshire Hathaway, once explained that:

One of the advantages of a fellow like Buffett, whom I’ve worked with all these years, is that he automatically thinks in terms of decision trees and the elementary math of permutations and combinations.

This post will attempt to break down the concept of permutations in a way that makes it more intuitive. The next Numeracy post will attempt to do the same but with Combinations.

History

Permutation refers to the selection and arrangement of things, with the specification that order matters. In 1150, the Indian mathematician Bhaskaraa II noted that:

The product of multiplication of the arithmetical series beginning and increasing by unity and continued to the number of places, will be the variations of number with specific figures.

In the 17th century, Pascal and Fermat began to lay the foundation of probability theory. They were contemplating a gambling problem posed by Chevalier de Mere that pertained to the number of turns required to obtain a six from rolling two dice. Pascal and Fermat exchanged letters, in which they discussed this question and other questions of chance. In the end they formulated the concept of permutation, combination, and probability. This would later come to be known as combinatorics.

Today, combinatorics are widely used for solving problems in probability, genetics, psychology, economics, business and engineering.

Understanding permutations

Imagine we have a combination lock that requires a 3 digit code to be opened. It is important to note that if [1, 2, 3] was the correct code, [3, 2, 1] would not work. Basically, order matters and just figuring the 3 numbers used is not enough. So the question we are trying to solve is: how many different permutations of codes are there? To make things easier, lets assume that each position in the code can only take on the values of 1-3 and no numbers are repeated.

So if we wanted to brute force this, we could simply write down all the combinations:

[1, 2, 3], [1, 3, 2]
[2, 1, 3], [2, 3, 1]
[3, 1, 2], [3, 2, 1]

We get that there are 6 possible permutations for the code. Remember a permutation is simply an arrangement where order matters. But what happens if we change our assumptions so that each position in the code can take on values of 0-9? We could write down all the possibilities again, but this would take a very long time. We need to figure out a mathematical way of expressing this process.

Lets dissect what we were doing in that first example. We have 3 positions that can each take 3 numbers but those numbers can’t be repeated. So for position 1, how many options for its value do we have? There are 3 numbers that could go in position 1. Now for position 2 there are only 2 numbers that could go there, and for position 3, now that we already picked the other two numbers, we are forced to choose whatever number remains.

Position 1: 3 possibilities
Position 2: 2 possibilities
Position 3: 1 possibility

Total Permutations: 3*2*1 = 6

Now, what happens if we go back and try to solve the problem where those 3 positions can take on values of 0-9?

Position 1: 10 possibilities
Position 2: 9 possibilities
Position 3: 8 possibilities

Total Permutations: 10*9*8 = 720

And there you have it, this is the big idea behind permutations. In mathematical speak, the formula for picking r amount of things from n choices is:

nPr = n! / (n-r)!

Just looking at that, it is a lot less intuitive than simply understanding the concept behind it. Ignoring it would probably be in our best interest. But back to our example, that isn’t how combination locks actually work. In reality we can repeat numbers. So using our intuitive understanding of permutations, lets change our assumptions again to allow for repeat numbers like [1,1,1]. Now how many possibilities are there for each position?

Position 1: 10 possibilities
Position 2: 10 possibilities (can repeat position 1)
Position 3: 10 possibilities (can repeat position 1&2)

Total Permutations: 10*10*10 = 1000

What if order doesn’t matter?

What if [1, 2, 3] and [3, 2, 1] would both open the lock? The amount of permutations would be less, but by how much? This is where combinations comes into play. We will talk about combinations in the next Numeracy post. But for now, combinations can be thought of as a subset of permutations. Having the tools of both permutations and combinations at our disposal will allow us to solve some interesting real life problems.

Conclusion

Today, we figured out the number of permutations for cases where repetition is or is not allowed. It is important to remember that permutations are for situations where order matters, and they can be thought of as all the possible ways of doing something.

Combinations are for situations where order doesn’t matter and are all the possible way of doing something divided by redundancies. We will talk about this next week.

The key takeaway from all this is that combination locks are poorly named. Permutation lock would make more sense.

References:
https://en.wikipedia.org/wiki/Permutation
https://www.khanacademy.org/math/probability/probability-and-combinatorics-topic

Advertisements

Author: David Shahrestani

"I have the strength of a bear, that has the strength of TWO bears."

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