Probability - Combinatorics

Combinatorics has three parts: Permutations, Variations, and Combinations.

Permutations

Permutations represent the number of different possible ways we can arrange a set of elements.

Example: there are six unique ways the 3 drivers can split the medals (Gold, Silver, and Bronze).

Math Formula:

P_n = n * (n - 1) * (n - 2) * ... * 1 = n!

n!: n factorial

When we determine the available options for every position in a permutation, can we start with the middle element?

Yes, choosing the order is completely up to us.

When dealing with permutation, we can start from any position in the sample space. Convention dictates that we usually start from the first, but we can begin with any element we desire.

Factorials

n!: the product of the natural numbers from 1 to n

or:

n! = 1 * 2 * 3 * ... * n

Factorial important properties:

n! = (n - 1)! * n

(n + 1)! = n! * (n + 1)

(n + k)! = n! * (n + 1) * (n + 2) * . . . * (n + k)

(n - k)! = n! / (n - k + 1) * (n - k + 2) * ... * n

n! / k! = (k + 1) * (k + 2) * ... * n

Variations

Variations are the total number of ways we can pick and arrange some elements of a given set.

Variations with repetition:

Math formula:

V ⁿ_p = n^p

n - the total number of elements we have available

p - the number of positions we need to fill

Example: we have a combination of 2 letters passcode with A, B, and C. The total elements would be 3 - A, B, and C. And total positions would be 2. Thus we will have the variations of this combination is n^p = 3² = 9

In case the combinations of 2 letters passcode with all 26 letters, we will have 26² = 676 variations.

When do we use Variations instead of Permutations?

When we are not arranging all elements in the sample space. We use Variations when we have to first pick and then arrange some (but not all) elements of the sample space.

Going back to the combination lock example from the lecture, imagine the correct code consisted of a single 4-letter word. However, this time the passcode can only consist of letters found in the word “password”. How many possible passcodes are there?

7⁴ - Even though “password” is an 8-letter word, it consists of only 7 distinct letters. That means we have 7 options for each position, so there exist 7⁴ different possible passcodes.

Variations without repetition:

The number of variations without repetition when arranging p elements out of a total of n

Math formula:

Vⁿ_p = n! / (n - p)!

Example: we need to choose 4 members in a team of 5 people to run the relay. The total people are n = 5, and we need to choose p = 4 members when arranging.

We will have V⁵₄ = 5! / (5 - 4)! = 5! / 1! = 120

From the above example, what if instead of 5 people on the team, we had 7. We would still have to choose 4 of them and arrange them in what order to run, but in how many ways can we accomplish that? 

7! / (7 - 4)! = 7! / 3!

What if instead of 5 people on the team, we had 7. Furthermore, this time we also need to pick a reserve player to be on stand-by. (So we need to choose 5 members)

n! / (n - p)!=7! / (7-5)! or simply 7! / 2!.

Imagine you were asked to order a 3-tier cake for your best friend's wedding. They asked you to get a cake with a variety of flavors, so you decide to order different batters (cake flavors)  for each tier. The pastry shop you contacted offers 5 different batters, so you want to know how many distinct options you have for the cake.

We need to pick and arrange 3 of the 5 available flavors. Applying the formula we talked about earlier, we get 5! / (5 - 3)! or 5! / 2! different cakes.

Combinations

Combinations are the number of different ways we can pick certain elements of a set.

What's the number of combinations for choosing p-any elements out of a sample space of n elements?

The number of combinations equals the number of variations, over the number of permutations:

Cⁿ_p = Vⁿ_p / P_p = n! / p!(n - p)!

Example: We need to chooose 3 people in a group of 10 people -> n = 10 and p = 3

We will have C¹⁰₃ = 10! / 3!(10 - 3)! = 10! / 3!7! = 120

The relationship between permutations, variations, and combinations without repetition?

C = V /P - every permutation of a combination is a different variation. Therefore, there are P-times more variations than combinations.

Imagine you are on a trip to Paris and decide to try some of their famous macaroons. The bakery you go to offers different size “variety” packs, where you get to choose 3, 5, or 8 macaroons. The only requirement is that they all be different flavors.

How many different 3-macaroon packs can you get, considering there are 8 distinct flavors.

There are 8 distinct flavors, but we are only getting 3 macarons. Then n is 8 and p is 3, so we plug these values into the formula from this lecture to get n! / p!(n - p)! = 8! / 3!5!.

Now imagine you want to get the medium pack which contains 5 macaroons instead of 3. How many different possible packs can you make?

There are 8 distinct flavors, but we are only getting 5 macaroons. Then n is 8 and p is 5, so we plug these values into the formula from this lecture to get n! / p!(n-p)! = 8! / (5!3!)

Now imagine the same scenario but this time you want the large box of 8 macaroons. How many different variety packs can you get?

If we plug in 8 for both n and p, we get that there are n! / p!(n-p)! = 8! / (8!0!) different variety packs of 8 macrons. Since 0! = 1, 8! / (8!0!) = 8! / 8! , which is just 1. Because we have only 1 way of getting 8 macrons with different flavors considering we only have 8 distinct fillings.

Symmetry of Combinations

Picking more elements can lead to having fewer combinations. We can pick p-many elements in as many ways as we can pick n minus p-many elements.

Cⁿ_p = Cⁿ_{n - p}

Example: From the example above, what if we choose 7 people in a group of 10 people? n = 10 and p = 7

C¹⁰₇ = 10! / 7!(10 - 7)! = 10! / 7!3! = 120

We have the same result as if we choose a group of 3 out of 10. This is the symmetry of combinations.

What is the intuition behind the symmetry of combinations?

Note: We're looking for a statement that explains precisely the mathematical symmetry aspect (i.e. objects equal distance apart, have identical characteristics)

Picking p-many elements out of n is the same as omitting (n - p)-many elements

Combinations with Separate Sample Spaces

A combination can be a mixture of different smaller individual events.

Calculating the total number of combinations is by multiplying the number of options available for each individual event.

How many different burger menus can we order from a McDonald's Restaurant if we have a choice of 8 burgers, 3 sizes of fries, and 5 different drinks, assuming a menu consisting of a burger, some fries, and a drink?

We have 3 positions and we have different-sized sample spaces for each one. We treat the different parts of the menu as positions. For each of the 3 positions, we have a different number of possible choices: 8 for the burgers, 3 for the fries, and 5 for the beverages. Therefore, we have 8×3×5, or 120 different possible menus to chose from.

Want to buy a lottery? Watch the Combinatorics in Real-Life: The Lottery from 365 Careers

Recap of Combinatorics

We use Permutations with Variations when we must arrange a set of objects in such cases of the order.

Permutations are different from Variations is we always arrange the entire set of elements in the sample space.

Example:

• If we need to pick and arrange 4 members in a team of 4 members, we will use Permutations.
• If we pick and arrange 4 members out of 6 members, we need to use Variations
• While Combinations help we pick a group of 4 members in 6 members

Watch again and again the video of "A Practical Example of Combinatorics" to train our analysis mind.

Course's Notes by 365 Careers.