Table of Contents
Combinatorics
Combinatorics is the branch of discrete mathematics concerned with counting problems. Techniques for counting are important in Mathematics and Computer Science especially in the analysis of algorithms and in the theory of probability.
Principle of Counting
1. Rule of Sum
If the object A may be chosen in ‘m’ ways, and B in ‘n’ ways, then “either A or B” (exactly one) may be chosen in m + n ways. This can be generalized for any ‘p’ objects
2. Rule of Product
If the object A may be chosen in ‘m’ ways and the object B in ‘n’ ways, then “A and B” may be chosen in this order in ‘mn’ ways. This can be generalized for any ‘p’ ways.
If there are 42 ways to select a representative for class A and 50 ways to select a representative for the class B, then
(i) By the rule of product, there are 42 × 50 ways to select the representative for both the class A and class B.
(ii) By the rule of sum, there will be 42 + 50 ways to select a representative for either class A or class B.
| Example 01 |
Suppose a license plate contains 2 letters followed by four digits, with the first digit is not zero. How many different license plates can be printed?
Solution:
Each letter can be printed in 26 different ways. Since the first digit is other than zero, this can be selected in 9 ways. Second, third and fourth digits can be selected in 10 ways.
Therefore by the rule of product, there are 26 × 26 × 9 × 10 × 10 × 10 ways.
Special case: All are distinct
First letter can be printed in 26 ways. Second letter can be printed in 25 ways. First digit can be printed in 9 ways (any one from 0 to 9 except chosen first digit). Third digit can be printed in 8 ways. Fourth digit can be printed in 7 ways.
Therefore, by the rule of product, there are 26 × 26 × 9 × 9 × 8 × 7 ways.
| Example 02 |
Suppose we want to choose two persons from a party consisting of 35 members as president and vice-president. In how many ways can this be done?
Solution:
Here, Subtask 1 is ‘choosing a president’. This can be done in 35 ways. Subtask 2 is ‘choosing a vice-president’. For each choice of president, we can choose the vice-president in 34 ways. Therefore, the total number of ways in which Subtasks 1 and 2 can be done is 35 × 34 = 1190.
| Example 03 |
There are three political parties, P1, P2, and P3. The party P1 has 4 members, P2 has 5 members and P3 has 6 members in an assembly. Suppose we want to select two persons, both from the same party, to become president and vice president. In how many ways can this be done?
Solution:
From P1, we can do the task in 4 × 3 = 12 ways, using the multiplication principle. From P2, it can be done in 5 × 4 = 20 ways. From P3 it can be done in 6 × 5 = 30 ways. So, by the addition principle, the number of ways of doing the task is 12 + 20 + 30 = 62.
Though both these principles seem simple, quite a number of combinatorial enumerations can be done with them. For instance, what we see from Example 03 is that the addition principle helps us to count all possible arrangements grouped into mutually exclusive and exhaustive classes.
| Example 04 |
Find the number of words of length 4, meaningful or not, made with the letters a, b, …, j.
Solution:
There are 10 letters from a, b, c, …, j. Here we apply the multiplication principle. Each letter has 10 possibilities. Therefore, the total number of words is = 10 × 10 × 10 × 10 = 104.
| Example 05 |
If n couples are at a dance, in how many ways can the men and women be paired for a single dance?
Solution:
Suppose we number the men as 1, 2, 3,…, n. Then the first man can be paired with any of the n women, the second can be paired with any from the remaining (n − 1) women, and so on. Hence, the number of ways of pairing is n × (n − 1) × … × 1 = n!.
| Example 06 |
How many integers between 100 and 999 consist of distinct even digits?
Solution:
By the multiplication principle, the number of integers between 100 and 999 with all digits even is 4 ×5 × 5 = 100 (Note that the first digit cannot be zero, but the second and third digits can be 0.)
| Example 07 |
Consider all the numbers between 100 and 999 that have distinct digits. How many of them are odd?
Solution:
For a number to be odd the last digit should be odd. So, the last position can be filled up in 5 ways. If the middle position is filled up by 0, then the first position can be filled up in 8 ways. Thus the number of odd numbers with 0 in the middle position and all digits distinct is 40, by the multiplication principle.
If the middle position is filled up by a digit other than 0, then this can be done in 8 ways. Then the first position can be filled up in 7 ways. So, the number of odd numbers with all digits distinct with the middle digit not zero is 5 × 8 × 7 = 280.
Thus, by the addition principle the answer is 40 + 280 = 320.
Sequence |
Inclusion and Exclusion – |
