Permutations and Combinations for GATE Exam

Last Updated: 16th October, 2023

Permutations and combinations are fundamental concepts in probability theory and are used to calculate the number of possible outcomes and favorable outcomes in various scenarios. They play a crucial role in determining the probability of events.

Permutations

A permutation is an arrangement of objects in a specific order. For example, arranging the letters A, B, and C in different orders such as ABC, ACB, BAC, etc.

In probability, permutations are used when the order of events or objects matters. For instance, when dealing with arrangements or sequences.

The number of permutations of n distinct objects taken r at a time is denoted as P(n, r) or nPr and is calculated as:

P(n, r) = n! / (n - r)!

Where:

• n is the total number of objects.
• r is the number of objects taken at a time.
• "!" denotes factorial, which is the product of all positive integers from 1 to the given number.

Example: If you have 5 students and you want to arrange 3 of them in a row, the number of permutations is P(5, 3) = 5! / (5 - 3)! = 60.

Combinations

A combination is a selection of objects without regard to the order. For example, choosing 2 out of 5 students to form a study group, where the order in which they are chosen doesn't matter.

The number of combinations of n distinct objects taken r at a time is denoted as C(n, r) or nCr and is calculated as:

C(n, r) = n! / [r!(n - r)!]

Where:

• n is the total number of objects.
• r is the number of objects chosen at a time.
• "!" denotes factorial, as explained earlier.

Example: If you want to select 2 students out of 5 to form a study group, the number of combinations is C(5, 2) = 5! / [2!(5 - 2)!] = 10.

How they are used in Probability?

Permutations in Probability:

• Permutations are used when calculating the probability of specific sequences or ordered events. For example, the probability of drawing a certain sequence of cards from a deck or the probability of a specific order of outcomes in a race.

Example: Suppose you have a standard deck of 52 playing cards, and you want to find the probability of drawing a straight flush, which is a sequence of five consecutive cards of the same suit (e.g., 8, 9, 10, Jack, Queen of hearts).

1. First, calculate the total number of favorable outcomes (straight flushes):
   • There are 4 suits in a deck (hearts, diamonds, clubs, spades).
   • For each suit, there are 10 possible straight flushes (e.g., A, 2, 3, 4, 5 of hearts; 2, 3, 4, 5, 6 of hearts, and so on).
   • So, there are a total of 4 suits × 10 straight flushes = 40 favorable outcomes.
2. Next, calculate the total number of possible outcomes:
   • There are 52 cards in the deck, and you're drawing 5 of them.
   • So, the total number of possible outcomes is the number of ways to choose 5 cards from 52 cards, which is a permutation: P(52, 5).
3. Now, you can calculate the probability of drawing a straight flush:

Probability = (Number of Favorable Outcomes) / (Number of Possible Outcomes) Probability = 40 / P(52, 5)

Probability = 40 / 311875200

Combinations in Probability:

• Combinations are used when the order of events or objects doesn't matter in a probability problem. For instance, when calculating the probability of getting a certain number of heads when flipping coins or the probability of drawing a certain combination of cards regardless of their order.

Example: Let's consider a simpler example involving combinations. You have a bag containing 12 marbles, 5 of which are red, 3 are blue, and 4 are green. You want to find the probability of drawing 2 red marbles without replacement.

1. Calculate the total number of favorable outcomes (drawing 2 red marbles):
   • You want to choose 2 red marbles from the 5 available. This is a combination: C(5, 2).
2. Calculate the total number of possible outcomes:
   • You're drawing 2 marbles from a total of 12, which can be calculated as a combination: C(12, 2).
3. Now, calculate the probability of drawing 2 red marbles:

Probability = (Number of Favorable Outcomes) / (Number of Possible Outcomes) Probability = C(5, 2) / C(12, 2)

Probability = 10 / 66

Probability of an Event:

Probability is a measure of the likelihood of an event occurring. It's expressed as a number between 0 and 1, where:

• Probability = 0 means the event is impossible.
• Probability = 1 means the event is certain.
• Probability between 0 and 1 represents the likelihood of the event occurring, with higher values indicating a greater likelihood.

The probability of an event A, denoted as P(A), is calculated as:

• P(A) = (Number of Favorable Outcomes) / (Total Number of Possible Outcomes)

In simple terms, it's the ratio of the number of successful outcomes (favorable to the event) to the total number of possible outcomes.

Example: What is the probability of getting heads when tossing a fair coin?

1. Define the Event:

Event A: Getting heads when tossing a fair coin.

2. Calculate the Number of Favorable Outcomes:

There is only one favorable outcome for this event, which is getting heads (H).

3. Calculate the Total Number of Possible Outcomes:

When tossing a fair coin, there are two possible outcomes: heads (H) and tails (T).

4. Calculate the Probability:

Probability of getting heads (P(A)) = (Number of Favorable Outcomes) / (Total Number of Possible Outcomes) Probability of getting heads (P(A)) = 1 (favorable outcome) / 2 (total possible outcomes) Probability of getting heads (P(A)) = 1/2

So, the probability of getting heads when tossing a fair coin is 1/2, which means there is a 50% chance of getting heads on a single coin toss.

Independent Events:

Two events, A and B, are considered independent if the occurrence (or non-occurrence) of one event doesn't affect the probability of the other event. In other words, the probability of both events happening together is the product of their individual probabilities.

Mathematically, events A and B are independent if:

• P(A ∩ B) = P(A) * P(B)

Where,

• P(A ∩ B) represents the probability of both events A and B happening together.
• P(A) represents the probability of event A.
• P(B) represents the probability of event B.

For example, when flipping a fair coin twice, the outcomes of the first flip do not affect the outcomes of the second flip. So, the events "getting heads on the first flip" and "getting tails on the second flip" are independent.

Example: Consider rolling a fair six-sided die twice. Let's determine if the events "rolling a 4 on the first roll" and "rolling a 3 on the second roll" are independent.

1. Event A: Rolling a 4 on the first roll.
   • Probability of rolling a 4 on a fair six-sided die (P(A)) = 1/6 (since there is 1 favorable outcome out of 6 possible outcomes).
2. Event B: Rolling a 3 on the second roll.
   • Probability of rolling a 3 on a fair six-sided die (P(B)) = 1/6 (again, 1 favorable outcome out of 6 possible outcomes).

Now, let's calculate the joint probability of both events occurring, P(A and B), and see if it matches the product of their individual probabilities, P(A) * P(B).

• P(A and B) = P(A) * P(B)
• P(A and B) = (1/6) * (1/6)
• P(A and B) = 1/36

Since P(A and B) = 1/36, and it matches the product of their individual probabilities (P(A) * P(B)), it confirms that the events "rolling a 4 on the first roll" and "rolling a 3 on the second roll" are independent events when rolling a fair six-sided die twice. The outcome of the first roll does not affect the outcome of the second roll.

Mutually Exclusive Events:

Two events, A and B, are considered mutually exclusive (or disjoint) if they cannot both occur at the same time. In other words, if event A happens, then event B cannot happen simultaneously, and vice versa.

Mathematically, events A and B are mutually exclusive if:

• P(A ∩ B) = 0

This means that the probability of both events occurring together is zero.

For example, when rolling a six-sided die, the events "getting an even number" and "getting an odd number" are mutually exclusive because it's impossible to roll a number that is both even and odd at the same time.

Example: Consider drawing a single playing card from a standard deck of 52 cards. Let's determine if the events "drawing a heart" and "drawing a spade" are mutually exclusive.

1. Event A: Drawing a heart.
   • Number of hearts in a standard deck = 13 (there are 13 cards in the heart suit).
   • Probability of drawing a heart (P(A)) = (Number of Hearts) / (Total Number of Cards) = 13/52 = 1/4.
2. Event B: Drawing a spade.
   • Number of spades in a standard deck = 13 (there are 13 cards in the spade suit).
   • Probability of drawing a spade (P(B)) = (Number of Spades) / (Total Number of Cards) = 13/52 = 1/4.

Now, let's calculate the probability of either event A or event B occurring, P(A or B), and see if it equals the sum of their individual probabilities, P(A) + P(B).

• P(A or B) = P(A) + P(B)
• P(A or B) = (1/4) + (1/4)
• P(A or B) = 2/4
• P(A or B) = 1/2

Since P(A or B) = 1/2, and it equals the sum of their individual probabilities (P(A) + P(B)), it confirms that the events "drawing a heart" and "drawing a spade" are mutually exclusive when drawing a single card from a standard deck. This means you cannot draw both a heart and a spade at the same time; they are distinct and separate outcomes.

Understanding these concepts is crucial for solving various probability problems and making informed decisions in situations involving uncertainty. Whether events are independent or mutually exclusive has a significant impact on probability calculations and predictions.

Exercises:

1. Suppose you have a standard deck of 52 playing cards. What is the probability of drawing a red card (hearts or diamonds) at random?

Solution

Number of Favorable Outcomes (Red Cards): There are 26 red cards in the deck (13 hearts and 13 diamonds).

Total Number of Possible Outcomes (All Cards): There are 52 cards in total.

Probability (P(Red Card)) = (Number of Red Cards) / (Total Number of Cards) Probability (P(Red Card)) = 26 / 52 Probability (P(Red Card)) = 0.5

2. Suppose you have a fair six-sided die (with numbers 1 to 6) and a standard deck of 52 playing cards. You roll the die and draw a card from the deck. Are the events of rolling a 3 on the die and drawing a spade from the deck independent?

Solution

Probability of Rolling a 3, (P(Rolling a 3)) = 1/6 (since there is 1 favorable outcome out of 6 possibilities).

Probability of Drawing a Spade, (P(Drawing a Spade)) = 13/52 (since there are 13 spades out of 52 cards).

Now, check if they are independent:

P(Rolling a 3) * P(Drawing a Spade) = (1/6) * (13/52) = (1/6) * (1/4) = 1/24

The product of the individual probabilities is equal to the joint probability:

P(Rolling a 3 and Drawing a Spade) = 1/24

3. Suppose you have a bag containing 10 red marbles and 8 blue marbles. What is the probability of drawing either a red marble or a blue marble (but not both) from the bag?

Solution

Number of Favorable Outcomes (Red or Blue Marble): There are 10 red marbles and 8 blue marbles.

Total Number of Possible Outcomes (All Marbles): There are 18 marbles in total.

Probability (P(Red or Blue Marble)) = (Number of Red or Blue Marbles) / (Total Number of Marbles) Probability (P(Red or Blue Marble)) = (10 + 8) / 18 Probability (P(Red or Blue Marble)) = 18 / 18 Probability (P(Red or Blue Marble)) = 1

4. Suppose you have a deck of 5 cards labeled A, B, C, D, and E. You want to know the probability of drawing two cards in a specific order, say, A followed by B, without replacement.

Solution

Calculate the number of favorable outcomes (getting "A, B" in that order):

There are 5 ways to choose the first card (A, B, C, D, E), and after you've chosen the first card, there are 4 remaining cards to choose from for the second card (excluding the one you've already chosen). So, there are 5 * 4 = 20 favorable outcomes.

Calculate the total number of possible outcomes:

When drawing two cards from 5 cards without replacement, you can calculate this as a permutation: P(5, 2).

P(5, 2) = 5! / (5 - 2)! = 5! / 3! = (5 * 4 * 3!) / 3! = 20

Calculate the probability:

Probability = (Number of Favorable Outcomes) / (Total Number of Possible Outcomes) 

Probability = 20 / 20 

Probability = 1

So, the probability of drawing "A, B" in that specific order is 1.

5. Consider a bag containing 6 red marbles and 4 blue marbles. You want to find the probability of drawing two marbles randomly without replacement and getting exactly one red marble and one blue marble.

Solution

Calculate the number of favorable outcomes (getting one red and one blue marble):

• Choose 1 red marble from 6: C(6, 1) = 6
• Choose 1 blue marble from 4: C(4, 1) = 4
• Multiply these to count the favorable outcomes: 6 * 4 = 24

Calculate the total number of possible outcomes:

When drawing two marbles from 10 (6 red + 4 blue) without replacement, you can calculate this as a combination: C(10, 2).

C(10, 2) = 10! / [2!(10 - 2)!] = (10 * 9) / (2 * 1) = 45

Calculate the probability:

Probability = (Number of Favorable Outcomes) / (Total Number of Possible Outcomes) 

Probability = 24 / 45

You can simplify this fraction further if needed, but this is the probability of drawing exactly one red and one blue marble.

Counting Principles:

Counting principles are fundamental techniques used in combinatorics, which is the branch of mathematics that deals with counting and arranging objects or elements. Counting principles provide systematic methods for determining the total number of possible outcomes in various situations. Two important counting principles are the Multiplication Principle and the Addition Principle:

Multiplication Principle (or Multiplication Rule):

The Multiplication Principle is used when you want to find the total number of outcomes for a sequence of events or choices. It states that if there are 'n' ways to perform one task and 'm' ways to perform another task independently of the first task, then there are 'n * m' ways to perform both tasks together.

Mathematically, it can be expressed as:

Total Number of Outcomes = (Number of Ways for Task 1) * (Number of Ways for Task 2)

This principle is particularly useful for scenarios where you have a series of choices or events occurring one after the other.

Example: If you have 3 different shirts and 4 different pairs of pants, you can find the total number of outfits by multiplying the number of choices for shirts (3) by the number of choices for pants (4), giving you 3 * 4 = 12 possible outfits.

Addition Principle (or Addition Rule):

The Addition Principle is used when you want to find the total number of outcomes for events that can occur in mutually exclusive ways. It states that if there are 'n' ways to perform one task and 'm' ways to perform another task, but the tasks cannot be performed together (i.e., they are mutually exclusive), then there are 'n + m' ways to perform either task.

Mathematically, it can be expressed as:

Total Number of Outcomes = (Number of Ways for Task 1) + (Number of Ways for Task 2)

This principle is often applied when there are two or more separate cases, and you want to find the total number of outcomes by adding up the possibilities for each case.

Example: If you want to find the total number of ways to travel from point A to point B by either walking (2 ways) or biking (3 ways), you can use the Addition Principle to determine that there are 2 + 3 = 5 ways in total.

Counting principles are foundational in combinatorics and are used to solve a wide range of problems related to counting and probability, including permutations, combinations, and more complex scenarios involving multiple choices and events. They provide a structured approach to determining the number of possible outcomes in various situations.

Example: Suppose you need to create a 3-digit code using the digits 0 to 9. However, there are some constraints:

1. The code cannot start with 0 (so the first digit cannot be 0).
2. No digit can be repeated in the code.

Let's find out how many different valid 3-digit codes can be created following these rules.

Solution

Using the Multiplication Principle:

1. Choosing the First Digit:
   • There are 9 choices for the first digit (1 through 9, as 0 cannot be the first digit).
2. Choosing the Second Digit:
   • After choosing the first digit, there are 9 remaining choices for the second digit (excluding the digit already chosen).
3. Choosing the Third Digit:
   • After choosing the first and second digits, there are 8 remaining choices for the third digit (excluding the two digits already chosen).

Now, use the Multiplication Principle to find the total number of codes:

Total Codes = (Number of Choices for the First Digit) × (Number of Choices for the Second Digit) × (Number of Choices for the Third Digit) Total Codes = 9 × 9 × 8 = 648 different 3-digit codes.

Example: Imagine you are at a dessert buffet with various options. You want to create a dessert plate with a total of 4 desserts. There are three categories of desserts:

1. Cakes: There are 5 different cake options.
2. Cookies: There are 4 different cookie options.
3. Ice Cream Flavors: There are 3 different ice cream flavors.

You want to choose a combination of desserts for your plate, but you want at least one dessert from each category. How many different dessert plates can you create following these rules?

Solution

Using the Addition Principle:

To find the total number of different dessert plates, we can consider two cases:

Case 1: At least one dessert from each category:

In this case, we ensure that we select at least one cake, one cookie, and one ice cream flavor for the plate.

1. Number of Ways to Choose a Cake: There are 5 options for cakes.
2. Number of Ways to Choose a Cookie: There are 4 options for cookies.
3. Number of Ways to Choose an Ice Cream Flavor: There are 3 options for ice cream flavors.

Now, use the Multiplication Principle to find the total number of plates in this case:

Total Plates (Case 1) = (Number of Cake Choices) × (Number of Cookie Choices) × (Number of Ice Cream Flavor Choices) Total Plates (Case 1) = 5 × 4 × 3 = 60 different plates in this case.

Case 2: No restrictions on dessert categories:

In this case, you can freely choose any combination of desserts from the three categories.

Number of Ways to Choose 4 Desserts from 12 Options (5 cakes + 4 cookies + 3 ice cream flavors) = C(12, 4)

Now, use the Combination formula:

Total Plates (Case 2) = C(12, 4) = 495 different plates in this case.

Now, add the possibilities from each case:

Total Plates = (Total Plates in Case 1) + (Total Plates in Case 2) Total Plates = 60 + 495 = 555 different dessert plates you can create following the rules.

So, using the Addition Principle, you can find that there are 555 different dessert plates you can create, ensuring that you have at least one dessert from each category at the buffet.

Exercises:

1. Building a Team: You are forming a basketball team of 5 players from a pool of 10 players. You need to choose a captain from the team. How many different ways can you form the team and select a captain?

Solution

• Number of players (n) = 10
• You want to choose 5 players (r = 5).
• You also need to select a captain from the 5 players (1 choice).

2. Dinner Options: You are planning a 3-course dinner, and you can choose from 3 appetizers, 4 main courses, and 2 desserts. How many different dinner combinations can you create?

Solution

• Number of appetizers (n1) = 3
• Number of main courses (n2) = 4
• Number of desserts (n3) = 2

Total number of dinner combinations = (Number of Choices for Appetizer) + (Number of Choices for Main Course) + (Number of Choices for Dessert) Total number of dinner combinations = 3 + 4 + 2 = 9 different dinner combinations.

3. You are going on a road trip with 4 friends in a car that fits 5 people. How many different ways can everyone sit if you have to drive the whole way?

Solution

You have to sit in the driver's seat. There are 4 options for the 1st passenger seat. Once that person is seated, there are 3 options for the next passenger seat. This goes on until there is one person left with 1 seat.

Possible ways = 1 * 4 * 3 * 2 * 1 = 24

4. In a university club, there are 7 students who want to form a committee consisting of a president, a vice-president, and a treasurer. How many different committees can be formed?

Solution

To find the total number of different committees, we can use the Counting Principle, specifically the Multiplication Principle.

1. Selecting the President:
   • There are 7 students to choose from for the president role.
2. Selecting the Vice-President:
   • After selecting the president, there are now 6 students left to choose from for the vice-president role.
3. Selecting the Treasurer:
   • After selecting the president and vice-president, there are 5 students left to choose from for the treasurer role.

Now, apply the Multiplication Principle:

Total Committees = (Number of Choices for President) × (Number of Choices for Vice-President) × (Number of Choices for Treasurer)

Total Committees = 7 × 6 × 5 = 210 different committees.

Advanced Problems and Applications

Arranging Letters with Restrictions

“Arranging letters with restrictions" refers to a type of combinatorial problem where you have a set of letters that need to be arranged in a specific order, but certain conditions or restrictions must be met during the arrangement. These restrictions often involve rules about the placement or arrangement of specific letters or groups of letters.

Example:

You have the word "COMBINATORICS," which has 13 letters. In how many ways can you arrange the letters if the vowels (O, A, I) must appear together?

Solution:

To solve this problem, we can treat the three vowels (O, A, I) as a single entity since they must appear together. So, we have 11 entities in total: {C, M, B, N, T, R, C, S, _, _, _}.

• Number of arrangements of the 11 entities = 11!
• Number of arrangements of the vowels within the "vowel entity" (OAI) = 3!

Selecting Committees with Overlapping Members

"Selecting committees with overlapping members" refers to a type of combinatorial problem where you need to form multiple committees, and some members may belong to more than one committee. In these problems, you typically have a group of individuals, and you need to create distinct committees while taking into account that some individuals may serve on multiple committees simultaneously.

Example:

In a club, there are 7 students, and you want to form two committees: a math committee with 4 members and a science committee with 3 members. If 2 students are excellent in both math and science, how many ways can you form the committees?

Solution:

To form the committees, we can consider two cases:

Case 1: 2 Overlapping Members and 2 Non-Overlapping Members on the Math Committee:

1. Number of ways to choose 2 students from the 7 for both math and science committees (overlapping members): C(7, 2).
2. Number of ways to choose the remaining 2 members for the math committee from the remaining 5 students (non-overlapping members): C(5, 2).
3. Number of ways to choose the 3 members for the science committee from the remaining 5 students: C(5, 3).

Now, apply the Multiplication Principle for Case 1:

Total Committees (Case 1) = C(7, 2) * C(5, 2) * C(5, 3)

Case 2: All Non-Overlapping Members on the Math Committee:

1. Number of ways to choose 4 students from the remaining 5 students (non-overlapping members) for the math committee: C(5, 4).
2. Number of ways to choose the 3 members for the science committee from the remaining 5 students: C(5, 3).

Now, apply the Multiplication Principle for Case 2:

Total Committees (Case 2) = C(5, 4) * C(5, 3)

Now, add the possibilities from both cases to find the total number of committee formations:

Total Committees = Total Committees (Case 1) + Total Committees (Case 2)

Calculate each part separately:

• C(7, 2) = 21
• C(5, 2) = 10
• C(5, 3) = 10
• C(5, 4) = 5

Now, add these values:

Total Committees = (21 * 10 * 10) + (5 * 10)

Total Committees = 2100 + 50

Total Committees = 2150 ways to form the committees.

Real World Applications:

Combinatorial problems arise in various real-world applications across multiple fields, including computer science, engineering, mathematics, and many other disciplines. Here are some examples of how combinatorial problems are applied in these fields:

1. Computer Science:

• Network Routing: In computer networks, finding the shortest or most efficient path for data packets to travel from one point to another is a combinatorial optimization problem. Algorithms like Dijkstra's or the A* search algorithm are used for solving these problems.
• Traveling Salesman Problem (TSP): In route optimization, the TSP is a classic combinatorial problem. It involves finding the shortest possible route that visits a given set of cities and returns to the original city, visiting each city exactly once. TSP has applications in logistics, transportation, and circuit design.
• Graph Theory: Combinatorics plays a crucial role in graph theory, which is widely used in computer science. Graph algorithms, like depth-first search (DFS) and breadth-first search (BFS), are used in applications like social network analysis, recommendation systems, and network flow problems.

2. Engineering:

• Scheduling and Resource Allocation: In manufacturing and project management, combinatorial problems are common when scheduling tasks or allocating resources optimally. The goal is to minimize costs or maximize efficiency while considering constraints.
• VLSI Design: In Very Large-Scale Integration (VLSI) chip design, combinatorial optimization techniques are used to place transistors, wires, and other components efficiently on the chip's surface while minimizing power consumption and signal delay.
• Control Systems: Control theory in engineering often involves solving combinatorial problems when designing algorithms for automated control systems. This is critical in applications such as robotics, process control, and autonomous vehicles.

3. Operations Research:

• Supply Chain Management: Combinatorial problems frequently arise in optimizing supply chain logistics, including inventory management, distribution, and demand forecasting. Algorithms are used to determine the most cost-effective routes and quantities to transport goods.
• Facility Location: Companies need to decide where to locate factories, warehouses, or service centers to minimize transportation costs and meet customer demand efficiently. Combinatorial optimization techniques help make these decisions.

4. Mathematics and Cryptography:

• Number Theory: Combinatorial methods are used in number theory, especially in the study of prime numbers and divisibility. The famous Goldbach conjecture and twin prime conjecture are examples of combinatorial problems in number theory.
• Cryptography: Many cryptographic algorithms rely on combinatorial principles. For example, the security of RSA encryption is based on the difficulty of factoring large composite numbers into their prime components.

5. Bioinformatics:

• Genome Sequencing: Genome assembly and sequence alignment involve solving combinatorial problems to reconstruct a complete genome from short DNA sequences. Algorithms like BLAST and Smith-Waterman are used for sequence comparison.
• Protein Folding: Predicting the three-dimensional structure of proteins is a challenging combinatorial optimization problem. Understanding protein structures has implications for drug discovery and disease treatment.

These examples demonstrate the widespread applicability of combinatorial problems in solving real-world challenges across various domains. Researchers and professionals in these fields rely on combinatorial optimization techniques and algorithms to make informed decisions and improve efficiency and resource allocation.

Exercises:

1. In how many ways can the letters of the word "SUCCESS" be arranged such that no two "S"s are adjacent?

Solution

Total permutations of "SUCCESS" = 7!

Number of permutations with "SS" together = 6! × 2! (consider "SS" as one entity).

Number of permutations with "S" together (SS) and "SC" together (SCC) = 5! × 2!

Number of permutations with "S" together, "SC" together, and "SU" together (SCCSU) = 4! × 2!

Total permutations without adjacent "S"s = Total permutations - Permutations with "SS" together + Permutations with "S" together (SS) and "SC" together (SCC) - Permutations with "S" together, "SC" together, and "SU" together (SCCSU)

Total permutations without adjacent "S"s = 7! - 6! × 2! + 5! × 2! - 4! × 2!

2. In a deck of 52 cards, how many ways can you choose 5 cards such that you have exactly 3 red cards and 2 black cards?

Solution

Number of ways to choose 3 red cards out of 26 red cards = C(26, 3)

Number of ways to choose 2 black cards out of 26 black cards = C(26, 2)

Total number of ways = C(26, 3) * C(26, 2)

3. A committee of 7 people needs to be formed from a group of 5 men and 5 women. If the committee must consist of at least 3 men and at least 3 women, how many different committees can be formed?

Solution

We need to consider different cases based on the number of men and women in the committee.

Case 1: 3 men and 4 women in the committee Number of ways to choose 3 men from 5 = C(5, 3) Number of ways to choose 4 women from 5 = C(5, 4)

Case 2: 4 men and 3 women in the committee Number of ways to choose 4 men from 5 = C(5, 4) Number of ways to choose 3 women from 5 = C(5, 3)

Total number of committees = (C(5, 3) * C(5, 4)) + (C(5, 4) * C(5, 3))

4. How many distinct anagrams can be formed from the letters of the word "MATHEMATICS"?

Solution

There are 12 letters in "MATHEMATICS," with repetitions: M (2 times), A (2 times), T (2 times), and the unique letters: H, E, I, C, S.

The total number of distinct anagrams = 12! / (2! * 2! * 2!).

5. How many different paths are there from the top-left corner to the bottom-right corner of a 5x5 grid, moving only right or down, such that you pass through the center cell?

Solution

To pass through the center cell, you must consider two sub-paths: from the top-left corner to the center cell and from the center cell to the bottom-right corner.

Number of ways to reach the center cell (3x3 grid) = C(6, 3) = 20.

Number of ways to reach the bottom-right corner (3x3 grid) = C(6, 3) = 20.

Total number of paths = 20 * 20 = 400.

6. In a deck of 52 cards, how many different ways can you select 5 cards such that you have at least one card from each suit (hearts, diamonds, clubs, and spades)?

Solution

We can use the principle of inclusion-exclusion to solve this problem.

Number of ways to select 5 cards from the entire deck = C(52, 5).

Number of ways to select 5 cards with cards from at least one suit missing = Number of ways to select 5 cards from any three suits * 4 (since there are 4 possible suits to be missing).

Number of ways to select 5 cards from any three suits = C(39, 5).

Now, apply inclusion-exclusion:

Total number of valid selections = C(52, 5) - (C(39, 5) * 4).

Conclusion

In conclusion, combinatorics is a versatile branch of mathematics that encompasses a wide range of topics, including counting, permutations, combinations, probability, and the application of counting principles. It plays a pivotal role in solving complex problems involving the arrangement, selection, and probability of objects or events. Key takeaways from this field include the distinction between permutations and combinations, the understanding of probability as a measure of event likelihood, the concepts of independent and mutually exclusive events, and the powerful tools of counting principles like multiplication and addition principles. Combinatorics finds extensive applications in various real-world domains, including computer science, engineering, operations research, and mathematics, making it an essential tool for solving practical problems and making informed decisions.

Key Takeaways:

• Combinatorics encompasses counting, permutations, combinations, probability, and counting principles.
• Permutations involve arranging objects in a specific order, while combinations are about selecting objects without regard to order.
• Probability measures the likelihood of an event occurring, with values between 0 and 1.
• Independent events and mutually exclusive events have distinct characteristics in probability.
• Counting principles, like the multiplication and addition principles, simplify complex combinatorial problems.
• Combinatorics finds applications in various real-world fields, such as computer science, engineering, and operations research, to solve practical problems.

Practice:

1. From a group of 7 men and 6 women, five persons are to be selected to form a committee so that at least 3 men are there on the committee. In how many ways can it be done? 

a. 564 

b. 645 

c. 735 

d. 756 

e. None of these

Answer:

Option d

Explanation:

There will be 3 cases for calculating the number of ways to form a committee is as follows

Case 1: 3 Men, 2 Women

For selecting 3 men out of 7 and 2 women out of 6 to form thee 5 people committee, we can use the formulas given in the hint as follows

Case 2: 4 Men, 1 Woman

For selecting 4 men out of 7 and 1 woman out of 6 to form thee 5 people committee, we can use the formulas given in the hint as follows

Case 3: 5 Men, 0 Women

For selecting 5 men out of 7 and 0 women out of 6 to form thee 5 people committee, we can use the formulas given in the hint as follows

2. In how many ways can 20 boys and 18 girls make a queue such that no two girls are together?

Answer:

(D)

Explanation:

The boys will be arranged in 20! ways. Now, there are a total of 21 possible places available between boys such that no 2 girls can be placed together (alternate sequence of boys and girls, starting and ending positions for girls).

Therefore, the 18 girls can stand at these 21 places only.

Hence, the number of ways =

Option (D) is correct.

3. Let E and F be two independent events. If the probability that both E and F happen is 1/12 and the probability that neither E nor F happens is 1/2. Then, find P (E) and P (F).

Solution:

Both E and F happen ⇒ P (E ∩ F) = 1/12, and neither E nor F happens.

P(E’∩F’)=12

But for independent events, we have P (E ∩ F) = P (E) P (F) = 1 / 12 …(i) and

P(E’∩F’) = P(E’)×P(F’)

= { 1 − P (E)} { 1 − P (F)}

= 1 − P (E) − P (F) + P (E) P (F)

=P (E) + P (F) = 1 − 1 / 2 + 1 / 12 = 7 / 12 …(ii)

On solving Equations (i) and (ii), we get

Either P (E) = 1 / 3 and P (F) = 1 / 4 or P (E) = 1 / 4 and P (F) = 1 / 3.

4. In a dictionary, if all permutations of the letters of the word AGAIN are arranged in an order. What is the 49th word?

• Solution:

| Start with the letter A | The arranging the other 4 letters: G, A, I, N = 4! = 24 | First 24 words |
| Start with the letter G | arrange A, A, I and N in different ways: 4!/2!  = 12 | Next 12 words |
| Start with the letter I | arrange A, A, G and N in different ways: 4!/2! = 12 | Next 12 words |

This accounts up to the 48th word. The 49th word is “NAAGI”

5. In how many ways a committee consisting of 5 men and 3 women, can be chosen from 9 men and 12 women?

Solution:

Choose 5 men out of 9 men = 9C5 ways = 126 ways

Choose 3 women out of 12 women = 12C3 ways = 220 ways

Total number of ways = (126 x 220)= 27720 ways

The committee can be chosen in 27720 ways.