Combinatorics - Animation Video
Video Transcript
(0:05)
Combinatorics is a branch of mathematics that deals with counting different arrangements of elements. This may not sound impressive, but it actually has uses in understanding
- Probability
- Graph Theory
- Games of Chance - Poker, Lotteries, and Roulette
(0:21)
The first question that allows us to enter this world is: “How many ways can I arrange unique objects in order?”
(0:29)
We can use the example of a locker filled with textbooks. Let’s say that you have 3 textbooks for 3 different classes, with each textbook being a different color.
(0:39)
How many ways can you arrange them from left to right?
(0:42)
We could simply list out all of the arrangements to find that we have:
- Blue, Red, Green
- Blue, Green, Red
- Red, Blue, Green
- Red, Green, Blue
- Green, Red, Blue
- Green, Blue, Red
(0:59)
We have shown that there are exactly 6 ways to arrange these textbooks. If you don’t believe me, try to come up with another way! This first concept is known as a permutation, or a specific arrangement of some elements.
(1:11)
To calculate a permutation more quickly, we could use a mathematical model to solve our problem. We have 3 textbooks to put in any order. This means that we have 3 positions for them to occur in. We can represent this with 3 slots.
(1:25)
Then, we must consider how many choices we have at each position. For the first textbook, we have 3 choices, the second textbook has 2 choices, and the third textbook has 1 choice.
(1:37)
Simply multiply all of these numbers together to find that 3 × 2 × 1 =6! This is exactly the same answer that we discovered earlier, but with much less effort.
(1:48)
When we think about why this works, we can visualize each decision we make as a separate branch on a tree.
(1:54)
We see that there are 3 choices for the first color, then there are 2 choices for the second color, and we only have 1 choice for the last color.
(2:05)
This is the idea of a factorial, which is written with an exclamation point and is defined by n! = n(n-1)(n-2)...(3)(2)(1).
(2:17)
This means that you simply multiply all of the numbers down to 1. For instance, 5! = 5 × 4 × 3 × 2 × 1 = 120.
(2:29)
However, what if we had 10 textbooks and only enough room for 4 of them in the locker?
(2:34)
This would mean that we have 4 slots, but a different number of choices. It would look like this:
(2:41)
This means we would have 10 × 9 × 8 × 7 = 5,040 different ways of ordering these 10 textbooks.
(2:51)
Slots are a useful method of thinking about this, but let’s try to come up with a formula to describe this!
(2:56)
We start off simply multiplying 10 × 9 × ..., but we have to cut off after we have filled our 4 slots. This is almost like 10!, but we stop once we reach 6.
(3:06)
We can actually achieve this exact same result by dividing 
. If we expand out the numerator and denominator, it becomes clear why. This shows us that we have 
. Notice that since 6 × 5 × 4 × 3 × 2 × 1 is in the numerator and denominator, they cancel out and we are left with 10 × 9 × 8 × 7, which is exactly what we want!
(3:44)
This shows us that a general formula for permutations is 
, where n is the total number of objects and r is the total number of slots. Take a moment to plug in the values for our previous example and verify that this formula works. You may have to rewatch parts of the video to solidify your understanding fully.
(4:08)
The final concept to cover here is combinations, which are almost the same, but occur when the order doesn’t matter. For instance, in the permutations example, we cared about the order of the textbooks in our locker. For a combination, we do not care about the order.
(4:23)
A great example of this is if your parents ask you to choose a group of friends to take to a movie after school. Does the order of your friends matter here? Of course not! It is simply a group of your friends.
(4:36)
This means that if we have Alice, Bob, and Charlie, we count that as the same group as Bob, Charlie, and Alice since they have the exact same people in the group.
(4:45)
Therefore, to calculate the number of combinations we can count the total number of permutations and then divide out how many times we overcount each group. Take a moment to consider that statement and understand what it means.
(4:59)
If you have a group of 7 friends and you are asked to choose 3 of them to go to a movie, calculate the number of permutations there are: 
.
(5:11)
Now, how many ways can you have a group of 3 friends? Well we already answered this! This is the same as the number of ways you can arrange 3 textbooks in order. This is simply 3! = 3 × 2 × 1 = 6.
(5:25)
Divide the number of permutations by the number of times we overcounted each group to find that the number of combinations is 210/6 = 35. There are only 35 combinations of 3 friends from a group of 7.
(5:43)
This formula for combinations can be generalized to 
.
(5:52)
Take your time to rewatch and rederive these formulas for yourself. These concepts and formulas are incredibly difficult for most students, but if you remember where the ideas come from, you’ll have a much easier time understanding them. Most importantly, notice that the only difference between combinations and permutations is the r! in the denominator to fix our “overcounting” problem. This also means that there are always fewer combinations than permutations.
