# Crash Course, Mathematics Permutations and Combinations Part 1

## Permutations and Combinations

Permutations and Combinations is a topic which involves basic counting techniques. We would learn how to calculate number of ways of arranging and selecting a group of objects without listing down all the possibilities.

Example problem:

Find the total number of possible outcomes when 3 coins are tossed at the same time?

## What else you can do inside qs leap ?

### 30 MinPrep Classes

Attend Free GMAT/GRE Prep Classes Everyday

### Virtual One-to-OneMeetings

Listing down all the possibilities: {H, H, H}, {H, H, T}, {H, T, H}, {H, T, T}, {T, H, H}, {T, H, T}, {T, T, H}, {T, T, T}

Where each set represents a possible outcome.

{T, H, T} means 1st coin has Tails, 2nd coin has Heads and 3rd coin has Tails and so on.

Total number of possibilities is 8

Knowledge of Permutations and Combinations allows us to come to the conclusion without making the list. Most of the numbers we work in this chapter are large so it becomes impractical to list down all the possibilities.

This technique is widely used in statistics where we have to deal with data. So it is used everywhere is science and technology.

### Principle of Multiplication (the rule of AND)

Let’s assume a situation in which Luffy the pirate wants to attack Marines headquarters. He has 3 ships AND 2 robots. In how many ways he can choose 1 ship and 1 robot to make the attack.

There are 3 ways in which a ship can be chosen because there are 3 ships. For every choice of ship Luffy has 2 robots.

So total number of ways he can choose 1 ship and 1 robot is 3 x 2 = 6

Let’s call ships as S¬1, S2 and S3 and robots R1 and R2. Our choices are

S1 R1

S1 R2

S2 R1

S2 R2

S3 R1

S3 R2

Total 6 ways to select.

In fundamentals of counting this is called the multiplication principle.

It states that “If there are two events, one of them can occur in p ways while the other can occur in q ways, the total number of ways both 1st and 2nd event can occur is p x q.”

### In general

“If n events, x1, x2, x3, . . . xn can occur in a1, a2, a3 . . . an ways. The total number of ways x1 and x2 and x3 . . . and xn can happen is a1 x a2 x a3 . . . x an .”

### Principle of addition (the rule of OR):

Namrata is going to draw one card from a deck of cards. In how many ways she can draw a king or a queen.

There are 4 kings and 4 queens in a deck. Namrata has to choose either king OR queen she can’t choose both (unlike the previous case where Luffy had to choose one ship AND one robot).

So number of ways of choosing = 4 + 4 = 8

Situation 2:

Namrata has to choose either a Queen or a hearts

We know that there are 4 queens, 13 hearts and there is 1 queen of hearts. So total number of choices would be 4 + 13 – 1 = 16

“In general, if n events x1, x2, x3, . . . xn can occur in a1, a2, a3 . . . an ways respectively and there is no way of two events happening at once the number of ways x1 or x2 or x3 . . . or xn can occur is a1 + a2 + a3 + . . . + an .”

[Similarly, "If there are two events x1 and x2 and they can occur in a1 and a2 ways and there are n ways in which they can occur together. Total number of ways x1 or x2 can occur is a1 + a2 – n.” Warning this second rule of addition should not be extrapolated for n objects!]

## What else you can do inside qs leap ?

### 30 MinPrep Classes

Attend Free GMAT/GRE Prep Classes Everyday

## Permutations:

Permutations simply mean the number of ways of arranging a certain number of objects.

To understand permutations let’s see what are the different types of problems we can encounter.

### Problem type 1. n distinct objects arranged in n different places in a row

How many 7 letter words can be formed by using the letters of the word PRODUCT where repetition is not allowed.

Solution:

We have 7 empty spots to fill with 7 letters.

1st spot can have 7 different letters

2nd spot cannot have the letter we placed on the first spot because repetition is not allowed. So 2nd spot has 6 choices of letters.

Similarly, 3rd spot has 5 choices, 4th spot 4 choices, 5th spot 3 choices, 6th spot 2 choices and 7th spot is left with 1 choice.

Since we have to fill 1st spot AND 2nd spot AND 3rd spot and so on

Multiplication rule will apply (the rule of AND).

Total number of words that can be made using the letters of the word product = 7 x 6 x 5 x 4 x 3 x 2 x 1 = 7!

This solution can be generalised for arrangement of n-objects.

N! is the product of all the integers from 1 through N.

N! = 1 x 2 x 3 x . . . x (N-1) x N

In general number of ways of arranging n DISTINCT objects in n distinct places in a row is n!

Important to remember 0! = 1

Reason why 0! =1? Because 0! Is number of ways of arranging 0 objects. And number of ways of arranging 0 objects is 1; i.e. you don’t arrange them. (this is a crude explanation. Actual proof involves use of what we call a gamma function in statistics. It is one of fundamentals in statistics but is not in the syllabus. Gamma function defines factorials for non-whole numbers i.e. it is generalisation of factorial. If you have any inquiries related to the gamma function you can discuss on official quant group on LEAP. I would be happy to reply.)

### Problem type 2: n distinct objects arranged in r distinct places in a row.

How many ways are there to make 4 letter word with or without meaning from the letters of the word PRODUCE without repetition? (i.e. each letter can appear only once in the word)

We have 4 spots to create a 4 letter word __    __    __    __

Word PRODUCE has 7 distinct characters.

1st spot has 7 choices

2nd spot has 6 choices

3rd spot has 5 choices

4th spot has 4 choices

So total number of words that can be made using 4 letters of the word PRODUCE is = 7 x 6 x 5 x 4

Multiplying and dividing this number by 3 x 2 x 1

= (7 x 6 x 5 x 4 x 3 x 2 x 1) / 3 x 2 x 1

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

The term 7! / (7 – 4)! Is called 7P4

In general, nPr is the number of ways of arranging n different objects in r different places in a row where nPr = n! / (n-r)!

### Problem type 3: How many 4 letter words can be formed by letters of the word PRODUCT with Repetition allowed?

We have four spots to create a 4 letter word __.  __.  __.  __.

1st place has 7 options

Since repetition is allowed second place also has 7 options

Similarly, 3rd and 4th place have 7 options.

So total number of permutations (arrangement of letters or words) =

7 x 7 x 7 x 7 = 74

### Problem type 4 (very important):

We have noticed that in all the above problems the objects we have to arrange are distinct. But what would happen if we have arranged a set of objects in which there are identical sets of objects?

We took the word PRODUCT for arrangements. Notice that each and every letter of the word PRODUCT is different. What would happen if rather than choosing the word PRODUCT we chose the word CAREERS? Both have 7 letters the only difference is in the word CAREERS the letters ‘R’ and ‘E’ are repeated twice.

Let’s compare the two situations with a very basic example:

Situation 1: number of ways of arranging letters of the word AB;

We know that there are 2. AB and BA.

Situation 2: number of ways of arranging letters of the word AA;

There is only 1 way because even if we switch the letters we will get the same word AA.

So if we have non-distinct objects, number of arrangements is reduced because we have to remove similar arrangements.

The problem statement:

Find the number of ways of arranging the letters of the word TREE.

To solve this let’s begin with assuming the word has all distinct letters.

Total number of ways of arranging a 4 letter word is 4! (problem type 1)

But there are two E’s (let’s call them E1 and E2)

The permutation TRE1E2 will be same as TRE2E1 and should be counted as 1

So from 4! We have remove all the possible arrangements of E and E2 that are counted more than once.

Number of ways of arranging E1 and E2 = 2!

Therefore, total number of permutations = 4! / 2!

Alternate Clarification

 If E1 and E2 were distinct If E1 and E2 are same TRE1E2 TREE TRE2E1 TE1RE2 TERE TE2RE1 E1TRE2 ETRE E2TRE1

And so on . . .

We can see that for every 2 arrangements there is only one UNIQUE arrangement that should be counted. Hence actual number of unique permutations = total number of permutations / number of ways E1 and E2 can be arranged among themselves = 4! / 2!

Example 2: Same problem type

Find number of ways to arrange letters of the word CHEESE?

Solution:

Here we see E appears thrice.

Let’s call the three E’s E1, E2 and E3

Total number of ways of arranging the words of letter CHEESE considering E1, E2 and E3 to be different = 6! (problem type 1)

Total number of ways of arranging E1, E2 and E3 = 3!

So number of unique arrangements for the word CHEESE = 6! / 3!

Visualisation:

CHE1E2SE3, CHE1E3SE2, CHE2E1SE3, CHE2E3SE1, CHE3E1SE2, CHE3E2SE1

Are all considered same as CHEESE. We have kept C, H and S at the same spot and arranged E1, E2 and E3. And number of ways of arranging 3 different objects is 3! (just like in the case of previous TREE example every 3! Objects have to be considered as 1)

Generalisation:

Problem: Number of ways of arranging n objects where r1 objects are of 1 kind, r2 objects are of second kind, r3 objects are of 3rd kind and so on . . . then

Total number of unique arrangements possible = n! / (r1! r2! r3! . . .)

Example:

How many ways are there to arrange the letters of the word MISSISSIPPI?

In the word MISSISSIPPI

Total number of letters = 11

“M” occurs 1 time, “I” occurs 4 times, “S” occurs 4 times, “P” occurs 2 times

So total number of unique arrangements = 11! / (1! X 4! X 4! X 2!)

We usually don’t write 1! Because it is equal to 1.

### Important Example:

A binary number x contains a total of n digits and r 1’s. What is the number of ways of arranging the digits of x?

Solution:

A binary number consists of 0s and 1s

Total number of digits in x = n

Total number of 1s in x = r

Hence total number of 0s in x = n – r

So x has r 1s and (n – r) 0s

From previous example we can say that Number of ways of arranging digits in x = n! / r! x (n – r)!

I will be referring back to this example in the article relating to Combinations.

Coming up next week Circular Permutations.

Will post the link once it is up.

Channel Name

GMAT RESOURCES