In the previous lab, you defined at a few sample spaces by counting the total number of possible outcomes. This is not very practical when sample spaces grow. In this lab, you'll be introduced to permutations, which will provide a structured way to help you define sample space sizes!
You will be able to:
- Understand how to count permutations, and how factorials are the building blocks of permutations
- Understand how to mathematically derive how many permutations there are for big sets
- Understand how to compute permutations of a subset
- Learn about permutations with replacement and repetition
Let's consider the following example.
The Beyonce tribute band "The Single Ladies" is playing a free mini gig in your local park next week. They have selected three all-time classics: "Drunk in Love", "Crazy in Love" and "Formation", but still have to decide the order they will play the songs in. Knowing this, how many playlists are possible?
It is easy and fairly quick to write down possible orders here:
"Drunk in Love", "Crazy in Love", "Formation"
"Drunk in Love", "Formation", "Crazy in Love"
"Crazy in Love", "Drunk in Love", "Formation"
"Crazy in Love", "Formation", "Drunk in Love"
"Formation", "Drunk in Love", "Crazy in Love"
"Formation", "Crazy in Love", "Drunk in Love"
That's it! When we count the possible outcomes, we get to 6 elements in the sample set. Now what if "The Single Ladies" plays a setlist of 4 songs? or 5? That's where the notion of permutations comes in handy.
The problem setting in general is that, there are
This is a way how you can tackle this. You're the front singer and have to decide which song to play first. You have 3 songs to choose from, so 3 ways of choosing a first song. Then, you move on to the second song. You've chosen the first one, so you have 2 songs to choose from now. Etcetera. Mathematically, this boils down to:
$ \text{# Beyonce permutations} = 321 = 3 ! = 6$
Generalizing this to
Now, lets consider another example. "The Single Ladies" is still playing a concert at central park, but the disagree on the final three songs that they will play. They only get a 12min gig slot, so they really can't play more than 3, yet they have a shortlist of 8 they need to pick from. How many final song selections are possible given this info? As for the first example, the order of the songs played is still important.
When the band members decide on the first song, they have 8 possible songs to choose from. When choosing the second song, they have 7 to choose from. Then for the third song, they have 6 left.
$ \text{# Beyonce k-permutations} = 876 = 336$
formalizing this, the question is how many ways we can select
$n*(n-1)...(n-k+1)$ or in other words,
This is known as a
The idea is here that we only "care" about the order of the first
When talking about setlists, it makes total sense to assume that songs will not be played twice. This is not always how it works though. Imagine a bag with three marbles in it: a green one, a red one, and a blue one. Now we'll draw marbles three times in a row, but each time, we'll write down the marble color and put it back in the bag before drawing again.
Now the number of possible outcomes is
Generalizing this to
When using permutations, some elements may be repeated.
A classic example is using permutations on words. Let's say you have the letters of the word "TENNESSEE". How many different words can you create using these letters?
Simply saying that there are 9 letters so the answer is
The solution is to divide
The answer here is then (9 letters, 4 x E, 2 x N, 2 x S)
The general formula can be written as:
where
Now you're well on your way to calculate all sorts of permutations using factorials - both for understanding the sample space, subsets, etc! Let's move on for some practice!