IS 5311: Discrete Mathematics

Chapter 5: Combinatorics
Lecturer: MS. M.W.S. Randunu Department of Interdisiplinary Studies,University of Ruhuna.

5.1 Introduction

Combinatorics is a fascinating and fundamental branch of mathematics concerned with counting, arranging,
and analyzing discrete structures. Its principles are essential not only in theoretical mathematics but also in
practical applications across various fields, including computer science, cryptography, network theory, and
more.
In this Chapter, we will explore key aspects of combinatorics, focusing on its role in problem-solving and
algorithm design. The study of combinatorics involves:

1. Counting
One of the core activities in combinatorics is determining the number of possible configurations or
arrangements of a set of objects. This includes counting permutations (arrangements) and combinations
(selections) of objects, which is foundational in many computational problems.
2. Permutations and Combinations
• Permutations: Refers to the number of ways to arrange a set of objects. For example, the
number of possible arrangements of 3 distinct books is 3! (3 factorial).
• Combinations: Concerns the number of ways to choose a subset of objects from
a larger set.
For instance, the number of ways to select 2 books from a set of 3 is given by 32 (read as ”3
choose 2”).
3. Graph Theory
Graph theory is a significant area of combinatorics that studies graphs—mathematical structures used
to model pairwise relationships between objects. Essential concepts include vertices (nodes), edges
(connections), paths, cycles, and connectivity. Understanding these concepts is crucial for analyzing
networks and designing algorithms.
4. Design Theory
Design theory focuses on the study of combinatorial designs, which are specific arrangements of subsets
or blocks with desired properties. Examples include balanced incomplete block designs and Latin
squares, which have applications in experimental design and coding theory.
5. Probabilistic Combinatorics
Probabilistic combinatorics uses probability theory to analyze combinatorial problems. This approach
often involves random graphs and probabilistic methods to estimate or bound the size of combinatorial
objects.
Combinatorics is widely applicable in computer science, particularly in algorithms, cryptography, and
network theory. It also has connections to other areas of mathematics like number theory, geometry,
and topology.

5-1
Chapter 5: Combinatorics 5-2

5.2 Counting Principles

Counting principles are essential tools in combinatorics used to determine the number of possible outcomes
in different scenarios.

5.2.1 Product Rule

The Product Rule is a fundamental concept in combinatorics used to determine the number of possible
outcomes in a sequence of events or tasks. It states:

Definition 1. If there are n1 ways to perform the first task, n2 ways to perform the second task, and so on,
then the total number of ways to perform all tasks is given by the product n1 × n2 × · · · × nk , where k is the
number of tasks.

Examples

1. Choosing an Outfit

Suppose you want to choose an outfit consisting of a shirt and pants. If you have 5 different shirts and
3 different pairs of pants, and each shirt can be paired with each pair of pants, the total number of
possible outfits is:

Total number of outfits = 5 (shirts) × 3 (pants) = 15

2. Creating a Password

Consider creating a 4-digit password where each digit can be any number from 0 to 9. Each digit is
chosen independently. Therefore, for each digit, there are 10 possible choices. The total number of
possible passwords is:

10 × 10 × 10 × 10 = 104 = 10,000

3. In a computer system, there are 4 different types of processors, 3 different types of memory modules,
and 2 different types of storage drives. How many different combinations of these components can be
created if you choose one of each type?

Solution:

Number of combinations = Number of processors×Number of memory modules×Number of storage drives

Number of combinations = 4 × 3 × 2 = 24
Chapter 5: Combinatorics 5-3

So, there are 24 different combinations of processors, memory modules, and storage drives.

4. Suppose there are 4 different letters (P, Q, R, and S) which must be placed into 6 different boxes. How
many ways are there to place these 4 letters into the 6 different boxes if each letter can go into any of
the boxes?

Solution:
Imagine you have 6 boxes labeled as follows:

Each letter (P, Q, R, and S) can be placed in any of these 6 boxes.

Each letter has 6 choices independently. Therefore, the total number of ways to place all 4 letters into
the 6 boxes is:

6 × 6 × 6 × 6 = 64 = 1296

So, there are 1296 different ways to place the 4 letters into the 6 different boxes.

5. Suppose there are 5 computer engineering students and 3 distinct project roles (e.g., Project Manager,
Developer, Tester) to be assigned. How many ways can you assign these 3 distinct roles to the 5
students if each role must be assigned to exactly one student and any student can take on any role?

Solution:
• Choose a Student for the First Role: There are 5 choices for the first role.
• Choose a Student for the Second Role: After assigning the first role, there are 4 students left for
the second role.
• Choose a Student for the Third Role: After assigning the second role, there are 3 students left
for the third role.
The total number of ways to assign the 3 roles is:

5 × 4 × 3 = 60

So, there are 60 different ways to assign the 3 distinct roles to the 5 students.
Chapter 5: Combinatorics 5-4

6. How many different bit strings of length 8 are there?

Solution:
Each bit in the string can be either 0 or 1. Since the bit string is 8 bits long, and each bit can be either
0 or 1 independently, you can use the product rule:

2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 = 28

Calculating 28 :

28 = 256

So, there are 256 different bit strings of length 8.

7. How many different number plates can be made if each plate contains a sequence of three uppercase
English letters followed by 4 digits?

Solution:
(a) Letters:
• There are 26 uppercase English letters.
• Each of the three positions for the letters can be filled with any of the 26 letters.
• The number of possible combinations for the letters is:

26 × 26 × 26 = 263
(b) Digits:
• There are 10 digits (0 through 9).
• Each of the four positions for the digits can be filled with any of the 10 digits.
• The number of possible combinations for the digits is:

10 × 10 × 10 × 10 = 104
The total number of different number plates is:

263 × 104

Calculating these values:

263 = 17576
104 = 10000
17576 × 10000 = 175760000
So, there are 175,760,000 different number plates possible.

The Counting Principle is essential for analyzing scenarios where multiple choices or stages are involved. By
applying this principle, one can systematically determine the total number of possible outcomes in various
combinatorial problems.
Chapter 5: Combinatorics 5-5

5.2.2 The Sum Rule

Definition 2. The Sum Rule (or Addition Rule) in combinatorics states that if you have two mutually
exclusive events (i.e., events that cannot occur at the same time), then the total number of ways that one of
these events can occur is the sum of the number of ways each event can occur.

Formal Definition:
If A and B are two mutually exclusive events, then the number of ways to choose one of these events is given
by:

|A ∪ B|= |A|+|B|

where:

• |A| is the number of ways to choose event A,

• |B| is the number of ways to choose event B,

• |A ∪ B| is the number of ways to choose either event A or event B.

Examples:

1. Consider a problem where you need to count the number of ways to choose a committee from a set of
people, with two options:

(a) Option 1: Choosing a committee of 3 people from 10 people.

(b) Option 2: Choosing a committee of 4 people from 15 people.

If these two options are mutually exclusive (i.e., you can only choose one of them), then the total
number of ways to choose a committee under either option is:

Total ways = Ways for Option 1 + Ways for Option 2

In mathematical terms, if |A| represents the number of ways to choose the committee in Option 1, and
|B| represents the number of ways to choose the committee in Option 2, then:

Total ways = |A|+|B|

Chapter 5: Combinatorics 5-6

2. Suppose there are two types of number plates:

(a) Plates that have a sequence of three uppercase English letters followed by 2 digits.
(b) Plates that have a sequence of two uppercase English letters followed by 3 digits.
How many different number plates can be made in total?
Solution:

• Type 1 Plates:
– There are 26 choices for each of the 3 letters.
– There are 10 choices for each of the 2 digits.
– The number of possible plates for this type is:
263 × 102
• Type 2 Plates:
– There are 26 choices for each of the 2 letters.
– There are 10 choices for each of the 3 digits.
– The number of possible plates for this type is:
262 × 103
To find the total number of different number plates, add the number of plates for each type:

263 × 102 + 262 × 103

Calculating these values:

263 = 17576
102 = 100
262 = 676
103 = 1000
17576 × 100 = 1757600
676 × 1000 = 676000
1757600 + 676000 = 2433600

So, there are 2,433,600 different number plates possible when combining both types.
Chapter 5: Combinatorics 5-7

5.2.3 Inclusion-Exclusion Principle

1. Counting Individual Sets: Start by counting the number of elements in each set individually. This
includes all elements in each set but may double-count elements in the intersections.
2. Subtracting Overlaps: Subtract the number of elements that belong to the intersection of every
pair of sets to correct the over-counting.

3. Adding Back Overlaps of Triples: Add back the number of elements common to every triplet of
sets, as these elements were subtracted too many times.
4. Continuing for Higher Orders: Continue this process for intersections of higher-order sets, alter-
nating between subtraction and addition.

Definition 3. For Two Sets A and B:

|A ∪ B|= |A|+|B|−|A ∩ B|

Here, |A ∪ B| is the number of elements in either set A or set B or both. We add |A| and |B| and subtract
|A ∩ B| to correct for double-counting.

For Three Sets A, B, and C:

|A ∪ B ∪ C|= |A|+|B|+|C|−|A ∩ B|−|A ∩ C|−|B ∩ C|+|A ∩ B ∩ C|

In this case, add the sizes of the three sets, subtract the sizes of all pairwise intersections, and add the size
of the intersection of all three sets to correct for triple-counting.
For n Sets:
The principle generalizes to n sets as follows:

n
[ n
X X X
Ai = |Ai |− |Ai ∩ Aj |+ |Ai ∩ Aj ∩ Ak |− · · · + (−1)n+1 |A1 ∩ A2 ∩ · · · ∩ An |
i=1 i=1 1≤i<j≤n 1≤i<j<k≤n

This formula alternates between adding and subtracting the sizes of intersections of increasing numbers of
sets.
Chapter 5: Combinatorics 5-8

Examples:

1. Consider a computer engineering department with three different student groups:

(a) Group A: Students who are taking Programming courses.
(b) Group B: Students who are taking Data Structures courses.
(c) Group C: Students who are taking Algorithms courses.
We want to find the number of students who are taking at least one of these courses.
Suppose we have the following counts:
• |A|= 120 (students taking Programming courses)
• |B|= 100 (students taking Data Structures courses)
• |C|= 90 (students taking Algorithms courses)
• |A ∩ B|= 50 (students taking both Programming and Data Structures courses)
• |A ∩ C|= 40 (students taking both Programming and Algorithms courses)
• |B ∩ C|= 30 (students taking both Data Structures and Algorithms courses)
• |A ∩ B ∩ C|= 20 (students taking all three courses)
Using the Inclusion-Exclusion Principle, we calculate the number of students taking at least one course:

|A ∪ B ∪ C|= |A|+|B|+|C|−|A ∩ B|−|A ∩ C|−|B ∩ C|+|A ∩ B ∩ C|

Substituting the given values:

|A ∪ B ∪ C|= 120 + 100 + 90 − 50 − 40 − 30 + 20

Performing the arithmetic:

|A ∪ B ∪ C|= 310 − 120 + 20 = 210

Thus, the number of students who are taking at least one of the courses is 210.
2. In a secure system, each user must create a password that consists of exactly 10 characters. These
characters can be uppercase English letters (26 options), lowercase English letters (26 options), or
digits (10 options). Each password must include at least one uppercase letter and at least one digit.
How many potential passwords exist under these conditions?

Solution:
Define the following sets:
• A: The set of passwords that do not contain any uppercase letters.
• B: The set of passwords that do not contain any digits.
We use the Inclusion-Exclusion Principle to find the number of passwords that do not meet the re-
quirement:

(a) Total number of possible passwords (with no restrictions):

|U |= 6210
Chapter 5: Combinatorics 5-9

(b) Number of passwords with no uppercase letters:

|A|= 3610

(c) Number of passwords with no digits:

|B|= 5210

(d) Number of passwords with only lowercase letters (no uppercase and no digits):

|A ∩ B|= 2610

(e) Apply Inclusion-Exclusion Principle:

|A ∪ B|= |A|+|B|−|A ∩ B|

|A ∪ B|= 3610 + 5210 − 2610

(f) Number of valid passwords (including at least one uppercase letter and one digit):

Valid passwords = 6210 − |A ∪ B|

3. How many bit strings of length 8 either start with a 1 bit or end with the two bits 11?
Solution:
Let:
• Event A: Bit strings of length 8 that start with a 1.
• Event B: Bit strings of length 8 that end with 11.
We want to find |A ∪ B|, the number of bit strings that either start with a 1 or end with 11.

(a) Calculate |A|:

|A|= 27 = 128
(b) Calculate |B|:
|B|= 26 = 64
(c) Calculate |A ∩ B|:
|A ∩ B|= 25 = 32
(d) Apply the Inclusion-Exclusion Principle:

|A ∪ B|= |A|+|B|−|A ∩ B|

|A ∪ B|= 128 + 64 − 32 = 160

Answer: The number of bit strings of length 8 that either start with a 1 bit or end with the two bits
11 is 160.
4. In a computer engineering department, there are 50 students taking Programming, 40 students taking
Data Structures, and 30 students taking Algorithms. The following information is given:
• 15 students are taking both Programming and Data Structures.
• 12 students are taking both Programming and Algorithms.
Chapter 5: Combinatorics 5-10

• 8 students are taking both Data Structures and Algorithms.

• 5 students are taking all three subjects (Programming, Data Structures, and Algorithms).
How many students are taking at least one of these subjects?
Solution:
Let:

• Event A: Students taking Programming.

• Event B: Students taking Data Structures.
• Event C: Students taking Algorithms.
We want to find |A ∪ B ∪ C|, the number of students taking at least one of these subjects.

(a) Calculate |A|, |B|, and |C|:

|A|= 50
|B|= 40
|C|= 30
(b) Calculate the number of students in the intersection of two subjects:

|A ∩ B|= 15

|A ∩ C|= 12
|B ∩ C|= 8

(c) Calculate the number of students in the intersection of all three subjects:

|A ∩ B ∩ C|= 5

(d) Apply the Inclusion-Exclusion Principle:

|A ∪ B ∪ C|= |A|+|B|+|C|−|A ∩ B|−|A ∩ C|−|B ∩ C|+|A ∩ B ∩ C|

|A ∪ B ∪ C|= 50 + 40 + 30 − 15 − 12 − 8 + 5
|A ∪ B ∪ C|= 120 − 35 + 5 = 90

Answer: The number of students taking at least one of Programming, Data Structures, or Algorithms
is 90.
Chapter 5: Combinatorics 5-11

5.2.4 The Division Rule

The Division Rule is used to determine the number of distinct objects when some of them are identical.

Definition 4. If a set of objects can be arranged in N different ways, but there are k1 indistinguishable
objects of one kind, k2 indistinguishable objects of another kind, and so on, then the number of distinct
arrangements is given by:

N
k1 ! ·k2 ! · · · · · km !

where k1 , k2 , . . . , km are the numbers of indistinguishable objects of each kind.

Example:

1. Suppose you have 10 letters, where 4 are ’A’s, 3 are ’B’s, and 3 are ’C’s. To find the number of distinct
arrangements of these letters, use the Division Rule:
(a) Calculate the total number of arrangements if all letters were distinguishable:

10!

(b) Divide by the factorial of the number of indistinguishable objects for each kind:
10!
4! ·3! ·3!

(c) How many distinct arrangements can be formed using the letters in ”COMPUTER ENGINEER-
ING”?
Solution:
i. Count the total number of letters:
”COMPUTER ENGINEERING” consists of 17 letters.
ii. Identify and count repeated letters:
• ’C’: 1
• ’O’: 2
• ’M’: 1
• ’P’: 1
• ’U’: 1
• ’T’: 1
• ’E’: 3
• ’R’: 2
• ’N’: 2
• ’G’: 1
• ’I’: 1
iii. Apply the Division Rule: The formula for arrangements of a multiset is:
n!
k1 ! ·k2 ! · · · · · km !
Chapter 5: Combinatorics 5-12

where n is the total number of letters, and ki is the factorial of the count of each distinct
letter.
For ”COMPUTER ENGINEERING”:
• Total number of letters, n = 17
• Count of each letter:
A. ’E’: 3 (so, kE = 3!)
B. ’O’: 2 (so, kO = 2!)
C. ’R’: 2 (so, kR = 2!)
D. ’N’: 2 (so, kN = 2!)
• Others: 1 each (so, kC = 1!, kM = 1!, kP = 1!, kU = 1!, kT = 1!, kG = 1!, kI = 1!)
Applying the formula:
17!
Number of distinct arrangements =
3! ·2! ·2! ·2!

5.3 Permutations and Combinatorics

Permutations refer to the different ways in which a set of objects can be arranged in order. The order of
arrangement is significant, meaning that different orders of the same set of objects are counted as different
permutations.

Example:
Consider the letters A, B, and C. The permutations of 2 letters out of these 3 are:

• AB
• AC
• BA
• BC
• CA
• CB

There are 6 permutations.

Definition 5. If you have a set of n distinct objects, the number of ways to arrange all of these objects in
order (i.e., the number of permutations) is given by n! (n factorial), where:

n! = n × (n − 1) × (n − 2) × · · · × 2 × 1

Example: Suppose you want to find the number of ways to arrange 5 distinct books on a shelf:

5! = 5 × 4 × 3 × 2 × 1 = 120
Chapter 5: Combinatorics 5-13

[Link] Permutations of a Subset

Definition 6. If you want to arrange r objects out of a set of n distinct objects, the number of permutations
is given by:

n!
P (n, r) =
(n − r)!

where:

• n is the total number of objects.

• r is the number of objects to arrange.

The number of r-permutations of a set with n elements is denoted by p(n, r).

Example: Suppose you have 8 distinct students and want to choose and arrange 3 of them in a line:

8! 8×7×6×5×4×3×2×1
P (8, 3) = = = 8 × 7 × 6 = 336
(8 − 3)! 5!

Example: Consider a set with 6 elements. The number of 2-permutations, 3-permutations, and 4-permutations
are denoted by p(6, 2), p(6, 3), and p(6, 4) respectively. These are calculated as follows:

6! 720
p(6, 2) = = = 30
(6 − 2)! 24

6! 720
p(6, 3) = = = 120
(6 − 3)! 6

6! 720
p(6, 4) = = = 360
(6 − 4)! 2

[Link] Permutations of Multisets

If some objects in the set are identical, the formula for the number of distinct permutations changes.

Definition 7. For a multiset with n total objects where there are k1 identical objects of one type, k2 identical
objects of another type, and so on, the number of distinct permutations is given by:

n!
k1 ! ×k2 ! × · · · × km !
Chapter 5: Combinatorics 5-14

Example: Consider the word ”BANANA”, where there are 6 letters, but the letter ’A’ appears 3 times,
and ’N’ appears 2 times. The number of distinct permutations is:

6! 720 720
= = = 60
3! ×2! ×1! 6×2×1 12

Example: How many different 8-character passwords can be created using the letters from the word ”COM-
PUTER” without repetition of characters?
Solution:
Since all 8 characters in ”COMPUTER” are distinct, the number of different passwords is simply:

8! = 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40320

5.3.1 Combinations

Combinations refer to the selection of items from a larger set where the order of selection does not matter.
Unlike permutations, where the order is important, combinations focus solely on the grouping of items.
Example:
Consider the letters A, B, and C. The combinations of 2 letters out of these 3 are:

• AB
• AC

• BC

There are 3 combinations.

Definition 8. The number of combinations of r objects chosen from n objects can be expressed in several
equivalent ways:

 
n n!
C(n, r) = = = n Cr
r (n − r)! r!
where:

• n is the total number of objects.

• r is the number of objects to choose.
• n! (n factorial) is the product of all positive integers up to n.
Chapter 5: Combinatorics 5-15

Examples:

1. Suppose you have 5 distinct books, and you want to select 2 of them to take on a trip. The number of
ways to choose these 2 books, without considering the order, is:
 
5 5! 5 × 4 × 3! 5×4
= = = = 10
2 2! (5 − 2)! 2 × 1 × 3! 2×1

Thus, there are 10 different ways to choose 2 books from a set of 5.

2. Consider a set of 8 different letters. The number of ways to choose 3 letters from this set is:
 
8 8! 8!
= =
3 3! (8 − 3)! 3! ·5!

3. In a deck of 52 cards, the number of ways to choose 5 cards is given by:

 
52 52!
=
5 5! (52 − 5)!

This represents the number of possible 5-card hands from a standard deck.
4. Given a set of 15 objects, the number of ways to select a subset of 6 objects is:
 
15 15! 15!
= =
6 6! (15 − 6)! 6! ·9!

5. In a Computer Engineering Faculty, there are 120 students in the Software Engineering department
and 150 students in the Hardware Engineering department. We need to form a committee of 6 students
from the Software Engineering department and 8 students from the Hardware Engineering department.
How many ways are there to select this committee?
we use the combination formula:
 
120 120!
Number of ways to select 6 students from 120: =
6 6! (120 − 6)!
 
150 150!
Number of ways to select 8 students from 150: =
8 8! (150 − 8)!

Since the selections are independent, the total number of ways to form the committee is:
   
120 150
Total Ways = ×
6 8
Chapter 5: Combinatorics 5-16

5.3.2 Differences between Permutations and Combinations

Aspect Permutations Combinations

Definition Arrangements of objects in a spe- Selection of objects without re-
cific order. Order matters. gard to order. Order does not
matter.
Order Important (e.g., AB is different Not important (e.g., AB is the
from BA). same as BA).
n! n!
Formula P (n, r) = (n−r)! C(n, r) = r!(n−r)!
Example For 3 objects (A, B, C) and For 3 objects (A, B, C) and
choosing 2: AB, AC, BA, BC, choosing 2: AB, AC, BC (3
CA, CB (6 ways). ways).
Application Used when the arrangement or Used when the selection or com-
sequence of objects matters (e.g., bination of objects matters with-
seating arrangements). out considering the order (e.g.,
selecting a committee).

5.4 Pigeonhole Principle

The Pigeonhole Principle is a fundamental concept in combinatorics. It states that if more ”pigeons” are
placed into fewer ”pigeonholes,” then at least one pigeonhole must contain more than one pigeon.

Definition 9. The Pigeonhole Principle states that if n items are distributed among m containers and
n > m, then at least one container must contain more than one item.

Example:
If there are 10 students and only 9 desks, then at least one desk must have more than one student.
Applications:

• Proving Existence: The principle can be used to show that in a group of 13 people, at least two
people must have the same number of hairs on their head if the number of hairs ranges from 0 to 12.
• Scheduling Problems: In resource allocation problems, if there are more tasks than resources, the
principle can show that some resources will be used more than once.
• Birthday Problem: In a group of 23 people, there is a better than even chance that at least two
people share the same birthday.

Problem: Prove that if 10 pigeons are placed into 9 pigeonholes, then at least one pigeonhole must contain
at least 2 pigeons.

Proof:

• Assume the contrary: each pigeonhole contains at most 1 pigeon.

Chapter 5: Combinatorics 5-17

• Since there are 9 pigeonholes, a maximum of 9 pigeons can be placed into these holes without any
pigeonhole containing more than one pigeon.
• However, we have 10 pigeons, which exceeds this maximum. Therefore, at least one pigeonhole must
contain more than one pigeon.

5.5 The binomial theorem

The binomial theorem provides a formula for expanding powers of binomials.

Definition 10. For any positive integer n and any real numbers x and y, the expansion of (x + y)n is:
         
n n n 0 n n−1 1 n n−2 2 n 1 n−1 n 0 n
(x + y) = x y + x y + x y + ··· + x y + x y
0 1 2 n−1 n

n  
n
X n
(x + y) = xn−k y k
k
k=0

n


where the binomial coefficient k is defined as:

 
n n!
=
k k! (n − k)!

Example 1: To expand (2x + 3)4 using the binomial theorem, we have:

4  
4
X 4
(2x + 3) = (2x)4−k · 3k
k
k=0

Calculating each term:

 
4
For k = 0 : (2x)4 · 30 = 1 · 16x4 = 16x4
0
 
4
For k = 1 : (2x)3 · 31 = 4 · 8x3 · 3 = 96x3
1
 
4
For k = 2 : (2x)2 · 32 = 6 · 4x2 · 9 = 216x2
2
 
4
For k = 3 : (2x)1 · 33 = 4 · 2x · 27 = 216x
3
 
4
For k = 4 : (2x)0 · 34 = 1 · 81 = 81
4

Thus, the expanded form is:

(2x + 3)4 = 16x4 + 96x3 + 216x2 + 216x + 81

Chapter 5: Combinatorics 5-18

Example 2: To find the coefficient of x4 y 5 in the expansion of (2x + 3y)9 , we use the binomial theorem:

9  
X 9
(2x + 3y)9 = (2x)9−k (3y)k
k
k=0

We need the term where x9−k = x4 and y k = y 5 . Thus:

9 − k = 4 =⇒ k = 5

The term is:

 
9
(2x)9−5 (3y)5
5

Simplify:

 
9
Term = (2x)4 (3y)5
5

Compute (2x)4 :

(2x)4 = 24 · x4 = 16x4

Compute (3y)5 :

(3y)5 = 35 · y 5 = 243y 5

Thus:

 
9
Term = · 16x4 · 243y 5
5

Calculate the binomial coefficient:

 
9 9!
= = 126
5 5! ·4!

The coefficient is:

126 · 16 · 243 = 488, 088

Example 3: To find the coefficient of x3 y 4 in the expansion of (3x − 2y)7 , we use the binomial theorem:

7  
X 7
(3x − 2y)7 = (3x)7−k (−2y)k
k
k=0
Chapter 5: Combinatorics 5-19

We need the term where x7−k = x3 and y k = y 4 . Thus:

7 − k = 3 =⇒ k = 4

The term is:

 
7
Term = (3x)7−4 (−2y)4
4

Simplify:

 
7
Term = (3x)3 (−2y)4
4

Calculate (3x)3 :

(3x)3 = 33 · x3 = 27x3

Calculate (−2y)4 :

(−2y)4 = (−2)4 · y 4 = 16y 4

Thus:

 
7
Term = · 27x3 · 16y 4
4

Calculate the binomial coefficient:

 
7 7!
= = 35
4 4! ·3!

The coefficient is:

35 · 27 · 16 = 15, 120
Chapter 5: Combinatorics 5-20

Example 4: To find the coefficient of x5 in the expansion of (−1 + x)6 , we use the binomial theorem:

6  
X 6
(−1 + x)6 = (−1)6−k xk
k
k=0

We need the term where xk = x5 . Thus:

k=5

The term is:

 
6
Term = (−1)6−5 x5
5

Simplify:

 
6
Term = (−1)1 x5
5

Calculate (−1)1 :

(−1)1 = −1

Calculate the binomial coefficient:

 
6 6!
= =6
5 5! ·1!

Thus, the coefficient is:

6 · (−1) = −6

Theorem:
Let n be a positive integer. Then

n  
X n
(−1)r =0
r=0
r

Proof:
We use the Binomial Theorem, which states that for any integers n ≥ 0 and any numbers x and y,

n  
X n n−r r
(x + y)n = x y
r=0
r
Chapter 5: Combinatorics 5-21

Set x = 1 and y = −1. Applying the Binomial Theorem, we get:

n  
n
X n n−r
(1 + (−1)) = 1 (−1)r
r=0
r

Since 1n−r = 1, this simplifies to:

n  
n
X n
(1 − 1) = (−1)r
r=0
r

Simplify (1 − 1)n :

(1 − 1)n = 0n

Since 0n = 0 for any positive integer n, we have:

n  
X n
0= (−1)r
r=0
r

This completes the proof.

5.6 Pascal’s Triangle

Pascal’s Triangle is a triangular array of numbers where:

• The top row is 1 (row 0).

• Each row corresponds to the coefficients of the binomial expansion (x + y)n for increasing n.
• Each number in the triangle is the sum of the two numbers directly above it.

Theorem:
Let n and r be positive integers with n ≥ r. Then

     
n+1 n n
= +
r r−1 r
Chapter 5: Combinatorics 5-22

Proof:
Consider a set of n + 1 elements. We want to count the number of ways to choose r elements from this set.

• Case 1: The element x is not chosen

If we do not choose the specific element x from the n + 1 elements, then we are left with n elements,
and we need to choose r elements from these n elements. The number of ways to do this is:
 
n
r

• Case 2: The element x is chosen

If we choose the specific element x, then we need to choose the remaining r − 1 elements from the
remaining n elements (since one element is already chosen). The number of ways to do this is:
 
n
r−1

Adding the number of ways from both cases, we get:

   
n n
Total number of ways = +
r r−1

This counts all possible ways to choose r elements from n + 1 elements. Therefore:

     
n+1 n n
= +
r r−1 r

The first few rows of Pascal’s Triangle are:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

Properties:

• Symmetry: Each row is symmetric.

• Binomial Coefficients: The n-th row corresponds to the coefficients of the binomial expansion
(x + y)n .
• Sum of Elements: The sum of the elements in the n-th row is 2n .