Math With Nazia: MathWithNaziaa : Permutation And Combination

Permutation and Combination: Permutation and Combination is one of the most important concepts in Mathematics which has practical applications in science, engineering and research. The difference between permutation and combination is that when a set of data is selected from a certain group, it is known as permutation; while the order in which the data is arranged is known as combination. Thus we can say that permutation is ordered combination.

Grouping of data and its interpretation is possible with the help of permutation and combination. Mathematics students should be well versed in the concepts because it finds applications in all advanced research and data analysis. This article provides insight on the permutation and combination questions, solutions, permutation and combination formulas and more. Read the complete article to get complete knowledge of the concepts.

Suppose you have a suitcase with a number lock. The number
lock has 4 wheels each labelled with 10 digits from 0 to 9.
The lock can be opened if 4 specific digits are arranged in a
particular sequence with no repetition. Some how, you have
forgotten this specific sequence of digits. You remember only
the first digit which is 7. In order to open the lock, how
many sequences of 3-digits you may have to check with? To
answer this question, you may, immediately, start listing all
possible arrangements of 9 remaining digits taken 3 at a
time. But, this method will be tedious, because the number
of possible sequences may be large. Here, in this Chapter,
we shall learn some basic counting techniques which will enable us to answer this
question without actually listing 3-digit arrangements. In fact, these techniques will be
useful in determining the number of different ways of arranging and selecting objects
without actually listing them. As a first step, we shall examine a principle which is most
fundamental to the learning of these techniques.

permutation sounds complicated, doesn’t it? And it is. With permutations, every little detail matters. Alice, Bob and Charlie is different from Charlie, Bob and Alice

Combinations, on the other hand, are pretty easy going. The details don’t matter. Alice, Bob and Charlie is the same as Charlie, Bob and Alice.

Permutations are for lists (order matters) and combinations are for groups (order doesn’t matter).

Permutations: The hairy details

Let’s start with permutations, or all possible ways of doing something. We’re using the fancy-pants term “permutation”, so we’re going to care about every last detail, including the order of each item. Let’s say we have 8 people:

1: Alice
2: Bob
3: Charlie
4: David
5: Eve
6: Frank
7: George
8: Horatio

How many ways can we award a 1st, 2nd and 3rd place prize among eight contestants? (Gold / Silver / Bronze)

We’re going to use permutations since the order we hand out these medals matters. Here’s how it breaks down:

Gold medal: 8 choices: A B C D E F G H (Clever how I made the names match up with letters, eh?). Let’s say A wins the Gold.
Silver medal: 7 choices: B C D E F G H. Let’s say B wins the silver.
Bronze medal: 6 choices: C D E F G H. Let’s say… C wins the bronze.

We picked certain people to win, but the details don’t matter: we had 8 choices at first, then 7, then 6. The total number of options was

Let’s look at the details. We had to order 3 people out of 8. To do this, we started with all options (8) then took them away one at a time (7, then 6) until we ran out of medals.

We know the factorial is:

$\displaystyle{ 8! = 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 }$

Unfortunately, that does too much! We only want

. How can we “stop” the factorial at 5?

This is where permutations get cool: notice how we want to get rid of

. What’s another name for this? 5 factorial!

So, if we do 8!/5! we get:

$\displaystyle{\frac{8!}{5!} = \frac{8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 8 \cdot 7 \cdot 6}$

And why did we use the number 5? Because it was left over after we picked 3 medals from 8. So, a better way to write this would be:

$\displaystyle{\frac{8!}{(8-3)!}}$

where 8!/(8-3)! is just a fancy way of saying “Use the first 3 numbers of 8!”. If we have n items total and want to pick k in a certain order, we get:

$\displaystyle{\frac{n!}{(n-k)!}}$

And this is the fancy permutation formula: You have n items and want to find the number of ways k items can be ordered:

$\displaystyle{P(n,k) = \frac{n!}{(n-k)!}}$

Combinations :

Combinations are easy going. Order doesn’t matter. You can mix it up and it looks the same. Let’s say I’m a cheapskate and can’t afford separate Gold, Silver and Bronze medals. In fact, I can only afford empty tin cans.

How many ways can I give 3 tin cans to 8 people?

Well, in this case, the order we pick people doesn’t matter. If I give a can to Alice, Bob and then Charlie, it’s the same as giving to Charlie, Alice and then Bob. Either way, they’re equally disappointed.

This raises an interesting point — we’ve got some redundancies here. Alice Bob Charlie = Charlie Bob Alice. For a moment, let’s just figure out how many ways we can rearrange 3 people.

Well, we have 3 choices for the first person, 2 for the second, and only 1 for the last. So we have

ways to re-arrange 3 people.

Wait a minute… this is looking a bit like a permutation! You tricked me!

Indeed I did. If you have N people and you want to know how many arrangements there are for all of them, it’s just N factorial or N!

So, if we have 3 tin cans to give away, there are 3! or 6 variations for every choice we pick. If we want to figure out how many combinations we have, we just create all the permutations and divide by all the redundancies. In our case, we get 336 permutations (from above), and we divide by the 6 redundancies for each permutation and get 336/6 = 56.

The general formula is

$\displaystyle{C(n,k) = \frac{P(n,k)}{k!}}$

which means “Find all the ways to pick k people from n, and divide by the k! variants”. Writing this out, we get our combination formula, or the number of ways to combine k items from a set of n:

$\displaystyle{C(n,k) = \frac{n!}{(n-k)!k!}}$

Sometimes C(n,k) is written as:

$\displaystyle{\binom {n}{k}}$

which is the the binomial coefficient.

A few examples

Here’s a few examples of combinations (order doesn’t matter) from permutations (order matters).

Combination: Picking a team of 3 people from a group of 10.

Permutation: Picking a President, VP and Waterboy from a group of 10.

.
Combination: Choosing 3 desserts from a menu of 10. C(10,3) = 120.
Permutation: Listing your 3 favorite desserts, in order, from a menu of 10. P(10,3) = 720.

Don’t memorize the formulas, understand why they work. Combinations sound simpler than permutations, and they are. You have fewer combinations than permutations.

Solved Permutation and Combination Problems

Example 1: How many four-digit numbers can be formed from the digits 1, 2, 3, 4, 5, 6 (Repetition of digits not allowed)?

Solution: Thousand's place can be filled in 6 ways. Hundred's place can be filled in 5 ways. Ten's place can be filled in 4 ways. Unit's place can be filled in 3 ways. So, using the Fundamental Principle of Counting, we get the answer as 6 × 5 × 4 × 3 = 360. Or using the formula of Permutations, we need to arrange 4 digits out of total 6 digits. This can be done in ⁶P₄= 360 ways.

Example 2: A person has 6 friends to be invited for dinner through invitation cards, and he has 3 servants. In how many ways can he extend the invitation card?

Solution: We can see that the 1^stfriend has 3 options to receive the card, i.e. either from 1^stservant or 2^ndor 3^rd. Similarly, 2nd friend also has 3 options to receive the card, i.e. either from 1^stservant or 2^ndor 3^rd. So we can say that each of the 6 friends has 3 options to receive the card. Hence the answer would be 3 × 3 × 3 × 3 × 3 × 3 = 3⁶=729 ways.

Example 3: There are 10 questions in an exam. In how many ways can a person attempt at least one question?

Solution: A person can attempt 1 question or 2 questions or .....till all 10 questions. One question out of ten questions can be attempted in ¹⁰C₁= 10 ways. Similarly, two questions out of ten questions can be attempted in ¹⁰C₂= 45 ways. Going ahead by the same logic, all ten questions can be attempted in¹⁰C₁₀= 1 way. Hence the total number of ways = 10 + 45 + 120 +.....10 + 1 = 1023 ways (Using the formula of Combination).

Alternate Method:

Or some logic can be applied: Every question has 2 options, either it is attempted or not. Going ahead with this logic, since there are 10 questions, and each question has 2 options, so total number of cases = 2¹⁰= 1024. But this count includes one case in which no question is attempted. This is the violation of the information given. So this case needs to be subtracted. Hence the total number of cases would be 1024 - 1 = 1023.

An analyst will recommend a combination of 3 industrial stocks, 2 transportation stocks, and 2 utility stocks. If the analyst can choose from 5 industrial stocks, 4 transportation stocks, and 3 utility stocks, how many different combinations of 7 stocks are possible?

Solution

Notice the underlined keywords ‘Choose’ and ‘Combinations’

Now, we can easily identify that this is selection question, right?

The analyst needs to form a different combination of 7 different stocks. Can you visualize how can he do that?

Approach

He needs to select 3 industrial stocks out of 5 industrial stock AND,
He needs to select 2 transportation stocks out of 4 transportation stocks AND,
He needs to select 2 utility stocks out of 3 utility stocks
- Notice the keyword ‘AND’ which indicates all the above 3 events have to occur simultaneously.
- Thus,

difference between permutation and combination GMAT Quant
By the application of nC_r formula, we can write:

3 industrial stocks out of 5 industrial stock can be selected in 5C₃ = 10 ways
2 transportation stocks out of 4 transportation stocks can be selected in 4C₂ = 6 ways
2 utility stocks out of 3 utility stocks can be selected in 3C₂ = 3 ways

Thus, the total ways to select 7 stocks = 10 × 6 × 3 = 180 ways.

Permutation and Combination Definition

Here we have given the mathematical definition of permutation and combination:

What is Permutation?

A permutation is an arrangement in a definite order of several objects taken, some or all at a time, with permutations, every tiny detail matters. It means the order in which elements are arranged is significant.

There are two types of permutations:

Repetition is Allowed: For the number lock example provided above, it could be “2-2-2”.
No Repetition Allowed: For example, the first three people in a race. You can’t be first and second at the same time.

What is Combination?

The combination is a way of selecting elements from a set so that the order of selection doesn’t matter. With the combination, only choosing elements matters. It means the order in which elements are chosen is not essential.

There are two types of combinations:

Repetition is Allowed: For example, coins in your pocket (2,5,5,10,10)
No Repetition Allowed: For example, lottery numbers (2,14,18,25,30,38)

Permutation and Combination Formula

There are many formulas that are used to solve permutation and combination problems. We have provided the complete permutation and combination formula list here:

Permutation Formulas

When repetition is not allowed: P is a permutation or arrangement of r things from a set of n things without replacement. We define P as:

When repetition is allowed: P is a permutation or arrangement of r things from a set of n things when duplication is allowed. We define P as:

Derivation of Permutation Formula:

Let us assume that there are r boxes, and each of them can hold one thing. There will be as many permutations as there are ways of filling in r vacant boxes by n objects.
– No. of ways the first box can be filled: n
– No. of ways the second box can be filled: (n – 1)
– No. of ways the third box can be filled: (n – 2)
– No. of ways the fourth box can be filled: (n – 3)
– No. of ways r^th box can be filled: [n – (r – 1)]

The number of permutations of n different objects taken r at a time, where 0 < r ≤ n and the objects do not repeat is: n(n – 1)(n – 2)(n – 3) . . . (n – r + 1)

⇒ nP_r = n(n – 1)(n – 2)(n – 3). . .(n – r + 1)
Multiplying and dividing by (n – r) (n – r – 1) . . . 3 × 2 × 1, we get:

Combination Formulas

Permutation	Combination
A selection of r objects from a set of n objects in which the order of the selection matters.	The number of possible combinations of r objects from a set on n objects where the order of selection doesn’t matter.
A permutation is used for lists (order matters).	The combination is used for groups (order doesn’t matter).
It denotes the arrangement of objects.	It does not denote the arrangement of objects.
We can derive multiple permutations from a single combination.	Only a single combination can be derived from a single permutation.
They are defined as ordered elements.	They are defined as unordered sets.

Thursday 23 June 2022

MathWithNaziaa : Permutation And Combination