Permutations for GATE Exam

Last Updated: 6th October, 2023

Permutations are a fundamental concept in combinatorics and mathematics that refer to the arrangement of objects in a specific order. In permutations, the order in which objects are arranged is essential and can result in different permutations even when using the same set of objects.

Permutations

The Concept of Arranging Objects in a Specific Order

Let's see in detail:

Order Matters: When arranging objects in a specific order, it means that the arrangement is considered distinct if the order of the objects is different, even if the same set of objects is used. In other words, changing the position of any object within the sequence results in a different arrangement.

Example - Permutations: Let's consider a simple example with three distinct objects: A, B, and C. If you want to arrange these objects in a specific order, such as ABC or BCA, each arrangement is unique because the order of the objects is different. For instance, ABC and BCA are two different permutations because A, B, and C appear in a different sequence.

Applications:

The concept of arranging objects in a specific order has numerous real-world applications. For example:

Example 1: Seating Arrangement Imagine you are organizing a dinner party with five friends: Alice, Bob, Carol, David, and Eve. The way you arrange these friends around the dining table creates different permutations. For instance, if Alice sits next to Bob, Carol is across from David, and Eve is at the head of the table, this seating arrangement is distinct from one where Carol sits next to David, Alice is across from Bob, and Eve is at the foot of the table. In this scenario, permutations represent the various ways your friends can be seated at the table.

Example 2: Password Creation When you create a password for your email, social media, or any online account, the order of characters matters. Consider a simple case where your password consists of four characters: letters (A, B, C, D), numbers (1, 2, 3, 4), and special symbols (!, @, #, $). The permutations of these characters create unique passwords. "A1$B" is a different password from "B$1A" because the order of characters is distinct. Permutations play a crucial role in password security.

Example 3: Lottery Numbers In a typical lottery, a set of distinct numbers (e.g., 1 to 60) is drawn randomly. The order in which these numbers are drawn is essential. For instance, if the winning numbers are 5, 12, 23, 45, and 56, and your ticket has the numbers 12, 5, 23, 45, 56, you win the lottery. However, if the order on your ticket were 5, 12, 23, 56, 45, it would not be a winning combination because the order differs. In this context, permutations represent the different ways the numbers can be drawn.

Key Characteristics of Permutations

Distinct Objects: When arranging distinct objects into permutations, each object is unique, and the order matters. For example, if you have three distinct objects A, B, and C, the permutations ABC and ACB are different because the order of the objects is not the same.

Notation: Permutations are often represented using notation like P(n, r), where "n" represents the total number of objects available, and "r" represents the number of objects to be arranged in a specific order.

Formula: The number of permutations of "n" distinct objects taken "r" at a time can be calculated using the permutation formula:

where,

• P(n, r) represents the number of permutations of "n" distinct objects taken "r" at a time.
• n is the total number of distinct objects available.
• r is the number of objects to be arranged in a specific order.
• n! is the factorial of "n," which is the product of all positive integers from 1 to "n."
• (n - r)! is the factorial of the difference between "n" and "r."

Solved Example: Here are a few examples of permutations:

Permutations of 4 distinct objects (X, Y, Z, W) taken 3 at a time:

XYZ, XZY, YXZ, YZX, ZXY, ZYX, WXY, WYX, WXZ, WZX, WYZ, WZY, XZW, XWZ, YXW, YWX, ZXY, ZYX, WXY, WYX, WXZ, WZX, WYZ, WZY (total of 24 permutations), which can also be calculated as:

n = 4 and r = 3

P(n , r) = (4_3_2*1)/(4-3)! = 24

Exercises:

Example 1: Calculate the number of ways you can arrange 3 different books (A, B, C) on a shelf.

Solution:

Using the permutation formula:

P(3, 3) = 3! / (3 - 3)!

So, there are 6 different permutations for arranging these books.

Exercise 1: Calculate the number of permutations for arranging 4 different-colored balls (Red, Green, Blue, Yellow) in a line.

Solution:

Use the permutation formula with n = 4 and r = 4.

P(3, 3) = 4! / (4 - 4)!

Permutations of Distinct Objects

Permutations of distinct objects refer to arranging objects in a specific order when all objects are unique and different from each other. In this case, the order of arrangement is crucial, and even a slight change in the order results in a distinct permutation.

Example:

Suppose you have three distinct books: Book A, Book B, and Book C. Permutations of these books would include arrangements like:

1. A, B, C
2. A, C, B
3. B, A, C
4. B, C, A
5. C, A, B
6. C, B, A

Each of these arrangements is considered distinct because the order of the books is different.

Permutations of Identical Objects

Permutations of identical objects involve arranging objects when some or all of the objects are identical and indistinguishable from each other. Two key concepts are permutations with repeated objects and the case of distinct objects with repeated permutations.

Formula:

When dealing with permutations of identical objects, you need to account for repeated objects using the following formula:

Number of Permutations = n! / (r1! * r2! * ... * rk!)

Where:

• n! is the factorial of the total number of objects (including repeated ones).
• r1, r2, ..., rk represent the counts of each type of repeated object.

Cases of Repeated Permutations

There are two common cases when dealing with permutations of identical objects:

1. Permutations with Repeated Objects involve arranging objects when you have identical or indistinguishable objects among a set of distinct objects. In this scenario, the order of arrangement is still significant, but you need to account for the fact that some objects are the same. The formula used for permutations with repeated objects is:

Number of Permutations = n! / (r1! * r2! * ... * rk!)

Example:

Consider arranging the letters of the word "MISSISSIPPI." There are 11 letters in total, with repeated letters (M, I, S, S, I, S, S, I, P, P, I). The number of permutations is calculated as:

Number of Permutations = 11! / (1! * 4! * 4! * 2!)

This accounts for the repeated letters, and you'll find that there are 34,650 distinct permutations of the word "MISSISSIPPI."

2. Distinct Objects with Repeated Permutations involve a scenario where you have some distinct objects and want to calculate the number of distinct permutations, taking into account repeated permutations of the same objects. In this case, the repeated permutations of identical objects contribute to the overall count of distinct permutations. The formula used for distinct objects with repeated permutations is:

Number of Permutations = n! / (r1! * r2! * ... * rk!) * (k!)

Where:

• n! is the factorial of the total number of objects (including repeated ones).
• r1, r2, ..., rk represent the counts of each type of repeated object.
• k is the number of distinct objects.

1. Calculate the factorial of 4: 4! = 4 × 3 × 2 × 1 = 24
2. Calculate the factorial of 2: 2! = 2 × 1 = 2
3. Use the formula to calculate the number of permutations:

Solved Example:

Now, imagine you have two identical red balls (R1, R2) and two blue balls (B1, B2). You want to arrange them on a shelf. In this case, the red balls are considered distinguishable, but the blue balls are not.

Let's calculate the number of permutations:

Number of Permutations = 4! / (2! * 2!) * (2!)

Now, let's break it down step by step:

1. Calculate the factorial of 4: 4! = 4 × 3 × 2 × 1 = 24
2. Calculate the factorial of 2: 2! = 2 × 1 = 2
3. Use the formula to calculate the number of permutations:

Number of Permutations = 24 / (2 * 2) * 2 = 24 / 4 * 2 = 6 * 2 = 12

So, there are 12 different permutations for arranging the two distinguishable red balls (R1, R2) and the two indistinguishable blue balls (B1, B2) on the shelf.

Exercise:

Seating Arrangement

Consider organizing a conference with 5 keynote speakers (A, B, C, D, E). You need to arrange them on a panel. You want to calculate the number of different ways the speakers can be seated.

Solution:

Use the permutation formula with n = 5 and r = 5:

P(5, 5) = 5! / (5 - 5)! = 5! / 0! = 5! = 120 ways

So, there are 120 different permutations for arranging the speakers on the panel.

Arranging Letters:

Imagine you want to arrange the letters of the word "BANANA." There are six letters in total, with repeated letters (B, A, N). You want to find the number of different arrangements.

Solution:

Use the permutation formula with adjustments for repetitions:

Number of Permutations = 6! / (1! * 2! * 2!) = 720 / 4 = 180 ways

So, there are 180 different permutations of the letters in the word "BANANA."

1. Calculate the number of permutations for the word "MATH."

Solution:

Since all letters are distinct, you can use the standard permutation formula:

P(4, 4) = 4! = 4 × 3 × 2 × 1 = 24 permutations.

2. Consider the word "BOOKKEEPER." Calculate the number of permutations.

Solution:

You have repeated letters ('O,' 'O,' 'K,' 'E,' 'E').

Now, let's calculate the number of permutations:

Number of Permutations = 10! / (2! * 1! * 2!)

Let's break it down step by step:

1. Calculate the factorial of 10: 10! = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 3,628,800
2. Calculate the factorial of 2: 2! = 2 × 1 = 2
3. Calculate the factorial of 1: 1! = 1
4. Calculate the factorial of 2: 2! = 2 × 1 = 2

Arranging Socks

Suppose you have five pairs of socks, each pair consisting of two identical socks. You want to find the number of ways to arrange them in a row. Each pair is indistinguishable, but pairs of different colors are distinguishable.

Solution:

Use the permutation formula with adjustments for distinguishable and indistinguishable objects:

Number of Permutations = 10! / (2! * 2! * 2! * 2! * 2!) = 72,576 ways

So, there are 72,576 different permutations of the socks.

Arranging Letters

You have the letters 'A,' 'A,' 'B,' 'C.' Calculate the number of permutations when the 'A' letters are indistinguishable, but 'B' and 'C' are distinguishable.

Solution:

To calculate the number of permutations for the letters 'A,' 'A,' 'B,' 'C' where the 'A' letters are indistinguishable, but 'B' and 'C' are distinguishable, we can use the permutation formula for indistinguishable objects with repetitions

Now, let's calculate the number of permutations:

Number of Permutations = 4! / (2! * 1! * 1!)

Let's break it down step by step:

1. Calculate the factorial of 4: 4! = 4 × 3 × 2 × 1 = 24
2. Calculate the factorial of 2: 2! = 2 × 1 = 2
3. Calculate the factorial of 1: 1! = 1
4. Calculate the factorial of 1: 1! = 1

Circular Permutations

Circular permutations refer to the arrangement of objects or elements in a circular fashion, where the order of arrangement matters. In contrast to linear permutations, where objects are arranged in a straight line, circular permutations consider objects arranged in a closed loop or circle. Think of a circular table with seats or a clock with hours - arranging items in such a way that the starting and ending points are not distinct.

Formula for Circular Permutations:

The formula for calculating the number of circular permutations (P) of n distinct objects is:

P=(n−1)!

Where:

• n represents the number of distinct objects to be arranged in a circle.
• ! denotes the factorial of a number, which means multiplying all positive integers from 1 to that number.

Examples:

Let's consider a few examples to illustrate circular permutations:

Example 1: Arrange 4 distinct objects (A, B, C, D) in a circle.

Using the formula: P=(_n_−1)! = (4−1)! = 3!

P=3 × 2 × 1 = 6

So, there are 6 different ways to arrange these 4 objects in a circle.

Example 2: Arrange 5 people (Alice, Bob, Carol, David, Eve) in a circle for a group photo.

Using the formula: P=(_n_−1)! = (5−1)! = 4!

P=4 × 3 × 2 × 1 = 24

There are 24 different ways to arrange these 5 people in a circle.

Exercises:

1. Arrange 6 different colored candles in a circle for a decoration.

Solution:

In this case, you have 6 different candles to arrange in a circle.

Using the formula for circular permutations: P = (_n_−1)! = (6−1)! = 5!

P = 5 × 4 × 3 × 2 × 1 = 120

There are 120 different ways to arrange the 6 colored candles in a circle for decoration.

2. There are 8 students in a circular discussion group. How many different seating arrangements can be made?

Solution:

You have 8 students to arrange in a circle.

Using the formula for circular permutations:

P = (_n_−1)! = (8−1)! = 7!

P = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5,040

There are 5,040 different seating arrangements for the 8 students in the circular discussion group.

3. You have 10 books, and you want to place them in a circular bookshelf. How many arrangements are possible?

Solution:

You have 10 books to arrange in a circle.

Using the formula for circular permutations:

P = (_n_−1)! = (10−1)! = 9!

P = 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 362,880

There are 362,880 different arrangements possible for the 10 books on the circular bookshelf.

4. In a circular race track, 7 horses are participating. How many different orders can they finish the race in?

Solution:

You have 7 horses participating in the race.

Using the formula for circular permutations: P = (_n_−1)! = (7−1)! = 6!

P = 6 × 5 × 4 × 3 × 2 × 1 = 720

There are 720 different orders in which the 7 horses can finish the race on the circular track.

Permutations with Restrictions

Permutations with restrictions involve arranging objects or elements with specific conditions or constraints. These constraints can include placing certain objects in fixed positions, ensuring that specific objects are not adjacent to each other, or satisfying other given conditions. Solving such problems requires adjusting the standard permutation formulas to accommodate the restrictions.

Examples:

Let's discuss some scenarios involving permutations with restrictions:

Example 1: Arrange the letters of the word "MATH" such that the letter 'A' is always at the beginning.

Solution:

In this case, 'A' must be in the first position. We can treat 'A' as a fixed element and then arrange the remaining letters ('M,' 'T,' and 'H').

So, we have three remaining positions for 'M,' 'T,' and 'H.' Using the standard permutation formula, we get:

Number of permutations = 3! (since there are 3 remaining elements) Number of permutations = 3×2×1=6

There are 6 different permutations that satisfy the given condition.

Example 2: Arrange the letters of the word "MISSISSIPPI" such that no two 'I's are adjacent.

Solution:

In this case, we need to arrange the letters while ensuring that 'I' is not adjacent to another 'I.'

Let's treat the 'I's as fixed elements and arrange the remaining letters ('M,' 'S,' 'S,' 'S,' 'P,' 'P'). We'll insert the 'I's into the gaps afterward.

The number of permutations for the remaining letters is 7! since there are 7 remaining elements. Now, we have 8 positions (represented by underscores) for the 'I's:

_M _M _S _S _S _P _P

To arrange the 'I's in non-adjacent positions, we can use combinations. We choose 4 positions out of 8 for the 'I's, which can be calculated as C(8,4).

C(8,4) = 8!/4!4! = 8×7×6×5 / 4×3×2×1 = 70

So, 70 different permutations satisfy the condition of no two 'I's being adjacent.

Exercises:

1. Arrange the letters of the word "BANANA" such that the two 'A's are always together.

Solution:

To solve this, treat the two 'A's as a single element, 'AA.' Now you have four elements ('AA,' 'B,' 'N,' 'N') to arrange.

Using the standard permutation formula: P = 4! / 2!

There are 12 different permutations where the two 'A's are always together.

2. Seat 5 people (A, B, C, D, E) in a row such that A and B must sit together.

Solution:

Consider A and B as a single entity (AB). Now you have four entities ('AB,' 'C,' 'D,' 'E') to arrange.

Using the standard permutation formula: P = 4!

There are 24 different permutations where A and B sit together.

3. Arrange the letters of the word "SUCCESS" such that the two 'S's are not adjacent.

Solution:

First, calculate the total number of permutations of "SUCCESS" without any restrictions: P(total)=7! / 2!

Now, calculate the number of permutations where the 'S's are adjacent. Treat 'SS' as a single entity and arrange the following: 'SS,' 'U,' 'C,' 'C,' 'E.' *P(*adjacent)=5!

Subtract the permutations with adjacent 'S's from the total to get the permutations with non-adjacent 'S's: *P(*non-adjacent) = *P(*total) − *P(*adjacent)

There are 2,400 different permutations where the two 'S's are not adjacent.

4. Place 4 red balls and 3 blue balls in a row such that no two blue balls are adjacent.

Solution:

First, arrange the 4 red balls: R_R_R_R

Now, you have 5 gaps (represented by underscores) between and around the red balls where you can place the blue balls. To ensure that no two blue balls are adjacent, choose 3 gaps out of the 5 to place the blue balls. This can be calculated using combinations: C(5,3) = 5! 3!2!

=10

There are 10 different arrangements that satisfy the condition of no two blue balls being adjacent.

Conclusion

In this lesson, we've covered permutation's fundamental aspects, including distinct and identical objects, circular arrangements, and restrictions. Permutations are vital in combinatorics for arranging objects with order significance. Real-world examples showcased their utility in seating, passwords, and more. We also discussed circular permutations and adapting formulas for restricted permutations, providing a comprehensive understanding of this essential concept.

Key Takeaway

1. Permutations involve arranging objects in a specific order: Permutations are used to calculate the number of ways distinct objects can be arranged when the order of arrangement is significant. Even a slight change in the order results in a distinct permutation.
2. Permutations of identical objects: Permutations of identical objects require considering repeated objects, and the formula for such permutations involves dividing by the factorial of the counts of repeated objects.
3. Circular permutations: Circular permutations deal with arranging objects in a circular fashion, where the starting and ending points are not distinct. The formula for calculating circular permutations is (_n_−1)!, where n is the number of distinct objects.
4. Permutations with restrictions: Permutations with restrictions involve arranging objects while adhering to specific conditions or constraints. Adjust the standard permutation formulas to account for these restrictions, such as fixed positions or non-adjacency.
5. Applications of permutations: Permutations have practical applications in various fields, including seating arrangements, password creation, lottery numbers, and decorative arrangements.
6. Combination principles: Combinations are often used to solve permutation problems with restrictions, such as choosing positions or elements in specific orders.

Practice Questions

1. In how many different ways can the letters of the word 'LEADING' be arranged in such a way that the vowels always come together?

1. 360
2. 480
3. 720
4. 5040

Answer:

Option c

Explanation:

The word 'LEADING' has 7 different letters.

When the vowels EAI are always together, they can be supposed to form one letter.

Then, we have to arrange the letters LNDG (EAI).

Now, 5 (4 + 1 = 5) letters can be arranged in 5! = 120 ways.

The vowels (EAI) can be arranged among themselves in 3! = 6 ways.

Required number of ways = (120 x 6) = 720.

2. In how many different ways can the letters of the word 'CORPORATION' be arranged so that the vowels always come together?

1. 810
2. 1440
3. 2880
4. 50400
5. 5760

Answer:

Option d

Explanation:

In the word 'CORPORATION', we treat the vowels OOAIO as one letter.

Thus, we have CRPRTN (OOAIO).

This has 7 (6 + 1) letters of which R occurs 2 times and the rest are different.

Number of ways arranging these letters = 7!/ 2 = 2520.

Now, 5 vowels in which O occurs 3 times and the rest are different, can be arranged in 5! / 3! = 20 ways

Required number of ways = (2520 x 20) = 50400.

3. In how many ways can the letters of the word 'LEADER' be arranged?

1. 72
2. 144
3. 360
4. 720
5. None of these

Answer:

Option c

Explanation:

The word 'LEADER' contains 6 letters, namely 1L, 2E, 1A, 1D and 1R.

Required number of ways = 6! / ((1!)(2!)(1!)(1!)(1!)) = 360.

4. In how many ways 8 girls and 8 boys can sit around a circular table so that no two boys sit together?

a. (7!)2

b. (8!)2

c. 7!8!

d. 15!

Answer:

(C) 7!8!

Explanation:

First arrange boys or girls on the circle

No of ways to arrange in nplaces around circle= (n-1)!

Here let say first we arrange boys in 8 places= (8-1)=7!

Now in the remaing 8 places we have to arrange girls= 8!

So total ways = 7! * 8!.

5. Five letters A,B,C,D and E are arranged so that A and C are always adjacent to each other and B and E are never adjacent to each other. The total number of such arrangements is a. 24 b. 16 c. 12 d. 32

Answer:

Option a. 24

Explanation:

Number of permutations of

A,B,C,D,E = 5! = 120 ways

Number of permutations of with AC as adjacent

AC(fixed) BDE = 4!2! = 48 ways

But in the above result, we need to subtract the case when BE is together

= AC(fixed) BE(fixed) D = (3!)2!2! = 24 ways

So, total ways required

= 48−24 = 24 ways