Combinatorics is a branch of Mathematics that studies finite or countable discrete structures and their relationships. It involves counting objects that have certain specified properties. Counting helps solve various types of problems, such as counting the number of IPv4 or IPv6 addresses.
It plays a very important role in various scientific fields such as computer science and statistics. Combinatorics involves studying combinations, permutations, and counting principles that are necessary to solve problems involving discrete objects.
Basic Principles of Combinatorics
Sum Rule
The Rule of Sum states that if there are n ways to do one thing and m ways to do another, and the two things cannot be done simultaneously, then there are n + m ways to choose one of the actions.
Example: If there are 3 ways to travel by bus and 2 ways to travel by train, then there are 3 + 2 = 5 ways to travel.
Product Rule
The Rule of Product states that if there are n ways to do one thing and m ways to do another, then there are n x m ways to do both.
Example: If there are 4 shirts and 3 pairs of pants, then there are 4 × 3 = 12 possible outfits.
Permutations and Combinations
Permutation and Combination are the most fundamental concepts in mathematics and with these concepts, a new branch of mathematics is introduced to students i.e., combinatorics. Permutation and Combination are the ways to arrange a group of objects by selecting them in a specific order and forming their subsets.
To arrange groups of data in a specific order permutation and combination formulas are used. Selecting the data or objects from a certain group is said to be permutation, whereas the order in which they are arranged is called a combination.
Examples – Combinatorics Basics
Example 1 – In how many ways can 3 winning prizes be given to the top 3 players in a game played by 12 players?
Solution – We have to distribute 3 prizes among 12 players. This task can be divided into 3 subtasks of assigning a single prize to a certain player.
Giving out the first prize can be done in 12 different ways. After giving out the first prize, two prizes remain and 11 players remain. Similarly, the second prize and third prize can be given in 11 ways and 10 ways. The total number of ways by the product rule is 12 * 11 * 10 = 1320.
Example 2 – In how many ways can a person choose a project from three lists of projects of sizes 10, 15, and 19 respectively?
Solution – The person has a choice of choosing a project from either of the three lists. So the person can choose from either 10 projects or 15 projects or 19 projects. Since choosing from one list is not the same as choosing another list, the total number of ways of choosing a project by the sum-rule is 10 + 15 + 19 = 44.
Example 3 – How many distinct license plates are possible in the given format- Two alphabets in uppercase, followed by two digits then a hyphen, and finally four digits. Sample- AB12-3456.
Solution – There are 26 possibilities for each of the two letters and 10 possibilities for each of the digits. Therefore the total number of possibilities is – 26 * 26 * 10 * 10 * 10 * 10 * 10 * 10 = 676000000.
Example 4 – How many variable names of length upto 3 exist if the variable names are alphanumeric and case-sensitive with the restriction that the first character has to be an alphabet?
Solution – Let N1, N2 and N3denote the number of possible variable names of lengths 1, 2, and 3. Therefore, the total number of variable names is N1+N2+N3.
For 
there are only 52 possibilities since the first character has to be an alphabet.
For 
, there are 52 * 62 = 3224 possibilities
For 
, there are 52 * 62 * 62 = 199888 possibilities
Therefore, total number of variable names = 52 + 3224 + 199888 = 203164
Principle of Inclusion-Exclusion
The Principle of Inclusion-Exclusion (PIE) is a fundamental theorem in combinatorics that provides a way to count the number of elements in the union of several sets. It accounts for the overlaps between the sets, ensuring that no element is counted more than once. PIE is widely used in probability, statistics, and various fields of engineering to solve complex counting problems.
Principle of Inclusion-Exclusion
The Principle of Inclusion-Exclusion states that for any finite sets A1,A2,…,AnA_1, A_2, \ldots, A_nA1,A2,…,An, the number of elements in the union of these sets can be calculated as:
A1 U A2 = A1 + A2 – A1 n A2
Solved Examples – Combinatorics Basics
Example 1: How many ways are there to arrange 5 distinct books on a shelf?
Solution:
This is a straightforward permutation problem. We have 5 distinct objects to arrange.
Number of permutations = 5! = 5 × 4 × 3 × 2 × 1 = 120
Example 2: A committee of 3 people needs to be formed from a group of 10 people. How many different committees are possible?
Solution:
This is a combination problem, as the order doesn’t matter.
We use the combination formula: C(n,r) = n! / (r! × (n-r)!)
Here, n = 10 and r = 3
C(10,3) = 10! / (3! × 7!) = 120
Example 3: How many 4-digit numbers can be formed using the digits 1, 2, 3, 4, and 5 if repetition is allowed?
Solution:
We have 5 choices for each of the 4 positions.
Total number = 5 × 5 × 5 × 5 = 5^4 = 625
Example 4: How many ways are there to select 3 ice cream scoops if there are 5 flavors available and repetition is allowed?
Solution:
This is a combination with repetition problem.
We use the formula: C(n+r-1, r) where n is the number of types and r is the number selected.
C(5+3-1, 3) = C(7,3) = 7! / (3! × 4!) = 35
Example 5: In how many ways can the letters of the word “MISSISSIPPI” be arranged?
Solution:
Total letters: 11
M: 1, I: 4, S: 4, P: 2
We use the formula: 11! / (1! × 4! × 4! × 2!) = 34,650
Example 6: In how many ways can a group of 12 people be divided into 3 teams of 4 people each?
Solution:
This is a partition problem. We can solve it step by step:
Choose 4 people for the first team: C(12,4)
Choose 4 from the remaining 8 for the second team: C(8,4)
The last 4 automatically form the third team
Divide by 3! to remove order of team selection
Result: (C(12,4) × C(8,4)) / 3! = (495 × 70) / 6 = 5,775
Example 7: In a class of 30 students, 18 play football, 15 play basketball, and 10 play both. How many students play neither sport?
Solution:
Let F be football players and B be basketball players.
Total = |F ∪ B| + Neither
30 = (|F| + |B| – |F ∩ B|) + Neither
30 = (18 + 15 – 10) + Neither
Neither = 30 – 23 = 7 students
Example 8 : In how many ways can 8 people be seated around a circular table?
Solution:
For circular permutations, we fix one person and arrange the rest.
Number of arrangements = (n-1)! = 7! = 5,040
Example 9: In the expansion of (x + y)^7, what is the coefficient of x^3y^4?
Solution:
We use the formula: C(n,r) × x^(n-r) × y^r
Here, n = 7, r = 4
Coefficient = C(7,4) = 7! / (4! × 3!) = 35
Example 10 : How many ways are there to distribute 10 identical candies among 4 children, allowing for the possibility that some children may receive no candies?
Solution:
This is a classic “Stars and Bars” problem.
We use the formula: C(n+k-1, k-1) where n is the number of items and k is the number of groups.
C(10+4-1, 4-1) = C(13, 3) = 13! / (3! × 10!) = 286
Practice Problems on Combinatorics Basics
1).How many ways are there to arrange the letters in the word “MATHEMATICS”?
2).A bakery offers 8 types of donuts. How many ways can a customer select a dozen donuts if repetitions are allowed?
3).In how many ways can 7 people be seated in a row if 2 specific people must sit next to each other?
4).How many 6-digit numbers can be formed using the digits 0 to 9 if the number must be even and no digit can be repeated?
5).A committee of 5 people is to be formed from a group of 8 men and 6 women. In how many ways can this be done if the committee must have at least 2 women?
6).In how many ways can 20 identical balls be distributed among 5 distinct boxes?
7).How many ways are there to select a team of 3 boys and 3 girls from a class of 10 boys and 12 girls?
8).In a group of 15 people, in how many ways can a president, vice president, and treasurer be chosen if no person can hold more than one position?
9).How many different necklaces can be made using 8 beads, if there are 3 red beads, 3 blue beads, and 2 green beads? (Consider rotations as the same necklace)
10).In how many ways can the letters of the word “COMBINATORICS” be rearranged so that no two vowels are adjacent?
