4 Steps to master Permutations and Combinations — Journey in Combinatorics
Well, combinatorics has been quite an interesting subject to talk about, and its ideas are widely applied to a wide range of area: computer science, physics, chemistry and ect. The article serves to help you understand permutations and combinations, two of the most fundamental ideas in a solid way by walking you through 4 steps:
Step 1. Understand multiplication rule with repetition
Imagine you and your friends walked into a haunted house, and there are three places where the ghosts will pop up to scare you. Each of the place will have a ghost, and the available scary characters are Freddy Krueger, Michael Myers, Jason Voorhees. Now, how many different potential three ghosts you are going to experience?
Well, we have three choice at first site, three choice at second site, and three choice at third site. So in total, we will have 3x3x3 = 27 potential ghosts, and this is an example of multiplication rule.
More abstractly, multiplication rule is phrased as following: If there a sequence of events of length M, and each event can have N_i possible outcomes, then the total number of different outcomes for the sequence will be N_1 x N_2 x ….. x N_M.
Now you understand the statements, here is an easy exercise for you: Suppose you will have a fruit after every meal, (assume you have 2 meals today), and you can have unlimited apples, oranges or bananas, how many possible ways you can arrange your fruits after-meal?
Solution: 3x3 = 9. For each meal, we have 3options, and there are two meals.
Step 2. Understand multiplication rule without repetition
Well, now things changed a bit. Suppose we only have 1 apple, 1 orange, and 1 banana. This means once we choose certain fruit to eat, we cannot choose it in the next meal. Then, how many possible fruit after-meals we can get?
Well, think this way. In the first meal, you have all three choices, so you just choose one of them. So, you will have 3 choices for first meal. Then, at second meal, you have already eaten of the three fruits, and that leaves you with two fruits to choose from. So, you only have 2 choices for second meal. Then, using multiplication rules, you will have 3x2=6 possible different ways to arrange your fruits after-meals.
The key difference between with repetition and without repetition is that in without repetition, once we choose a choice, the choice will no longer be available. Despite this difference, the statement of multiplication rule will stay the same.
A simple exercise for you:
Suppose you are in a tennis club with 10 people, and there is a match that requires 5 people to be chosen — from 1st player to play to 5th to play (the order matters). How many ways are there?
Solution:10x9x8x7x6=30240. The first player will have 10 choices, second will have 9 and ect.
Step 3. Understand multiplication rule when order does not matter
In previous setting, there is an assumption that the order of our choice matters. For instance, in the fruit after-meal settings, we assume eating applies at lunch is different than eating apples at dinner, so in which order do we put our choice matters above. The next step is to understand the scenarios when the order does not matter.
Consider the tennis club settings above. This time, rather than choosing people for competition, we choose 5 people to be volunteers for a teaching session for kids. This time, we do not care which player is chosen as the first one and which is the last one. How many possible 5-people volunteering team we can form?
Well, as usual, we have 10x9x8x7x6=30240 outcomes when order matters, but we are over-counting if the order does not matter. Inside the 30240, we count A B C D E (each character represents a person) and A C D B E as two different choices, but now, we would like to group them into a single choice. So, what we need to do is to collapse different ordering on same characters into 1 count. To address this, it is enough for us to consider, how many possible ordering we can have for 5 elements. It sounds like a familiar question, isn’t it? (Refer to step 1). We can have 5x4x3x2x1=120 possible order given 5 fixed elements. Combine things together, we first get 30240 outcomes from step 2, and then to “de-orderfy” we collapse 120 possible different ordering for same 5 elements into 1 count. Therefore, in total, we will have (10x9x8x7x6)/(5x4x3x2x1) = 252 outcomes.
The general way to solve the problem is to use the “choose” syntax. By “choose m of them from n”, (n ≥ m) we mean that the order of the x elements does not matter for us. The answer to “choose m of them from n” is
Step 4. Formalize our ideas into mathematical language
Actually, till this step, you have understood all the ideas and logic behind permutations and combinations. All left to do is to introduce some formal language and operations to make things more compact!
First, let me introduce the operation factorial !. The definition of ! is as follows:
Let n be an integer, n! = n x (n-1) x (n-2) x… 1
Simple exercise, calculate 5!. (Solution: 120)
Combination: combination is just the formal language for question of type “choose m from n”. Its solution in factorial form is
Permutation: question of type choose m from n when order matters. Its solution in factorial form is
Now, you have understood the fundamental concepts and ideas of combinatorics, the next series will be on Pigeonhole principle.