Permutations and Combinations

Podcast Transcript

Whenever there is a lottery, the odds of winning are given.

If you go to a pizzeria, they might tell you the number of possible pizzas that can be made, given their toppings.

If you have a combination lock, it is secured because of the number of different solutions that are possible.

All of these things might seem different, but they are all part of the same branch of mathematics.

Learn more about Permutations and Combinations and how they work on this episode of Everything Everywhere Daily.

If you are not familiar with permutations and combinations, do not fear. It is a subject that isn’t often covered in basic mathematics courses, but it also isn’t that complicated. It involves nothing other than basic multiplication and division.

It doesn’t necessarily even involve fractions or decimals, just whole numbers, and they can be explained using everyday things you are familiar with.

To start this discussion, let’s take a very simple case: how many ways can you arrange the numbers 1,2 and 3?

This is a pretty small number of things, we could just brute force this and write them all out.

There is:

123

132

213

231

312

321

So there are six ways you can arrange the numbers 1, 2, and 3.

Now, let’s say we wanted to do the same thing with 1, 2, 3, and 4.

That suddenly becomes much harder. Not ridiculously hard, but hard enough that you don’t want to listen to me read out strings of numbers for the better part of a minute.

Is there a way we could make a simple formula for calculating this?

There is. Let’s say I have balls numbered 1, 2, 3, and 4 in a hopper and pull them out to create an arrangement.

For the first ball, there are four possibilities because all four balls are in the hopper.

Once I pull that ball out, there are now three possible balls I could select.

Once I pull that ball out, there are now two possible balls left, and then finally, there is only one ball.

So, the total number or arrangements of the numbers one through four can be calculated by multiplying 4 x 3 x 2 x 1 or 24.

In my first example, there were six ways to arrange three numbers, which is equal to 3 x 2 x 1.

If I wanted to calculate the number of ways of arranging five numbers, it would be 5 x 4 x 3 x 2 x 1 or 120.

This calculation where you multiply all of the numbers less than or equal to a given number has a special name and symbol in mathematics, and it is one that you might have encountered if you have used a calculator.

It is called a factorial, and its symbol is an exclamation mark. If you’ve ever played with the factorial key on a calculator, you might have discovered that it is a very easy way to create numbers so large that the calculator can’t handle it.

Factorials are just a shorthand for “multiply together this number and everything below it.”

To give you an idea of how quickly factorial numbers increase, 5! Is 120, 10! Is 3,628,800, 15! 1,307,674,368,000

In fact, the numbers get so large so fast you can arrive at some surprising results.

Take, for example, a deck or ordinary playing cards. There are 52 cards in the deck.

How many different ways can a deck of playing cards be ordered?

This is fundamentally the same problem I addressed above, just with a bigger number. There are 52 possibilities for the first card, 51 for the second card, 50 for the third card, and so on.

The answer is just 52!

52! is a ridiculously large number. It starts with an eight and then has 67 digits after it. There are more ways to shuffle a deck of cards than there are atoms in the entire galaxy!

Assuming you have truly shuffled a deck randomly, that means it is highly probable that the ordering of the cards in your hand is an ordering that has never existed before and will probably never exist again in history.

If you shuffled a deck of cards every second since the universe began, and each shuffle was a different arrangement of cards, you wouldn’t have even come within a trillionth of one percent of all the possible arrangements.

The mathematical term for putting things into a particular order is known as a permutation.

Now let’s go back to my original example of arranging the numbers 1, 2, and 3.

This time let’s assume that numbers can repeat. 123 would be one arrangement, but 113 could be a possibility as well.

This is actually really easy to figure out using the same method we did before.

There are 3 possibilities for the first number, 3 for the second number, and 3 for the third number. The answer is just 3 times 3 times 3 or 27, or to write it more succinctly, 3³.

For four numbers, it would be 4^4, and for five numbers would be 5⁵. These numbers grow even faster than factorials do.

Now let’s consider a different problem, where the order of things doesn’t matter.

Let’s say you go to a pizza place, and they have five different toppings. How many different ways can you make a three-topping pizza, assuming you don’t use any topping more than once?

What makes this problem different from the earlier ones is that the order of the toppings doesn’t matter. A pizza with olives, onions, and pepperoni is the same as one with pepperoni, olives, and onions.

When the order doesn’t matter, this is known as a combination. In mathematical parlance, you would say 5 pick 3.

To solve this problem you first look at the number of ways you can pick three things out of five.

There five possibilities for the first topping, four possibilities for the second topping and three possibilities for the third topping.

However, as I mentioned, the order doesn’t matter, so I’ve actually selected several redundant arrangements by doing this. We can correct for this by dividing that number by the total number of ways you can arrange three things, which is three factorial.

So, the number of three topping pizza combinations out of five, where there are not repeated toppings is 5 x 4 x 3 / 3 x 2 x 1 or 10.

Interesting side note: if you have a combination lock where you have a wheel and need to put numbers is order to open it, it is actually a permutation, not a combination, because the order matters. Technically, combination locks should be called permutation locks.

Lets take this idea of combinations a bit further by looking at something with more numbers that you are probably still familiar with: the lottery.

A typical lottery will involve taking several numbered balls out of a hopper containing as many more balls. As with pizza toppings, the order of the balls doesn’t matter.

Just to use an example that many people listening to this will be familiar with, I’m going to use the Powerball Lottery. This is a large lottery which is played in 45 US states as well as Washington DC, Puerto Rico, and the US Virgin Islands.

The game is played by selecting five numbers from a hopper containing 69 numbers, and then a Powerball is selected from a different hopper containing 26 balls.

First, let’s look at the number of ways five balls can be selected out of 69 balls. Again the order doesn’t matter, so in mathematical parlance, we would say 69 pick 5.

The number of permutations of five balls would be 69 x 68 x 67 x 66 x 65. We could make this a much simpler formula by just saying 69! divided by 64! We get 64 because it is just 69 minus 5.

Again that number contains many redundant combinations, so we divide that number by 5!

The result is 11,238,513 possible five-number combinations out of 69 numbers.

Those are long odds, but they are much better odds than you get in the actual game. That is because there is a sixth number that comes from a separate hopper.

As there are 26 balls in that hopper, and the Powerball number can match one of the other five numbers, we treat it separately and just multiply the previous result by 26.

11,238,513 x 26 = 292,201,338

So, the odds of a single ticket winning is one in 292,201,338, which is exactly what you will find on the Powerball website and on a Powerball ticket.

Here is an interesting question: Why do they bother with a special Powerball? Why not just select six numbers from the main hopper instead of five and get rid of the Powerball?

Take 69! and divided by 63! (again, we get that because we are selecting six numbers out of 69).

We then take the number and divide it by 6! and the number we get is 119,877,472.

If they did it that way, the odds would be more than TWICE as good for players, still astronomical, but still much better.

For most people, six numbers are six numbers. The fact that one of those numbers comes out of a separate hopper doesn’t really seem relevant. However, the designers of Powerball weren’t stupid, and they obviously did the math before they launched the game.

They wanted odds that were long but not too long. There are 330 million people in the United States. Most of them don’t play the lottery every week. That means for any given drawing, and there are two per week, no one will win the jackpot, and the prize will get rolled over to the next drawing.

However, when jackpots get extremely large, they make the news, and more people will play. In fact, mathematically, it might actually make sense to play once the jackpot gets beyond a certain point.

A Powerball ticket costs $2, which means once a jackpot is over $584,402,676, the expected value of a ticket is more than the price of a ticket…..that is, of course, assuming that there is only one winner and the jackpot isn’t split.

So, for a lottery like Powerball, you want the odds to be long but not too long.

We can use the same technique to determine the number of possible five-card combinations out of a deck of cards.

Again, the order doesn’t matter, so it would be 52! divided by 47! and then divide that number by 5!.

The number of possible hands of five cards is 2,598,960. Significantly less than the number of ways to shuffle a deck.

Of those possible hands, there are four that are considered a royal flush, the best hand in poker. So the odds of getting a royal flush are 1 in 649,740.

In the most popular poker game, Texas Hold’em, players have seven cards to make a five-card hand, so the odds aren’t quite the same. The math requires a few more steps, but the odds of a Royal Flush in Texas Hold’em is one in 30,940—exactly 21x better than getting it in the first five cards.

If you play a lot of poker, you might get a royal flush once or twice in your life, or quite possibly, never.

Permutations and combinations are something that most people never encounter as part of a basic mathematics education, but they really aren’t that hard to understand. As I said before, it’s all basic multiplication and division, albeit with very large numbers sometimes.

There are many resources online if it is something you want to learn more about. It is an extremely handy thing to know if you want to be able to calculate the odds of something.

The Executive Producer of Everything Everywhere Daily is Charles Daniel.

The associate producers are Thor Thomsen and Peter Bennett.

I have some Boostagrams for you today. Boostagrams are ways of interacting and supporting the show directly using newer podcast apps that can be found at newpodcastapps.com

The first is from Petar who sent 7777 sats on the Betamax vs VHS episode. He writes:

Nailed it. I remember the extended VHS recording time was huge when trying save money on tapes and the open standard allowed for much greater selection of films at the video rental store. I have such fond memories of those times, renting movies for the weekend. My brother and I would each get to choose 1 and it became kind of a competition of who pick find the better film, on top of all that, the video store gave out free bags of popcorn. Life was good as a kid in the 80s.

Ninja sent 251 sats from the Discovery of Fire episode. They write:

I believe you confused the word “discover” with “invent” at the beginning. The first insinuates the finding of without necessarily creating, and the second implicitly requires creation. In other words, finding a burning stick in the wild is absolutely discovery.

Thanks, pninja, but I’m going to stick with my explanation that the discovery of fire is something so basic, that it might technically be a discovery, but it is like the discovery of air, dirt, or light. So basic that is just part of life, not a discovery that could be attributed to a person, or quite frankly, even a human.

Pninja also sent 251 sats on the episode about the history of wine. They ask:

Was the rice honey wine discovered in China a mead, or simply back-sweetened with honey?

The answer is we don’t know. The evidence was gathered from molecular analysis of ancient pottery fragments. They could detect trace materials on it, but it isn’t possible to determine much beyond that. In the research I did, it was described as a proto-wine. It might have been more of a mead with fruit, or it could have been more of a wine with honey.

Remember, if you leave a review or send me a boostagram, and my node is back up and working so I can actually accept boostagrams again, you too can have it read on the show.