JeffAstor
Statistics

Synthesized Statistics - Permutations and Combinations

undraw svg category

Statistics is tough for me. I’m only ok at math and I never intuitively understand something the first time I hear it. So when I sucked at MIT’s intro to probability course, I took another one from Harvard and synthesized my knowledge of the two together into this series of blog posts. Most of the time, I try and convert the mathematics into code, and that gives me slightly better insight into how things work. Follow along and hopefully you’ll learn something too.

Prerequisite Math

Here’s the part I both simultaneously love and hate. The math is cool because it just works, but if I can’t conceptualize it visually, it takes me a long time to wrap my head around it.

The first thing I had to get comfy with are factorials, and they’re by far the easiest math we deal with. We designate factorials by placing an exclamation point after the number. It end up looking like n!n!.

Turning Math Into Code

n!n! translates pretty evenly into this code block:

Recognize the pattern?

We are essentially counting down from n and multiplying each value by the previous total. Python’s range() function takes three arguments, the starting value, the ending value, and the step. By ending at 1 and using a step of -1, we first multiply total by 3, and then by 2, and then by 1.

If you want to get really terse, you could shorten this to something like this:

Personally, I like the first version better. However, there’s two things here that both functions don’t handle correctly.

First, the math defines the factorial(0) to be 1. Our function would return zero, so we’ll need to account for that. Also, it’s impossible to calculate factorials for a negative nn, so we should handle that more appropriately as well. Doing so might give you something close to this:

That’s not quite as pretty, but it’s functional.

Fortunately, we can check our work by importing the math module and using the built in factorial function.

You’ll notice that the error printed is the same as the one used in our custom function. And you’re right, I stole it.

So why do we need to know all this mathy goodness?

Getting Choosy

Unit 1 in Harvard’s Intro to Probability course covers the math of counting. I enjoyed this section and found examples to be the best way to conceptualize the math. Let me preface this by saying that some forms of counting are easier than others. We’ll start small and build up.

The easiest kind of counting is done when we are looking to sample from a collection of items with replacement. A good example would be choosing a four digit passcode for your smart phone. You can pick 4 numbers, and you’re welcome to use any of those numbers more than once. That’s what with replacement refers to - being able to choose an item from a collection, replace it, and then choose it again.

If you were to count the total number of unique passcodes available, you would get 10410^{4}, or 10,000 possible choices. That’s easy math. As a rule of thumb, when choosing kk items from a collection of size nn with replacement, the formula will always be nkn^{k}.

The next type of counting we’ll learn is how to calculate the number of ways to choose groups of size kk from nn items in a particular order.

This is essentially discussing the number of permutations . Here’s a concrete example for when permutations come into play. We have a deck of 52 cards. How many possible ways can we deal 5 cards?

One example would be the dealer placing down an Ace of spades and a 2 of diamonds on the flop. Then up comes a Queen of hearts, followed by a 7 of clubs, and finally a 10 of diamonds. That’s just one possible outcome, and things start to get out of hand if we try to count every possible permutation by hand.

The answer can instead be found by using the following formula:

P_kn=n!(n−k)!P\_{k}^{n} = \dfrac{n!}{(n-k)!}

So now we know why we need factorials.

Plug in 52 (the number of cards) for nn, and 5 (the group size) for kk. What value do you get?

52!(52−5)!\dfrac{52!}{(52-5)!}

Using our previously defined function, we can calculate the answer as 311,875,200 . Memorize that number and you’ll be super fun at cocktail parties.

If you think about it, what we’re essentially doing is saying that at first we can choose any one of the 52 cards. The next time we deal a card, we can choose any one of the remaining 51 cards, then 50 cards, then 49, and finally 48.

That’s why we divide 52!52! by 47!47!. Neat, huh?

Permutations vs. Combinations

Ok, so what if order doesn’t matter? Well in that case, we’re no longer dealing with permutations.

In general, combinations provide an answer to the question: “How many ways can we create a subset kk out of nn items?“.

We write that out mathematically as (_kn)(\_{k}^{n}).

That looks kinda weird, right? We say this out loud like nn choose kk.

Calculating nn choose kk takes advantage of our previous knowledge about permutations, coupled with the fact that we don’t need to know the order, so we divide that value by k!k!.

Doing so gives us this formula:

(nk)=P_knk!=n!(n−k)!k!=n!(n−k)!k!\displaystyle\binom{n}{k} = \dfrac{P\_{k}^{n}}{k!} = \dfrac{ \dfrac{n!}{(n-k)!}}{k!} = \dfrac{n!}{(n-k)!k!}

Ok, that makes sense. Now what if we wanted to figure out how many distinct 5-card hands we could deal to a given player? Well in this case, the order doesn’t matter, so we’re working with combinations.

So what is 52 choose 5?

52!(52−5)!5!\dfrac{52!}{(52-5)!5!} comes out to 2,598,960 .

NOTE: k!k! here is simply the number of ways we can order kk items. Dividing by this amount makes sense when the order of the items isn’t taken into account.

With those two formulas, we’re well equipped to take on most counting problems. Head over to the MIT or Harvard EdX course and see how you do with their practice problems.

Wrapping Up

Here’s some of the resources I use to think through problems in this category:

Tags:

← Previous Post undraw svg category

Doing Data Science in the Browser

 Next Post →undraw svg category

Conditional Probability and the Monty Hall Game