One Marble Drawn Is Red and the Other Two Marbles Drawn Are Blue Order of Selection Doesnt Matter

Back to Basics: Part 1

Permutations and Combinations

It seems that no matter how many advanced stats classes I take, or how many times I revisit this topic, permutations and combinations continue to elude me. This post is the first in a series of "Back to Basics" blog posts, which aims to build up the Mathematical foundations of Data Science. The goal of this first post is to help sort out, once and for all, how to choose those pesky marbles from a jar!

Permutations and combinations fall under a branch of Mathematics called Combinatorics. In particular, this is built off of the generalized basic principle of counting, which states that if you run r experiments, with n₁ possible outcomes in the first round, n₂ in the second round, …, nᵣ in the rᵗʰ round, then there are n₁·n₂·…·nᵣ possible outcomes.

Suppose we run an experiment with three rounds, such as choosing marbles from a jar that contains two marbles, red and blue. We choose two marbles each round. How many possible outcomes will there be for the entire experiment?

For the first round, there are two possible outcomes. For each of these two outcomes, there are two possible outcomes for the second round, so 2·2 = 4 possible outcomes. In the third final round, each of the four variations have two more possible outcomes, so 4·2 = 2·2·2=2³ = 8 total possible outcomes.

We can use this general principle to find variations of arranging items from a given set with four criteria. This can be broken into two ways of thinking about arrangements of items from a set of objects: Permutations and combinations. With permutations, order matters. In this case, choosing a red marble and then a blue marble is a distinct outcome from choosing a blue marble and then a red marble. With combinations, order doesn't matter, i.e. the group containing one blue marble and one red marble is the same grouping, regardless of which one was chosen first. With either one, we can either replace the marbles in the jar, or not.

1. Permutations (order matters)

a. WITH replacement

How many ways can we choose two marbles from a jar of three, with replacement, when order doesn't matter? In this first example, there are three ways to choose the first marble, and, for each of those three ways, three more ways to choose the next marble. Following the arrows, there are 9 different possible outcomes, or 3².

If we wanted to replace the marbles and choose a third time, there would be 3·3·3 = 3³ possibilities; with a fourth round, we'd have 3·3·3·3 = 3⁴ possible outcomes, and so on. Generally speaking, there are nʳ ways to choose r objects from a set of n total objects.

b. WITHOUT replacement

How many ordered arrangements of three marbles are there, if we don't put them back in the jar? For the first choice, there are again three options. For any of those three choices, there will be only two options left for the second marble. There will always be only one left for the final marble, and we will be forced to stop choosing after three rounds. So there are 3·2·1 = 6 possible outcomes, or 3!.

What about if we don't intend to choose all of the marbles? Suppose there are 5 marbles in the jar and we will only choose 2 of them. In this case, there are 5 ways to choose the first marble and, since we are not putting it back in the jar, 4 possibilities for the second marble. This is 5·4 = 20 possible combinations. Alternatively, this is the same as the problem above, but "removing" the final rounds where we continued to finish selecting all of the marbles in the jar. So, we can divide out those possibilities and rewrite 5·4 as:

In general, the number of ways to choose r objects from n total objects without replacement is:

2. Combinations (order doesn't matter)

a. WITHOUT replacement

Let's expand on the example above, and consider the number of ways we can choose 2 marbles from five without replacing them in the jar.

We know that when we choose 2 items from a set of 5 objects, there are 5!/(5–2)! possible outcomes. What's new here is the issue of redundancy. Each color pair has one redundant copy (e.g. red+blue = blue+red), so we can divide the number of possibilities by 2·1 = 2!

So, the number of total possibilities is:

Generalizing, the number of ways to make groups of r objects from a total of n objects without replacement (i.e. no repeating items within a group) is equal to:

This is also written using the notation:

b. WITH replacement

How many different groups of 2 can be made from three marbles, with replacement? In this case, the group containing one red and one blue marble is the same as choosing red then blue, or choosing blue then red. As in the previous section, we only care about the final grouping, rather than the order in which each object was selected. But, since we have replacement, there can be repeating colors in each group.

In this case, there are six possible groupings, which we can expand out to get:

Similarly, there are 15 ways to choose 2 marbles from a total of 5, with replacement, when order doesn't matter.

Just as before, we can expand this out to get:

So, in general, the total number of ways to make groups of r objects from a total of n objects, with replacement, when order doesn't matter, is:

Useful formulas

In sum, we have the following rules for the number of possible ways to select r objects from a total of n objects:

I hope you find this post useful next time you are selecting from your lucky jar of marbles, or just prepping for Data Science interviews. Feel free to connect with me or leave thoughts in the comments.

collinsworthevanight.blogspot.com

Source: https://towardsdatascience.com/back-to-basics-part-1-7065c90eae71

Share this post