Combinations for GATE Exam

Combinations are a fundamental concept in combinatorics and mathematics that deal with selecting objects from a set without regard to the order in which they are arranged. Unlike permutations, where the order matters, combinations focus on choosing a subset of items without considering their arrangement sequence.

Combinations

Selecting Objects without Regard to Order:

In combinations, the emphasis is on forming subsets or groups from a larger set of objects, where the arrangement or order of the selected items is not significant. This means that, in combinations, the same selection of objects is considered identical regardless of the order in which the objects are chosen.

Notation for Combinations (C(n, r)):

Combinations are often represented using the notation C(n, r), read as "n choose r," where:

• n represents the total number of objects available for selection.
• r represents the number of objects to be chosen or the size of the subset.

The formula for calculating combinations is:

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

Where:

• C(n, r) is the number of combinations.
• n! is the factorial of "n," which is the product of all positive integers from 1 to "n."
• r! is the factorial of "r," which is the product of all positive integers from 1 to "r."
• (n - r)! is the factorial of the difference between "n" and "r."

Combinations find applications in various fields, such as probability, statistics, and discrete mathematics, whenever there's a need to count the number of ways to form groups or subsets without considering the order of selection.

Combinations of Distinct Objects:

When all objects are distinct, calculating combinations is straightforward using the combination formula:

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

Here's how to calculate combinations when all objects are distinct:

Determine the total number of distinct objects (n) available for selection.

Decide how many objects (r) you want to choose or the size of the subset.

Plug the values of n and r into the combination formula:

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

Calculate the factorials:

• Calculate n! (the factorial of n), which is the product of all positive integers from 1 to n.
• Calculate r! (the factorial of r), which is the product of all positive integers from 1 to r.
• Calculate (n - r)! (the factorial of the difference between n and r), which is the product of all positive integers from 1 to (n - r).

Substitute these values into the combination formula and simplify to find the number of combinations.

Relationship Between Permutations and Combinations:

Permutations and combinations are closely related concepts, but they differ in terms of order. The key relationship between them is:

Number of Combinations (C) = Number of Permutations (P) / (r!),

where:

• C represents the number of combinations.
• P represents the number of permutations.
• r represents the number of objects chosen or the size of the subset.

In other words, the number of combinations is equal to the number of permutations divided by the number of ways the selected objects can be arranged (r!).

Example 1: Calculate the number of ways to choose 2 distinct books from a collection of 5 distinct books.

Solution:

Using the combination formula:

C(5, 2) = 5! / [2! * (5 - 2)!]

Calculate the factorials:

• 5! = 5 × 4 × 3 × 2 × 1 = 120
• 2! = 2 × 1 = 2
• (5 - 2)! = 3! = 3 × 2 × 1 = 6

Exercises

Exercise 1:

Calculate the number of ways to choose 3 distinct fruits from a basket containing 8 distinct fruits.

Solution:

Using the combination formula:

C(8, 3) = 8! / [3! * (8 - 3)!]

Calculate the factorials:

• 8! = 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40,320
• 3! = 3 × 2 × 1 = 6
• (8 - 3)! = 5! = 5 × 4 × 3 × 2 × 1 = 120

Exercise 2:

Determine the number of ways to select 4 different students from a class of 30 students to form a study group.

Solution:

Using the combination formula:

C(30, 4) = 30! / [4! * (30 - 4)!]

Calculate the factorials:

• 30! = 30 × 29 × 28 × ... × 3 × 2 × 1 (a large number)
• 4! = 4 × 3 × 2 × 1 = 24
• (30 - 4)! = 26! (another large number)

Exercise 3:

If you have 7 different colors of paint and want to choose 5 colors to paint a picture, how many different color combinations can you choose?

Solution:

Using the combination formula:

C(7, 5) = 7! / [5! * (7 - 5)!]

Calculate the factorials:

• 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5,040
• 5! = 5 × 4 × 3 × 2 × 1 = 120
• (7 - 5)! = 2! = 2 × 1 = 2

Exercise 4:

A committee is to be formed with 6 members selected from 12 candidates. Calculate the number of ways to select the committee members.

Solution:

Using the combination formula:

C(12, 6) = 12! / [6! * (12 - 6)!]

Calculate the factorials:

• 12! = 12 × 11 × 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1
• 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
• (12 - 6)! = 6! = 720

Combinations with Identical Objects:

Combinations with identical objects involve selecting objects from a set where some or all of the objects are identical or indistinguishable from each other. In such cases, the order of selection doesn't matter, and we're interested in the number of ways to choose a subset of objects without regard to their order.

Cases Involving Repetitions:

There are two common scenarios when dealing with combinations of identical objects:

1. Combinations with Repeated Objects: This scenario occurs when you have identical or indistinguishable objects among a set of distinct objects. In this case, you want to calculate the number of combinations for selecting objects without considering their order.

Formula:

The number of combinations when choosing "r" objects from "n" distinct objects with "k" objects being identical can be calculated using the following formula:

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

Where:

• C(n, r) represents the number of combinations.
• n is the total number of distinct objects available.
• r is the number of objects to be chosen.
• k is the count of identical objects.

2. Combinations with Identical Objects in Distinct Sets: In this scenario, you have some distinct objects and want to calculate the number of distinct combinations, taking into account the repeated combinations of identical objects. This occurs when objects are divided into groups or sets, and each set contains identical objects.

Formula:

The number of combinations when choosing objects from distinct sets, where each set contains identical objects, can be calculated using the following formula:

C(n, r) = [n! / (r! * (n - r)!)] * (k1! * k2! * ... * kr!)

Where:

• C(n, r) represents the number of combinations.
• n is the total number of distinct objects available.
• r is the number of objects to be chosen.
• k1, k2, ..., kr are the counts of identical objects in each set.

Examples:

Let's illustrate these concepts with some examples:

Example 1:

You have the letters 'A,' 'A,' 'B,' 'C,' 'C.' Calculate the number of combinations when selecting 3 letters, considering the 'A's as identical.

Solution:

Using the formula for combinations with repeated objects:

C(5, 3) = [5! / (3! * (5 - 3)!)] * (1 / 2!)

Calculate the factorials:

• 5! = 5 × 4 × 3 × 2 × 1 = 120
• 3! = 3 × 2 × 1 = 6
• (5 - 3)! = 2! = 2 × 1 = 2
• 2! = 2 × 1 = 2

Substitute these values into the formula:

C(5, 3) = [120 / (6 * 2)] * (1 / 2) = (120 / 12) * 0.5 = 10 * 0.5 = 5

There are 5 different combinations of selecting 3 letters from 'A,' 'A,' 'B,' 'C,' 'C,' considering the 'A's as identical.

Example 2:

You have 8 balls, including 3 red balls, 2 green balls, and 3 blue balls. Calculate the number of combinations when selecting 4 balls without regard to their order.

Solution:

Using the formula for combinations with repeated objects in distinct sets:

C(8, 4) = [8! / (4! * (8 - 4)!)] * (3! * 2! * 3!)

Calculate the factorials:

• 8! = 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1
• 4! = 4 × 3 × 2 × 1 = 24
• (8 - 4)! = 4! = 24
• 3! = 3 × 2 × 1 = 6
• 2! = 2 × 1 = 2

Substitute these values into the formula:

C(8, 4) = [(8 × 7 × 6 × 5) / (24)] * (6 * 2 * 6) = (1680 / 24) * 72 = 70 * 72 = 5040

There are 5040 different combinations of selecting 4 balls from the set of 8, considering the repeated colors.

Exercises:

Now, let's practice with some exercises:

Exercise 1: You have 4 identical red balls, 3 identical blue balls, and 2 identical green balls. Calculate the number of different combinations when selecting 5 balls from this set.

Solution:

Using the formula for combinations with repeated objects in distinct sets:

C(9, 5) = [9! / (5! * (9 - 5)!)] * (4! * 3! * 2!)

Calculate the factorials:

• 9! = 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 (a large number)
• 5! = 5 × 4 × 3 × 2 × 1 = 120
• (9 - 5)! = 4! = 24
• 4! = 24
• 3! = 6
• 2! = 2

Exercise 2: A deck of cards has 4 suits, each with 13 cards. Calculate the number of combinations when selecting 3 cards from the deck without regard to their order, considering the suits as identical.

Solution:

Using the formula for combinations with repeated objects in distinct sets:

C(52, 3) = [52! / (3! * (52 - 3)!)] * (13! * 13! * 13!)

Calculate the factorials:

• 52! = (a very large number)
• 3! = 6
• (52 - 3)! = 49! = (a very large number)
• 13! = (a large number)

Exercise 3: You have 5 identical marbles, 4 identical stones, and 3 identical shells. Calculate the number of distinct combinations when selecting 4 items from this set.

Solution:

Using the formula for combinations with repeated objects in distinct sets:

C(12, 4) = [12! / (4! * (12 - 4)!)] * (5! * 4! * 3!)

Calculate the factorials:

• 12! = (a very large number)
• 4! = 24
• (12 - 4)! = 8! = (a very large number)
• 5! = 120
• 4! = 24
• 3! = 6

Exercise 4: In a puzzle, you have 6 identical pieces of one shape and 8 identical pieces of another shape. Calculate the number of different combinations when selecting 7 pieces from this set.

Solution:

Using the formula for combinations with repeated objects in distinct sets:

C(14, 7) = [14! / (7! * (14 - 7)!)] * (6! * 8!)

Calculate the factorials:

• 14! = (a very large number)
• 7! = 5040
• (14 - 7)! = 7! = 5040
• 6! = 720
• 8! = 40320

Combinations with Restrictions:

Combinations with restrictions involve scenarios where certain conditions or restrictions must be met when selecting objects from a set. These conditions can include requirements like selecting specific items, excluding certain items, or following specific rules.

Examples:

Example 1: You have a group of 7 friends, and you want to invite 3 of them to a dinner party. However, you have two friends, Alice and Bob, who are not on good terms and cannot be invited together. How many different ways can you invite 3 friends to the dinner party?

Solution:

To solve this problem, we can break it down into cases:

Case 1: Alice is invited, and Bob is not.

We have 5 friends (excluding Alice and Bob) to choose from for the remaining 2 spots. This can be calculated using combinations as C(5, 2).

Case 2: Bob is invited, and Alice is not.

Similar to Case 1, we have C(5, 2) ways to choose 2 friends from the remaining 5.

Total ways = Case 1 + Case 2 = C(5, 2) + C(5, 2) = 10 + 10 = 20 ways.

There are 20 different ways to invite 3 friends to the dinner party while ensuring Alice and Bob are not both invited.

Example 2: You have 8 different books, and you want to arrange them on a shelf. However, two specific books, Book A and Book B, must always be placed together on the shelf. How many different ways can you arrange the books?

Solution:

Since Book A and Book B must always be placed together, treat them as a single unit. Now, you have 7 units to arrange (6 individual books and the unit of Books A and B).

You can arrange these 7 units in 7! ways.

However, within the Books A and B unit, they can be arranged among themselves in 2! ways.

So, the total number of arrangements is 7! * 2!.

Calculate this to get the total number of arrangements.

Exercise:

Exercise 1: You have 10 different colored balls, and you want to select 4 of them. However, you want to ensure that no two adjacent balls are of the same color. How many different sets of 4 balls can you select?

Solution:

To solve this problem, we can use a recursive approach. Start by selecting the first ball. You have 10 choices.

For the second ball, you need to choose from the 9 remaining colors (excluding the one you just picked).

For the third ball, you need to choose from 8 remaining colors, and for the fourth ball, you have 7 remaining colors to choose from.

So, the total number of sets of 4 balls with the given restriction is 10 * 9 * 8 * 7.

Exercise 2: You are organizing a committee of 4 people from a group of 8 individuals. However, two of them, Alex and Bob, refuse to work together on the same committee. How many different committees can you form?

Solution:

First, calculate the total number of committees without any restrictions: C(8, 4) = 8! / (4! * (8 - 4)!) = 70

Now, calculate the number of committees where Alex and Bob are together: Calculate the number of committees with Alex and Bob together, treating them as a single entity: C(7, 3) = 7! / (3! * (7 - 3)!) = 35

Finally, subtract the number of committees with Alex and Bob together from the total number of committees to get the desired count: 70 - 35 = 35

So, there are 35 different committees you can form where Alex and Bob are not together.

Exercise 3: You have 6 different colors of paint, and you want to paint a 4-panel door such that no two adjacent panels have the same color. How many different ways can you paint the door?

Solution:

For the first panel, you have 6 color choices. For the second panel, you cannot choose the same color as the first panel, so you have 5 color choices. Similarly, for the third panel, you have 5 color choices, and for the fourth panel, you have 5 color choices.

Now, use the multiplication principle to calculate the total number of ways to paint the door: 6 (choices for the first panel) * 5 (choices for the second panel) * 5 (choices for the third panel) * 5 (choices for the fourth panel) = 6 * 5 * 5 * 5 = 750 ways

So, there are 750 different ways to paint the door without two adjacent panels having the same color.

Exercise 4: In a deck of 52 playing cards, you want to select 5 cards. However, you want to ensure that you have at least one card of each suit (hearts, diamonds, clubs, and spades) in your selection. How many different sets of 5 cards can you choose?

Solution:

Calculate the total number of ways to select 5 cards from a deck of 52 without any restrictions: C(52, 5) = 2,598,960 ways.

Now, calculate the number of ways to select 5 cards without considering the suits (i.e., without restrictions): C(13, 5) = 1,287 ways (selecting 5 cards from one suit)

There are four suits in a deck, so the total number of ways to select 5 cards from all suits is: 1,287 * 4 = 5,148 ways

Now, subtract the total number of unrestricted selections from the selections with at least one card from each suit: 2,598,960 - 5,148 = 2,593,812 ways

So, there are 2,593,812 different sets of 5 cards you can choose with at least one card from each suit.

Exercise 5: You are selecting a team of 3 players from a group of 10 basketball players. However, two of them, Mike and Sarah, do not want to play on the same team. How many different teams can you form?

Solution:

Calculate the total number of ways to select 3 players from 10 without any restrictions: C(10, 3) = 120 ways.

Now, calculate the number of teams that include both Mike and Sarah: C(8, 1) = 8 ways (choose one player from the remaining 8).

Now, subtract the number of teams that include both Mike and Sarah from the total number of teams: 120 - 8 = 112 ways

So, there are 112 different teams you can form where Mike and Sarah are not on the same team.

Exercise 6: You have 5 different types of candies, and you want to distribute them into 3 gift bags, with each bag containing at least one candy. How many different ways can you distribute the candies into the bags?

Solution:

This is a problem of distributing identical objects into distinct boxes (gift bags) with the condition that each box must contain at least one object. It can be solved using the concept of distributing indistinguishable objects into distinct boxes.

Using the stars and bars (or balls and bins) method, you can represent this problem as distributing 5 identical candies into 3 distinct gift bags. The number of ways can be calculated as C(5 + 3 - 1, 3 - 1) = C(7, 2) = 21 ways.

So, there are 21 different ways to distribute the candies into the gift bags while ensuring each bag contains at least one candy.

Conclusion

In this comprehensive exploration of combinations, we've covered the fundamental concept of selecting objects from a set without considering their order. We introduced the notation for combinations (C(n, r)) and provided the formula for calculating combinations. We discussed various scenarios, including combinations with distinct objects, combinations with identical objects, and combinations with restrictions. Examples and exercises were used to illustrate these concepts and their practical applications.

Key Takeaways

1. Combinations vs. Permutations: Combinations focus on selecting objects without regard to their order, while permutations consider the order of arrangement. The relationship between them is crucial: C(n, r) = P(n, r) / (r!), where C represents combinations and P represents permutations.
2. Combinations with Distinct Objects: When selecting objects with distinct identities, use the combination formula straightforwardly. Consider the total number of objects available (n) and the number to be chosen (r) to find the number of combinations.
3. Combinations with Identical Objects: Combinations with identical objects involve scenarios where some or all objects are indistinguishable. Formulas were provided for cases involving repeated objects and identical objects in distinct sets.
4. Combinations with Restrictions: In cases with specific conditions or requirements, such as selecting objects while following rules, it's essential to analyze and calculate valid combinations based on the constraints.

Practice Questions:

1. Out of 16 players, 11 are to be selected for a cricket team. If the wicketkeeper and captain are to be always included in each selection, in how many ways can this be done?

a. 14C9

b. 16C11

c. 14C11

d. none of these

Solution:

Given n = 16

r = 11

No. of players always included, p = 2

So, the number of ways = n-pCr-p

= 14C9

hence, option 1 is the answer.

2. Find the number of ways of selecting of 11 players out of 16, if the wicketkeeper and captain are always included in each selection, and 1 player is injured.

a. 14C9

b. 13C9

c.  13C11

d. none of these

Solution:

Total number of players, n = 16

Number of players to be selected, r = 11

Number of players who are always included, k = 2

Number of players rejected, p = 1 (injured player)

Number of ways of selection = n-k-pCr-k

= 16-2-1C11-2

= 13C9

Hence, option 2 is the answer.

3. There are 5 Maths books, 4 Science books and 3 Literature books. How many collections can a person make taking at least one from each type

a. when all the books are different

b. when all the books are similar within a group

Solution:

a) When all the books are different, at least one of the 5 math books can be selected in (25-1 ways).

At least one of the 4 science books in (24-1) ways and selecting at least one of the 3 literature books in (23-1) ways.

The answer is 31x15x7=3255

b) When all the books are similar. The total number of ways of selection of one or more from 5 math books can be done in n=5 ways.

The number of ways of selecting one or more of the 4 science books is 4.

The number of ways in which one or more of the literature books can be selected is 3. Therefore the total number of ways is 5x4x3=60

4. There are 5 maths books, 4 science books, 3 literature books. How many collections can a person make?

a. when all the books are different

b. when all the books are similar within a group

Solution:

(a) In this case when all the books are different, even 0 books can be selected.

Therefore the total number of ways in which the books can be selected in 212-1 =4095 (since 212=25 x24 x23 )

We remove 1 because we need to subtract that one case when no books are selected at all.

(b) Zero or more Maths books can be selected in 5+1 ways

Zero or more Science books can be selected in 4+1 ways

Zero or more Literature books can be selected in 3+1 ways

Total 6x5x4 = 120 ways,

but this includes a case where none of them is selected.

So subtract one. The required answer is 120-1=119

5. Number of ways in which (mn) distinct objects be distributed into m number of groups such that each group gets n objects.

1. Groups are distinct
2. Groups are identical

Solution:

(a) Groups are distinct

In this case r1=r2=r3=……= rm =n

Hence number of distributions are = (mn)!/(n!)^m

(b) Groups are identical

Since groups are identical hence if same set of objects in group are interchanged between groups are then distribution remain same.

Hence number of distribution =(mn)!/(n!)^m.m!