# Combinatorics

---
title: Content
description:
duration: 5400
card_type: cue_card
---

### Content
* Combinatorics
* Permutations
* Permutation : Generic Approach
* Combinations

---
title: Introduction
description:
duration: 5400
card_type: cue_card
---

#### Introduction [3-4 mins]

In today's class, we will be looking at a new topic: Combinatorics

This majorly comprises of 2 topics:

* Arrangement: Permutation
* Selection / Choosing: Combination

We will do that by solving a lot of problems along the way. The goal is to develop a basic understanding of these topics.

These concepts will come in handy in our future classes, when we look at Binomial distribution.

It's going to be a very fun and interactive class.

We will bring the concepts to light using quizzes, and diving deep into their logic, to ensure proper understanding.

With that, let's start. Keep your pen and paper ready!

---
title: Question
description:
duration: 5400
card_type: cue_card
---

Let's start with a very basic question to test our understanding.

> **Suppose we have 2 True/False questions. In how many ways can they be solved?**

For question 1, we have two possible outcomes:

* True
* False

Similarly, for question 2 as well.

**Since we need to solve both questions, will we add or multiply their number of possible outcomes?**

We will multiply since we have to solve question 1 AND 2

Instead, if we had to solve question 1 OR 2, we would've added.

This is because, when considering `Event 1 AND Event 2`, we are talking about two independent events.

Solving question 1 is independent from solving question 2
Hence, we need to multiply to consider their combined effect.

Therefore, we can solve them in $2*2 = 4$ ways:

* True, True
* True, False
* False, True
* False, False

<img src = https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/055/821/original/pc1.png?1699021147 width = 400 height = 400>

Now, let's start solving quizzes, where we will incrementally increase difficulty, whilst learning about new concepts.

---
title: Quiz-1
description:
duration: 60
card_type: quiz_card
---

# Question
India and Pakistan play a 3-match series. How many results are possible (total number of outcomes)?
Note that we consider (Ind, Ind, Pak) different from (Ind, Pak, Ind) etc.

# Choices
- [ ] 6
- [ ] 9
- [x] 8
- [ ] 4

---
title: Explanation Quiz 1
description:
duration: 5400
card_type: cue_card
---

### Explanation for Quiz 1

For each match played between India and Pak, there are 2 possibilities.

* Either India will win
* Or, Pakistan will win

**Now what we do ? Do we add all 2\'s or multiply them to get the answer ?**

Since we need to consider the result for all 3 matches, we will multiply

Therefore, total number of possible outcomes: $222 = 8$

We can also think about this situation by creating a tree/chart.

* After one match , there are 2 possibilities: India or Pak
* The second match will take place AFTER the first one. And it will further have 2 possibilities: Ind or Pak
* Therefore, After the 2nd match there 4 possibilties
* Similarly, after the 3rd match, there are 8 possiblities

So need to 2 x 2 x 2 = 8, to get the result, since the order in which games are won also matters

> **What are the 8 possibilities?**

Suppose $I$ represents India winning, and $P$ for Pakistan wining. Let's list them:
- III
- IIP
- IPI
- IPP
- PII
- PIP
- PPI
- PPP

i.e. 8 possible ways, as we theorized.

Hence, for this setup we can say that for `n` matches, total number of possibilities is $2^n$

<img src = https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/055/822/original/indpa.png?1699021720 width=400 height = "400">

In the world of Cricket, when there is a draw between the teams, the tie is broken through a **bowl-out**

In a bowl-out, the teams need to choose
- 1 bowler, amd
- 1 wicket keeper

... for each ball.

They can have different bowlers/wicket-keppers for each ball.

With this, let's start the second quiz.

---
title: Quiz-2
description:
duration: 60
card_type: quiz_card
---

# Question
In a bowl-out, for a specific ball you have to choose a bowler and a wicket keeper.
Suppose you have 5 bowlers and 3 wicket keepers. How many ways can you select for a ball?

# Choices
- [ ] 8
- [ ] 125
- [ ] 243
- [x] 15
- [ ] 2

---
title: Explanation for Quiz 2
description:
duration: 5400
card_type: cue_card
---

### Explanation for Quiz 2:

We are given that there are 5 bowlers, and 3 wicket-keepers

> In how many ways can we choose a bowler?

5

> In how many ways can we choose a wicket-keeper?

3

> Do we need to choose a `bowler AND wicket-keeper`, or a `bowler OR wicket-keeper`?

AND.

Therefore, total no of ways to select them becomes: $5*3 = 15$

We can also build the chart for this to visualize.
<img src = https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/055/841/original/qui2.png?1699027304 width=500 height = "400">

---
title: Quiz-3
description:
duration: 60
card_type: quiz_card
---

# Question
There are 3 ways to move from Chennai to Bangalore.
There are 4 ways to move from Bangalore to Delhi.

In how many ways can one reach from Chennai to Delhi via BLR?

# Choices
- [ ] 7
- [x] 12
- [ ] 81
- [ ] 64

---
title: Explanation for Quiz 3
description:
duration: 5400
card_type: cue_card
---

### Explanation for Quiz 3:

- There are 3 ways to move chennai to banglore. They may be anything, like:
- Bus
- Train
- Plane
- Similarly, we have 4 ways from Banglore to Delhi.
- Bus
- Train
- Plane
- Bike

> **Do you need to go `from CHN to BGL OR BGL to DL` or `from CHN to BGL AND BGL to DL`?**

We need to go `from CHN to BGL AND BGL to DL`

- This means we 3 x 4 = 12 ways to reach Delhi from Chennai.
<img src = https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/055/842/original/qui3.png?1699027450 width=500 height = "400">

---
title: Quiz-4
description:
duration: 60
card_type: quiz_card
---

# Question
There are 3 ways to move from Chennai to Bangalore, and 4 ways to move from Bangalore to Delhi.
There are 2 ways to move from Chennai to Hyderabad, and 3 ways to move from Hyderabad to
Delhi. In how many ways can we move from Chennai to Delhi?

# Choices
- [ ] 12
- [ ] 6
- [ ] 72
- [x] 18

---
title: Explanation for Quiz 4
description:
duration: 5400
card_type: cue_card
---

### Explanation for Quiz 4:

Given that we want to move from Chennai to Delhi, we can take 2 different routes:
- Via Bangalore
- 3 ways for CHN -> BLR
- 4 ways for BLR -> DEL
- This means that there are $3 x 4 = 12$ ways to reach Delhi from Chennai via Bangalore
- Via Hyderabad
- 2 ways for CHN -> HYD
- 3 ways for HYD -> DEL
- This means that there are $2 * 3 = 6$ ways to reach Delhi from Chennai via Hyderabad.

Hence, if we consider all possible ways to reach DEL from CHN, we get: `Either [CHN -> BLR AND BLR -> DEL] OR [CHN -> HYD AND HYD -> DEL]`

This means that total no of ways to make this travel is: $(3*4) + (2*3) = 18$

We can represent this as a chart as shown below:

<img src = https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/055/843/original/qui4.png?1699027803 width=500 height = "400">

The reason for solving so many questions here, is to ensure that when these things come while studying different Distributions, there would be no doubt.

This lecture is dedicated to clear those fundamentals, and make you comfortable there.

Moving to the next question.

---
title: Quiz-5
description:
duration: 60
card_type: quiz_card
---

# Question
A fast food outlet has the following types of items in their menu:
- Burgers: 3
- Pizzas: 3
- Drinks: 3
- Sandwiches: 5
- Fruits: 7

From these items, you can choose one of the following combos:
- 1 Buger and 1 Sandwhich
- 1 Fruit and 1 Drink
- 1 Pizza

How many different combos can you order ?

# Choices
- [ ] 21
- [ ] 945
- [x] 39
- [ ] 30

---
title: Explanation for Quiz 5
description:
duration: 5400
card_type: cue_card
---

### Explanation for Quiz 5:

<img src = https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/055/844/original/burg.png?1699028348 width=500 height = "400">

To summarize from question, we can order following combos:

One of 3 burgers AND one of 5 sandwiches, OR
One of 7 fruits AND one of 3 drinks, OR
One of 3 pizzas

Therefore
- No of possible Combos of Burger and Sandwhich => 3 x 5 = 15
- No of possible Combos of Fruit and Drink => 7 x 3 = 21
- No of possible Combos of only Pizza => 3

Thus, the Total no of possible combos becomes => $15 + 21 + 3 = 39$

We can represent this as a chart as follows:
- 3 possible burgers
- For each burger, 5 possible sandwiches
- 7 possible fruits
- For each fruit, 3 possible drinks
- 3 possible pizzas

So if we add all these possibilities, we get 39 possible combos.

<img src = https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/055/846/original/burgc2.png?1699028506 width=500 height = "400">

In the questions we've been solving, there are 2 aspects.

Let's understand the distinction between them.

---
title: Permutation and Combination
description:
duration: 5400
card_type: cue_card
---

### Permutation and Combination [5 mins]

The First aspect is **Permutation**

> **What is a permutation?**

- When talking about permutations, we mean **arrangement of objects**
- Therefore, as with arranging objects, the most important thing is **order** is which they are arranged.
- This means that $(i, j) \neq (j, i)$

**Formal Definition:** `A permutation is an arrangement of items or elements in a specific order, where the order of the arrangement matters.`

The second aspect is **Combinations**

> **What is a combination?**

- Combination is **Selection of objects**.
- Over here, the order of objects **does not matter**.
- This means that $(i, j) = (j, i)$

**Formal Definition:** `A combination is selection of items or elements where the order of the arrangement does not matter.`

<img src = https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/055/847/original/acx12.png?1699029444 width=500 height = "400">

We can relate this to the Ind vs Pak series question we solved.

- It is known that any team that wins 2 out of 3 matches, will win the series
- It does not matter in which order, first-second, first-third, anything.
- So this becomes the combination, where the order does not matter.
- In permutation, order matters
- India winning the first 2 matches is different from India winning last 2 matches, i.e. $IIP \neq PII$
- In both cases, Ind is winning the series, but the pattern in which they won can be calculated using permutations.

Let's solve some more questions that will make this distinction between these concepts more clear.

---
title: Quiz-6
description:
duration: 60
card_type: quiz_card
---

# Question
What are the number of ways of ARRANGING three characters A, B and C, such that there is no repitition?

# Choices
- [ ] 3
- [ ] 4
- [x] 6
- [ ] 8

---
title: Explanation for Quiz 6
description:
duration: 5400
card_type: cue_card
---

### Explanation for Quiz 6:
Let's visualize that we have 3 blanks.
- For 1st slot I have three option i.e `A`,`B` and `C`
- Let's say I selected `A` for the 1st slot
- So for 2nd slot I have only 2 option i.e `B` and `C`.
- Suppose we selected `B` for this blank.
- Then, we have only one option left for the third blank, i.e. `C`.

Since we want to arrange the first, second AND the third blank, and we know the number of ways they can be filled,

Total no of ways of arranging = $3*2*1 = 6$

Let's create a chart to visualize this siuation.

Here also, we got 6 possibilities.

Note:
- So basically what did is 3 x 2 x 1 = 6, also called as **factorial** of 3!
- In general, we define factorial of a number n as: $n! = n \times (n-1) \times (n-2) \times ... \times 2 \times 1$
- As a rule, factorial of 0 is defined as: $0! = 1$

<img src = https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/055/852/original/dfw1.png?1699031227 width=500 height = "400">

.
> **How would we solve this question if repetition was allowed?**

By saying that repition is allowed, we mean that we can have all 3 options `A`, `B` and `C` available for use, for each blank.

Therefore
- 3 options for first blank
- 3 options for second blank
- 3 options for third blank

We can create a chart to visualise as shown:

<img src = https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/055/855/original/fre2.png?1699031407 width=500 height = "400">

---
title: Quiz-7
description:
duration: 60
card_type: quiz_card
---

# Question
What is the number of ways of ARRANGING four characters A, B, C and D, without repitition?

# Choices
- [ ] 4
- [ ] 12
- [ ] 16
- [x] 24

---
title: Explanation for Quiz 7
description:
duration: 5400
card_type: cue_card
---

### Explanation for Quiz 7:

This is the same problem we had earlier, just with
- 4 blanks to fill, and
- 4 characters this time

Hence, This would easily become factorial of 4!= 4 x 3 x 2 x 1= 24

<img src = https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/055/856/original/cq7.png?1699031852 width=500 height = "400">

---
title: Quiz-8
description:
duration: 60
card_type: quiz_card
---

# Question
Given 5 different characters, in how many ways can we arrange them in 2 places, without repitition?

# Choices
- [ ] 5
- [ ] 10
- [x] 20
- [ ] 120

---
title: Explanation for Quiz 8
description:
duration: 5400
card_type: cue_card
---

### Explanation for Quiz 8:

**Explanation:**

Note that we have:
- 2 blanks
- 5 characters

i.e. the number of blanks is less than no of characters.

<br>

**Solution:**

Therefore,
- For 1st slot we have 5 options, but once slot is gone, now we only 4 option for 2nd slot
- This imples 5 x 4 = 20

**Discussion:**

In this question, since we were arranging characters, would you agree that the order matters?

Though this question was very easy and dealt with small values. But this would not be feasible to evaluate with large values.

So, we need to have a generic approach to solving these problems.

We got our answer using $5 \times 4$

Let's re-write this in terms of factorial as: $\frac{5 \times 4 × 3×2×1}{3×2×1} = \frac{5!}{3!}$

Further, we define these situations where we want to arrange or permutate elements with the symbol `P`

<br>

Here we put
- 5 characters, into
- 2 blanks

So we can represent this as: $^5P_2$

If we notice the expression we found above, we get the formula: $^5P_2 = \frac{5!}{(5-2)!}$

<img src = https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/055/857/original/wer3.png?1699032234 width=500 height = "400">

---
title: Permutation Generic Formula
description:
duration: 5400
card_type: cue_card
---

### Permutation : Generic Formula [8-9 mins]

Similar to the question above,

> **How would you arrange N object, given that there only 3 slots?**

Since there are 3 slots for `N` objects, the no. of ways in which we can arrange them is $^N P_3$

i.e. $^N P_3 = N . (N-1) . (N-2)$

<img src = https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/055/858/original/bw23.png?1699032365 width=500 height = "200">

.
> **How would you arrange N object, given that there only 4 slots?**

$^N P_4 = N . (N-1) . (N-2) . (N-3)$

<img src = https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/055/859/original/bw2.png?1699032650 width=500 height = "200">

Do you observe a pattern between the no. of slots/blanks, and the last term of the above expressions?

Now, answer this

> **How would you arrange N object, given that there are `k` slots available?**

This can be found using:

$^N P_k = N (N-1) (N-2) (N-3) .... (N-(k-1)) = N (N-1) (N-2) (N-3) .... (N-k+1) $

<br>

Let's re-write this equation by multiplying and dividing by same expression, as:

$^N P_k = N (N-1) (N-2) (N-3) .... (N-(k-1)) = N (N-1) (N-2) (N-3) .... (N-k+1) \times \frac{(N-k)(N-k-1)(N-k-2)....1}{(N-k)(N-k-1)(N-k-2)....1}$

As you know, we can write this in the form of factorial as: $^N P_k = \frac{N!}{(N-k)!}$

<img src = https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/055/860/original/bw24.png?1699032746 width=500 height = "250">

Let's start the next question.

Now that we've studied it, try to solve it using the concepts of Permutations.

---
title: Quiz-9
description:
duration: 60
card_type: quiz_card
---

# Question
There are 4 players P1, P2, P3, and P4 who can play in the top-order batting positions of 1, 2, and 3.
How many arrangements of top-order can we make from 3 of these 4 players, keeping in mind the order in which these batsmen come?

# Choices
- [ ] 12
- [ ] 16
- [ ] 9
- [ ] 4
- [x] 24
- [ ] 48

---
title: Combinations and Explanation for Quiz 9
description:
duration: 5400
card_type: cue_card
---
### Combinations

### and Explanation for Quiz 9:

We can think of it as having
- 3 blanks / batting positions (striker, runner, 1-down batsmen)
- 4 players ($P_1, P_2. P_3, P_4$)

So, we can get the answer by using concept of permutation as: $^4P_3 = \frac{4!}{(4-3)!} = 24$

Let's take a look at these 24 possible arrangements.

<img src = https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/055/861/original/badim.png?1699033121 width=500 height = "300">

#### Discussion / Deeper Analysis [10 mins]:

Let's say
- P1-Sachin,
- P2-Sehwag,
- P3- Rohit, and
- P4- Kohli

<br>

Consider the first column of arrangements here, **do you. notice anything?**
- We can see different arrangements of Sachin ($P_1$), Sehwag ($P_2$) and Rohit ($P_3$)
- But Kohli is not a part of any arrangement in this column.

Similarly, we can notice that for other columns, we basically have grouped arrangements for following groups:
- $P_1, P_2, P_4$
- $P_1, P_3, P_4$
- $P_2, P_3, P_4$

Therefore, we can say that all these groups represent the **SELECTION** of players, in some sense.

<img src = https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/055/862/original/ft1.png?1699033333 width=500 height = "200">

Therefore, when we **don't care about the order** while creating the group.
- We are able to group the 24 arrangements into 4 groups
- That's because we are **SELECTING** 3 players out of the 4 available players.
- And hence, within each of these selected groups, we can have $24/4 = 6$ possible arrangements

> **What exactly is this `6`? Where did it come from?**

Consider any one group, say $P_1, P_2, P_3$

For this group of cricketers, the number of possible arrangements can be found as: $3! = 3 \times 2 \times 1 = 6$

This is exactly what `6` represents.

And, since we have 4 such groups, we get a total of $4 \times 6 = 24$ possible arrangements.

This is exactly what we calculated using permutation formula!!

In the language of combinatorics, this number of ways of **selecting** is known as **Combination**.
- As we already know, order does not matter here.

With context to this question, we write is as: $^4C_3$

And we saw that this is nothing but, $^4C_3 = \frac{^4P_3}{3!}$

Similarly, we can write the **general formula** for combinations in terms of permutations as: $^nC_k = \frac{^nP_k}{k!}$

We can further expand it as: $^nC_k = \frac{n!}{k! (n-k)!}$

<img src = https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/055/863/original/fut3.png?1699033614 width=500 height = "400">

.
Let's practice this concept by looking at a fresh problem.

### Visual Tool [2-3 mins]
> **Instructor Note:**
- Visit this website: https://seeing-theory.brown.edu/compound-probability/index.html#section2
- Here, this tool can help you illustrate the visualization of the above problem.
- Select the number of marbles here as 4.
- This becomes the no of cricketers.
- Then show the visualizations of level 1, 2 and 3, for both permutation and combination

<img src = https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/055/865/original/vtoo.png?1699034030 width=500 height = "250">

### Moving on to the last problem for this class

Car showrooms are generally designed in such a way that they exhibit their new and popular car models on the window in their vibrant colors, in an attempt to attract customers.

---
title: Quiz-10
description:
duration: 60
card_type: quiz_card
---

# Question
A Maruti Showroom has 3 colours in their “Baleno” model and 3 different colours in the “Swift” model.
In how many ways can they place these 6 cars, such that Baleno and Swift are kept in alternate slots?

# Choices
- [ ] 6
- [ ] 36
- [x] 72
- [ ] 216
- [ ] 720

---
title: Explanation for Quiz 10
description:
duration: 5400
card_type: cue_card
---

### Explanation for Quiz 10:
Let's visualise our problem. We need to exhibit 6 cars in the window, such that no two alternate cars are of the same model.

- Let's assume that the first car on the left is Swift
- Here, we can place 3 options
- In the next slot, we again have 3 options of Baleno
- In the next slot, we're left with 2 options of Swift
- ... and so on
- This means we have $3 \times 3 \times 2 \times 2 \times1 \times 1 = 36$ ways of arranging the cars.
- But let's not forget! The first car could've been a Baleno also. Hence,
- We have 3 possible options of Baleno for first slot
- 3 options of Swift for the next
- 2 options of Baleno
- 2 options of Swift
- ... and so on
- This means, we have another $3 \times 3 \times 2 \times 2 \times1 \times 1 = 36$ ways of arranging the cars.

Therefore, total no of ways = $36 + 36 = 72$

<img src = https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/055/866/original/shw1.png?1699034358 width=500 height = "400">

This is how we can use the concepts of arranging and selection to answer tricky questions like this one.

> **How could we have solved this empirically?**

Assuming that we cannot place same models next to each other,
- We need to arrange 3 Swift cars into 3 slots, i.e. $3!$ ways
- AND, we need to arrange 3 Balenos into other 3 slots, i.e. $3!$ ways
- AND, there are 2 different orientations possible to arrange them
1. Left most car is Swift
2. Left most car is Baleno

Therefore, we have a total of $3! \times 3! \times 2! = 72$ ways

<img src = https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/055/867/original/g34.png?1699034478 width=500 height = "400">

---
title: Conclusion
description:
duration: 5400
card_type: cue_card
---

### Conclusion
With this, we wrap up today's class.

Encouraging you to solve the assessments, as this topic can be tricky and problem solving is the only way to make your fundamentals stronger.

From next class, we will be using these concepts to evaluate calculations, as we study about different probability distributions.

Hoping to see you then!