Counting Techniques

Overview

In the realm of Data Science, understanding the sheer scale and variety of possibilities is paramount. This chapter, "Counting Techniques," equips you with the fundamental mathematical tools to systematically quantify outcomes, arrangements, and selections. Far from being a mere abstract exercise, these techniques form the bedrock for critical areas such as probability theory, statistical inference, and the analysis of algorithms, enabling you to precisely define sample spaces, evaluate computational complexity, and design robust experiments.

For your CMI examinations, a firm grasp of counting techniques is non-negotiable. You will encounter problems requiring you to determine the number of ways events can occur, calculate the size of data subsets, or analyze the efficiency of different computational approaches. Proficiency in this area ensures you can accurately interpret problem statements, construct valid mathematical models, and arrive at precise solutions, directly impacting your performance in quantitative and analytical sections.

Mastering these foundational principles will not only prepare you for immediate exam challenges but also lay essential groundwork for advanced modules. The ability to count effectively underpins your understanding of discrete probability distributions, sampling methods, and even the combinatorial aspects of machine learning feature engineering. Consider this chapter your essential toolkit for navigating the quantitative landscape of Data Science.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|-------|-------------------|
| 1 | Elementary Counting Principles | Master fundamental rules for simple counts. |
| 2 | Permutations and Combinations | Arrange and select items systematically. |
| 3 | The Binomial Theorem | Expand powers of binomial expressions efficiently. |

---

Learning Objectives

---

Now let's begin with Elementary Counting Principles...

Part 1: Elementary Counting Principles

Introduction

Elementary Counting Principles form the bedrock of combinatorics, a branch of discrete mathematics focused on counting, arrangement, and combination of objects. For the CMI Masters in Data Science exam, a strong grasp of these principles is crucial for solving problems in probability, algorithm analysis, data structures, and various applied mathematics scenarios. This topic covers fundamental techniques for enumerating possibilities, understanding arrangements, and calculating selections, often appearing in logical reasoning and problem-solving sections of the exam.

---

Key Concepts

1. Fundamental Principles of Counting

The two most basic rules are the Sum Rule and the Product Rule, which form the basis for all other counting techniques.

a. The Sum Rule (Rule of Addition)

If a task can be done in one of $m$ ways OR in one of $n$ ways, where the $m$ ways and $n$ ways are mutually exclusive (i.e., cannot occur at the same time), then there are $m + n$ ways to do the task.

b. The Product Rule (Rule of Multiplication)

If a procedure can be broken down into a sequence of two tasks, and there are $m$ ways to do the first task AND $n$ ways to do the second task, then there are $m \times n$ ways to do the procedure. This extends to any number of sequential tasks.

Worked Example:

Problem: A menu offers 3 appetizers, 5 main courses, and 2 desserts. How many different 3-course meals can be ordered?

Solution:

Step 1: Identify the sequence of tasks.
Ordering a meal involves choosing an appetizer, then a main course, then a dessert.

Step 2: Apply the Product Rule.
Number of choices for appetizer = 3
Number of choices for main course = 5
Number of choices for dessert = 2

Answer: $30$ different 3-course meals.

---

2. Permutations

A permutation is an ordered arrangement of objects. The order of selection matters.

a. Permutations of $n$ distinct objects taken $r$ at a time

The number of ways to arrange $r$ objects chosen from $n$ distinct objects is given by:

b. Permutations with Repetition

If there are $n$ objects where $n_1$ are of type 1, $n_2$ are of type 2, ..., $n_k$ are of type $k$, and $n_1 + n_2 + \dots + n_k = n$, then the number of distinct permutations of these $n$ objects is:

c. Circular Permutations

The number of ways to arrange $n$ distinct objects in a circle is $(n-1)!$. This is because in a circle, there's no fixed "start" or "end," so we fix one object's position and arrange the remaining $n-1$ objects relative to it.

Worked Example:

Problem: How many different ways can 5 distinct books be arranged on a shelf?

Solution:

Step 1: Identify the type of arrangement.
This is an arrangement of $n$ objects taken $n$ at a time ($r=n$).

Step 2: Apply the Permutation formula.
Here $n=5$, $r=5$.

Answer: $120$ different ways.

---

3. Combinations

A combination is an unordered selection of objects. The order of selection does not matter.

a. Combinations of $n$ distinct objects taken $r$ at a time

The number of ways to choose $r$ objects from $n$ distinct objects without regard to order is given by:

b. Combinations with Repetition (Stars and Bars)

The number of ways to choose $r$ objects from $n$ types of objects with repetition allowed is given by:

Worked Example:

Problem: A committee of 3 members is to be selected from a group of 10 people. How many different committees can be formed?

Solution:

Step 1: Identify the type of selection.
The order in which members are selected for a committee does not matter, so this is a combination.

Step 2: Apply the Combination formula.
Here $n=10$, $r=3$.

Answer: $120$ different committees.

---

---

4. Principle of Inclusion-Exclusion (PIE)

PIE is used to find the number of elements in the union of multiple sets when the sets are not mutually exclusive. It accounts for elements that might be counted multiple times.

a. For Two Sets

To find the number of elements in the union of two sets $A$ and $B$:

b. For Three Sets

To find the number of elements in the union of three sets $A$, $B$, and $C$:

Worked Example:

Problem: How many positive integers less than 100 are divisible by 2 or 3?

Solution:

Step 1: Define sets.
Let $U = \{1, 2, \dots, 99\}$. Total integers $N=99$.
Let $A$ be the set of integers in $U$ divisible by 2.
Let $B$ be the set of integers in $U$ divisible by 3.

Step 2: Calculate sizes of individual sets.
$|A| = \lfloor 99/2 \rfloor = 49$
$|B| = \lfloor 99/3 \rfloor = 33$

Step 3: Calculate the size of the intersection.
$A \cap B$ is the set of integers divisible by both 2 and 3, i.e., divisible by $\operatorname{lcm}(2,3)=6$.
$|A \cap B| = \lfloor 99/6 \rfloor = 16$

Step 4: Apply PIE for two sets.

Answer: $66$ integers.

---

5. Pigeonhole Principle (PHP)

The Pigeonhole Principle is a powerful tool for proving existence. It states that if you have more "pigeons" than "pigeonholes," at least one pigeonhole must contain more than one pigeon.

a. Basic Form

If $n$ items are put into $m$ containers, with $n > m$, then at least one container must contain more than one item.

b. Generalized Form

If $n$ items are put into $m$ containers, then at least one container must contain at least $\lceil n/m \rceil$ items.

Worked Example:

Problem: In a group of 13 people, show that at least two people must have been born in the same month.

Solution:

Step 1: Identify pigeons and pigeonholes.
Pigeons = 13 people ($n=13$)
Pigeonholes = 12 months in a year ($m=12$)

Step 2: Apply the Pigeonhole Principle.
Since $n=13 > m=12$, by the basic form of the PHP, at least one month (pigeonhole) must contain more than one person (pigeon).

Answer: At least two people must have been born in the same month.

---

6. Combinatorial Arguments & Problem-Solving Techniques

Many CMI problems require applying counting principles in creative ways, often involving specific arguments like coloring, parity, or systematic enumeration.

a. Tiling and Coloring Arguments

These arguments are often used to prove impossibility in tiling problems. By coloring a grid (e.g., a chessboard) in a specific way, one can show that a certain shape of tile cannot cover the grid, usually because it covers an unequal number of colored squares.

Worked Example:

Problem: Can a $4 \times 4$ chessboard be perfectly tiled by $1 \times 3$ trominoes?

Solution:

Step 1: Color the chessboard.
A standard $4 \times 4$ chessboard has 16 squares. A $1 \times 3$ tromino covers 3 squares.
If we color the board with 3 colors (0, 1, 2) such that square $(i,j)$ has color $(i+j) \pmod 3$.

Count the number of squares of each color:
Color 0: 6 squares (e.g., (0,0), (0,3), (1,2), (2,1), (3,0), (3,3))
Color 1: 5 squares
Color 2: 5 squares

A $1 \times 3$ tromino, placed horizontally or vertically, will always cover one square of each color (0, 1, 2) in any cyclic permutation.
For example, if it covers $(i,j), (i,j+1), (i,j+2)$, the colors are $(i+j)\pmod 3$, $(i+j+1)\pmod 3$, $(i+j+2)\pmod 3$, which are $C, C+1, C+2 \pmod 3$. This means it covers one of each color.

Step 2: Check for divisibility and color count.
The total number of squares is 16. Since a tromino covers 3 squares, if it were possible to tile, the total number of squares (16) must be divisible by 3. $16 \pmod 3 = 1 \ne 0$. So it's impossible.
Even if the total number of squares were divisible by 3, the coloring argument strengthens the proof. Each tromino covers one square of each color. If the board were perfectly tiled, there must be an equal number of squares of each color. Here, we have 6 squares of color 0, and 5 each of colors 1 and 2. Since the counts are not equal, it's impossible to tile.

Answer: No, a $4 \times 4$ chessboard cannot be perfectly tiled by $1 \times 3$ trominoes.

b. Parity Arguments

Parity (whether a number is even or odd) can be used to track changes in a system. If a game or process involves operations that always change the parity of a certain quantity, it can be used to determine if a certain state is reachable.

Worked Example (Conceptual):

Problem: Six children are sitting around a circular table. Each child can be either seated or standing. Initially, all are seated. A game rule is: call out initials of a pair of adjacent children, and they both change their state (seated to standing, or vice versa). Can you reach a state where exactly one child is standing?

Solution:

Step 1: Assign numerical states and track parity.
Let 'seated' be 0 and 'standing' be 1. The state of the system is the sum of the states of all children.
Initially, all are seated, so sum = $0+0+0+0+0+0 = 0$ (even parity).
When an adjacent pair changes state:

• If both were 0 (seated), they become 1 (standing): $0+0 \to 1+1$. Change in sum: $+2$. Parity of sum remains even.


• If one was 0, one was 1, they become 1, 0: $0+1 \to 1+0$. Change in sum: $0$. Parity of sum remains even.


• If both were 1 (standing), they become 0 (seated): $1+1 \to 0+0$. Change in sum: $-2$. Parity of sum remains even.

Step 2: Analyze the target state.
Target state: exactly one child standing. Sum of states = 1 (odd parity).

Step 3: Conclusion.
Since each operation preserves the even parity of the total number of standing children, it is impossible to reach a state with an odd number of standing children (like exactly one standing).

Answer: No, it is not possible to reach a state where exactly one child is standing.

c. Systematic Enumeration (e.g., Counting Squares on a Grid)

Some problems involve counting objects of varying sizes within a larger structure. This often requires systematic enumeration, possibly leading to a summation formula.

Worked Example:

Problem: How many squares are there on an $n \times n$ chessboard?

Solution:

Step 1: Identify types of squares.
Squares can be of size $1 \times 1$, $2 \times 2$, $3 \times 3$, ..., up to $n \times n$.

Step 2: Count squares of each size.

• For $1 \times 1$ squares: There are $n$ rows and $n$ columns, so $n \times n = n^2$ squares.


• For $2 \times 2$ squares: The top-left corner of a $2 \times 2$ square can be at any position from row 1 to row $n-1$, and column 1 to column $n-1$. So there are $(n-1) \times (n-1) = (n-1)^2$ squares.


• For $k \times k$ squares: Similarly, there are $(n-k+1) \times (n-k+1) = (n-k+1)^2$ squares.


• This continues until $n \times n$ squares: There is only $(n-n+1)^2 = 1^2 = 1$ such square.

Step 3: Sum the counts.
The total number of squares is the sum of squares of all possible sizes:

This is the sum of the first $n$ square numbers.

Answer: $\frac{n(n+1)(2n+1)}{6}$ squares. For a $7 \times 7$ board, this is $\frac{7(7+1)(2 \times 7+1)}{6} = \frac{7 \times 8 \times 15}{6} = 7 \times 4 \times 5 = 140$.

d. Longest Common Subsequence (LCS) - Length and Count

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. A common subsequence of two strings is a subsequence that is common to both. The Longest Common Subsequence (LCS) is the common subsequence with the greatest length.

While finding the length of an LCS is typically done using dynamic programming, counting the number of distinct LCS can be a combinatorial problem.

Length of LCS:
Let $S_1$ be a string of length $m$ and $S_2$ be a string of length $n$. Let $LCS(i, j)$ be the length of the LCS of $S_1[1 \dots i]$ and $S_2[1 \dots j]$.
If $S_1[i] = S_2[j]$, then $LCS(i,j) = 1 + LCS(i-1, j-1)$.
If $S_1[i] \ne S_2[j]$, then $LCS(i,j) = \max(LCS(i-1, j), LCS(i, j-1))$.

Counting Number of LCS:
Let $CountLCS(i, j)$ be the number of distinct LCS of $S_1[1 \dots i]$ and $S_2[1 \dots j]$.
Base cases: $CountLCS(i, 0) = 1$ for all $i \ge 0$, $CountLCS(0, j) = 1$ for all $j \ge 0$. (An empty string has one LCS: the empty string itself).

If $S_1[i] = S_2[j]$:
The characters match, so we extend all LCS of $S_1[1 \dots i-1]$ and $S_2[1 \dots j-1]$ by this character.

If $S_1[i] \ne S_2[j]$:
We need to consider the LCS from $S_1[1 \dots i-1], S_2[1 \dots j]$ and $S_1[1 \dots i], S_2[1 \dots j-1]$.
Let $L_1 = LCS(i-1, j)$ and $L_2 = LCS(i, j-1)$.
If $L_1 > L_2$: The LCS comes only from $S_1[1 \dots i-1], S_2[1 \dots j]$.

If $L_2 > L_1$: The LCS comes only from $S_1[1 \dots i], S_2[1 \dots j-1]$.

If $L_1 = L_2$: The LCS can come from both paths. We need to sum the counts. However, we must subtract the count of common subsequences that are counted twice (those formed from $S_1[1 \dots i-1], S_2[1 \dots j-1]$).

This subtraction is for the case where the longest common subsequences from $LCS(i-1, j)$ and $LCS(i, j-1)$ also include those from $LCS(i-1, j-1)$. This is an application of PIE.

Worked Example (Conceptual):

Problem: For strings $S_1 = \text{"ABABA"}$ and $S_2 = \text{"BABAB"}$, find the length and number of LCS.

Solution:

Step 1: Compute LCS length table (standard DP).
Length is 4. (e.g., "ABAB", "BABA").

Step 2: Compute LCS count table.
Using the rules above, carefully populate a DP table for counts.
For $S_1 = \text{"ABABA"}$, $S_2 = \text{"BABAB"}$:
LCS length is 4.
The LCS are "ABAB" and "BABA".
The number of LCS is 2.

Answer: Length $x=4$, Number $y=2$.

---

7. Connectivity and Design Principles (Elevator Problem Type)

Problems involving resource allocation, connectivity, and constraints on subsets (like the elevator problem) often combine counting with design theory. These problems typically involve:

Double Counting: Summing quantities in two different ways to establish an inequality or equality.

Extremal Arguments: Determining maximum or minimum possible values under given constraints.

Existence Proofs: Showing if a configuration is possible or impossible.

Worked Example (Conceptual - based on PYQ 9):

Problem: There are $E$ elevators in a mall, each stopping at the ground floor and at most $k$ other floors. At least $r$ elevators stop at each floor. It is possible to go from any floor to any other floor without changing elevators. What is the maximum number of floors in the mall?

Solution Approach:

Step 1: Define variables.
Let $N$ be the total number of floors.
Let $E_j$ be the $j$-th elevator, stopping at $k_j$ floors (including ground). So $k_j \le k+1$.
Let $F_i$ be the $i$-th floor. Let $r_i$ be the number of elevators stopping at $F_i$. So $r_i \ge r$.

Step 2: Apply double counting for total stops.
The total number of (floor, elevator) pairs, where the elevator stops at the floor, can be counted in two ways:
Sum over elevators: $\sum_{j=1}^E k_j$
Sum over floors: $\sum_{i=1}^N r_i$
So, $\sum_{i=1}^N r_i = \sum_{j=1}^E k_j$.
Using the constraints: $rN \le \sum_{i=1}^N r_i = \sum_{j=1}^E k_j \le E \times (k+1)$.
Thus, $rN \le E(k+1) \implies N \le \frac{E(k+1)}{r}$. This gives an upper bound for $N$.

Step 3: Apply connectivity condition (covering pairs).
"Possible to go from any floor to any other floor without changing elevators" means that for any pair of distinct floors $\{F_a, F_b\}$, there must be at least one elevator $E_j$ that stops at both $F_a$ and $F_b$.
The total number of distinct pairs of floors is $\binom{N}{2}$.
Each elevator $E_j$ stops at $k_j$ floors, covering $\binom{k_j}{2}$ pairs.
So, $\binom{N}{2} \le \sum_{j=1}^E \binom{k_j}{2}$.
Using the constraint $k_j \le k+1$:
$\binom{N}{2} \le E \times \binom{k+1}{2}$. This gives another upper bound for $N$.

Step 4: Combine bounds and check for existence.
The maximum $N$ must satisfy both upper bounds. The tighter bound will be the maximum.
For PYQ 9: $E=7$, $k=6$ (meaning $k+1=7$ floors per elevator), $r=3$.
From Step 2: $3N \le 7 \times 7 = 49 \implies N \le \lfloor 49/3 \rfloor = 16$.
From Step 3: $\binom{N}{2} \le 7 \times \binom{7}{2} = 7 \times 21 = 147$.
$N(N-1) \le 294$.
For $N=17$, $17 \times 16 = 272 \le 294$.
For $N=18$, $18 \times 17 = 306 > 294$.
So $N \le 17$.
Combining both, $N \le \min(16, 17) = 16$.

Step 5: Check if $N=16$ is achievable.
If $N=16$, then $3 \times 16 = 48$. This means $\sum r_i \ge 48$.
Also $\sum k_j \le 49$.
So, to achieve $N=16$, we must have $\sum r_i = 48$ or $49$, and $\sum k_j = 48$ or $49$.
If $\sum r_i = 48$, then all $r_i$ must be exactly 3. And $\sum k_j = 48$. This means the 7 elevators must visit an average of $48/7 \approx 6.85$ floors each. For example, six elevators visit 7 floors each, and one visits 6 floors.
It turns out that a combinatorial design satisfying these conditions ($N=16$, each floor on exactly 3 elevators, elevators covering specific number of floors, and all pairs connected) does not exist. This is a known result in design theory.
Therefore, $N=16$ is not possible. The maximum possible value is $N=15$.

Answer: $N=15$.

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="A standard deck of 52 cards has 4 suits, each with 13 ranks. How many 5-card hands can be formed that contain exactly three aces?" options=["4512","65800","42300","4896"] answer="4512" hint="Break the problem into two independent choices: choosing aces and choosing non-aces." solution="Step 1: Choose 3 aces from the 4 available aces. This is a combination:

Step 2: Choose the remaining 2 cards from the non-ace cards. There are $52 - 4 = 48$ non-ace cards.

Step 3: Apply the Product Rule to combine these choices.

Answer: $\boxed{4512}$"
:::

:::question type="NAT" question="How many positive integers less than 500 are divisible by 4 or 6, but not by 10?" answer="133" hint="Use PIE for divisibility by 4 or 6. Then, use PIE again to exclude numbers divisible by 10 from this set." solution="Let $U = \{1, 2, \dots, 499\}$. Total integers $N = 499$.

Step 1: Find integers divisible by 4 or 6.
Let $A$ be divisible by 4: $|A| = \lfloor 499/4 \rfloor = 124$.
Let $B$ be divisible by 6: $|B| = \lfloor 499/6 \rfloor = 83$.
$A \cap B$ are divisible by $\text{lcm}(4,6) = 12$: $|A \cap B| = \lfloor 499/12 \rfloor = 41$.
Integers divisible by 4 or 6: $|A \cup B| = |A| + |B| - |A \cap B| = 124 + 83 - 41 = 166$.

Step 2: Find integers divisible by 10 that are also divisible by 4 or 6.
Let $C$ be divisible by 10. We want to exclude $(A \cup B) \cap C$.
$(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$.
$A \cap C$ are divisible by $\text{lcm}(4,10) = 20$: $|A \cap C| = \lfloor 499/20 \rfloor = 24$.
$B \cap C$ are divisible by $\text{lcm}(6,10) = 30$: $|B \cap C| = \lfloor 499/30 \rfloor = 16$.
$(A \cap C) \cap (B \cap C)$ are divisible by $\text{lcm}(20,30) = 60$: $|A \cap B \cap C| = \lfloor 499/60 \rfloor = 8$.
Using PIE for $(A \cap C) \cup (B \cap C)$:
$|(A \cup B) \cap C| = |A \cap C| + |B \cap C| - |A \cap B \cap C| = 24 + 16 - 8 = 32$.

Step 3: Subtract the excluded count from the total of (4 or 6).
Result = $|A \cup B| - |(A \cup B) \cap C| = 166 - 32 = 134$.
Answer: $\boxed{134}$"
:::

---

---

Part 2: Permutations and Combinations

Introduction

Permutations and Combinations form the bedrock of combinatorics, a branch of discrete mathematics focused on counting, arrangement, and selection. In the context of a Masters in Data Science, these techniques are crucial for understanding probability, analyzing algorithms, designing experiments, and working with complex data structures. For the CMI exam, a deep understanding of these concepts is essential, as they frequently appear in various forms, often requiring a combination of different counting principles and advanced problem-solving strategies.

This chapter will delve into the fundamental principles of counting, exploring how to systematically determine the number of possible arrangements and selections of objects. We will cover linear and circular permutations, basic and constrained combinations, and introduce advanced techniques like the Principle of Inclusion-Exclusion and Derangements, which are vital for tackling more complex counting problems. Mastery of these methods will equip you to approach a wide range of CMI-style questions effectively.

---

Key Concepts

1. Fundamental Principles of Counting

The two most basic principles in combinatorics are the Multiplication Principle and the Addition Principle. They form the basis for solving almost all counting problems.

1.1. The Multiplication Principle

If an event can occur in $m$ ways, and after it occurs, another independent event can occur in $n$ ways, then the two events can occur in $m \times n$ ways. This principle extends to any number of sequential independent events.

Worked Example:

Problem: A menu offers 3 appetizers, 5 main courses, and 2 desserts. How many different 3-course meals can be ordered?

Solution:

Step 1: Identify the number of choices for each stage of the meal.

• Appetizer: 3 choices
• Main Course: 5 choices
• Dessert: 2 choices

Step 2: Apply the Multiplication Principle.

Step 3: Calculate the total number of meals.

Answer: $\boxed{30}$

---

1.2. The Addition Principle

If an event can occur in $m$ ways OR in $n$ ways, and these two ways cannot occur simultaneously (they are mutually exclusive), then the event can occur in $m + n$ ways. This principle extends to any number of mutually exclusive events.

Worked Example:

Problem: A student can choose a project from three categories: Programming (4 options), Research (3 options), or Design (2 options). How many total project options are there if they must choose exactly one project?

Solution:

Step 1: Identify the number of options in each category.

• Programming: 4 options
• Research: 3 options
• Design: 2 options

Step 2: Apply the Addition Principle as the choices are mutually exclusive.

Step 3: Calculate the total number of options.

Answer: $\boxed{9}$

---

2. Permutations

A permutation is an arrangement of objects in a specific order. The order of selection matters.

2.1. Linear Permutations

The number of ways to arrange $n$ distinct objects is $n!$ (n factorial). The number of ways to arrange $k$ objects chosen from $n$ distinct objects is denoted by $P(n, k)$ or $_nP_k$.

Worked Example:

Problem: In how many ways can 5 different books be arranged on a shelf?

Solution:

Step 1: Identify $n$ (total objects) and $k$ (objects to arrange).
Here, $n = 5$ and $k = 5$ (all books are arranged).

Step 2: Apply the permutation formula for all objects.

Step 3: Calculate the factorial.

Answer: $\boxed{120}$

---

2.2. Permutations with Repetition

If there are $n$ objects where $n_1$ are of one type, $n_2$ are of another type, ..., $n_k$ are of a $k$-th type, and $n_1 + n_2 + \dots + n_k = n$, then the number of distinct permutations is given by:

Worked Example:

Problem: How many distinct permutations can be formed using the letters of the word "MISSISSIPPI"?

Solution:

Step 1: Count the total number of letters and the frequency of each distinct letter.

• Total letters $n = 11$
• M: $n_M = 1$
• I: $n_I = 4$
• S: $n_S = 4$
• P: $n_P = 2$

Step 2: Apply the formula for permutations with repetition.

Step 3: Calculate the value.

Answer: $34,650$

---

2.3. Circular Permutations

The number of ways to arrange $n$ distinct objects in a circle is $(n-1)!$. This is because in a circular arrangement, rotations of the same arrangement are considered identical. We fix one object's position to eliminate these rotations.

If arrangements are considered the same when reflected (e.g., beads on a necklace), the formula changes to $\frac{(n-1)!}{2}$ for $n \ge 3$.

Worked Example:

Problem: 5 friends are to be seated around a circular table. In how many distinct ways can they be seated?

Solution:

Step 1: Identify $n$ (total distinct objects).
Here, $n=5$.

Step 2: Apply the circular permutation formula.

Step 3: Calculate the factorial.

Answer: $24$

---

2.4. Permutations with Constraints (Grouping and Alternating)

Many problems involve placing restrictions on arrangements, such as certain objects always sitting together or alternating positions.

Grouping Method: When items must sit together, treat them as a single unit. Arrange this unit with the other items, then arrange the items within the unit.

Alternating Arrangements: For alternating patterns (e.g., male/female, DS/CS students), consider arranging one group first, then placing the other group in the gaps.

Worked Example (Grouping):

Problem: 5 people (A, B, C, D, E) are to be seated in a row. In how many ways can they be seated if A and B must sit together?

Solution:

Step 1: Treat A and B as a single unit.
Now we are arranging 4 "items": (AB), C, D, E.

Step 2: Arrange these 4 items linearly.

Step 3: Consider the internal arrangement of the unit (AB).
A and B can sit as AB or BA. So there are $2!$ ways to arrange them.

Step 4: Multiply the arrangements of the units by the internal arrangements.

Answer: $48$

---

Worked Example (Alternating):

Problem: 3 boys and 3 girls are to be seated in a row such that no two students of the same gender sit next to each other.

Solution:

Step 1: Consider the possible alternating patterns.
Since there are equal numbers of boys and girls, the patterns must be B G B G B G or G B G B G B.

Step 2: Calculate arrangements for the first pattern (B G B G B G).
Arrange the 3 boys in $3!$ ways. Arrange the 3 girls in $3!$ ways.

Step 3: Calculate arrangements for the second pattern (G B G B G B).
Similarly, $3! \times 3! = 36$.

Step 4: Add the results for the mutually exclusive patterns.

Answer: $72$

---

3. Combinations

A combination is a selection of objects where the order of selection does not matter. The number of ways to choose $k$ objects from $n$ distinct objects is denoted by $\binom{n}{k}$ or $C(n, k)$ or $_nC_k$.

Worked Example:

Problem: A committee of 3 members is to be chosen from a group of 8 people. How many different committees can be formed?

Solution:

Step 1: Identify $n$ (total objects) and $k$ (objects to choose).
Here, $n=8$ and $k=3$. Order does not matter for committee members.

Step 2: Apply the combination formula.

Step 3: Calculate the value.

Answer: $56$

---

3.1. Combinations with Repetition (Stars and Bars)

This technique is used to count the number of ways to distribute $k$ identical items into $n$ distinct bins, or to select $k$ items from $n$ types with replacement.

Worked Example:

Problem: In how many ways can 10 identical chocolate bars be distributed among 5 children?

Solution:

Step 1: Identify $k$ (identical items) and $n$ (distinct bins).
Here, $k=10$ (chocolate bars) and $n=5$ (children).

Step 2: Apply the Stars and Bars formula.

Step 3: Calculate the value.

Answer: $1001$

---

---

Constraint: Each bin gets at least one item.
If each of the $n$ bins must receive at least one item, we first place one item in each bin. This leaves $k-n$ items to distribute among $n$ bins without further restrictions.

Worked Example:

Problem: In how many ways can 10 identical chocolate bars be distributed among 5 children, such that each child gets at least one chocolate bar?

Solution:

Step 1: Identify $k$ (total items) and $n$ (total bins).
Here, $k=10$ and $n=5$.

Step 2: Apply the Stars and Bars formula with the minimum requirement.

Step 3: Calculate the value.

Answer: \boxed{126}

---

4. Advanced Counting Techniques

4.1. Principle of Inclusion-Exclusion (PIE)

PIE is used to find the size of the union of multiple sets. For two sets A and B:
$|A \cup B| = |A| + |B| - |A \cap B|$

For three sets A, B, and C:
$|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C|$

In general, for $N$ sets, it involves summing the sizes of individual sets, subtracting the sizes of all pairwise intersections, adding the sizes of all three-way intersections, and so on, alternating signs.

4.2. Derangements

A derangement is a permutation of objects such that no object ends up in its original position (i.e., no fixed points). The number of derangements of $n$ objects is denoted by $D_n$ or $!n$.

Worked Example:

Problem: Four friends leave their coats at a checkroom. In how many ways can they each receive a coat that does not belong to them?

Solution:

Step 1: Identify $n$ (number of objects to be deranged).
Here, $n=4$.

Step 2: Apply the derangement formula.

Step 3: Calculate the value.

Answer: \boxed{9}

---

4.3. Functions and Mappings

Counting different types of functions between sets $A$ and $B$, where $|A|=m$ and $|B|=n$.

Total functions: Each of the $m$ elements in $A$ can map to any of the $n$ elements in $B$. So, $n^m$.

Injective (one-to-one) functions: Each element of $A$ maps to a unique element of $B$. This requires $m \le n$. The number of ways is $P(n, m) = \frac{n!}{(n-m)!}$.

Bijective (one-to-one and onto) functions: Each element of $A$ maps to a unique element of $B$, and every element of $B$ is mapped to. This requires $m=n$. The number of ways is $n!$. These are essentially permutations.

Surjective (onto) functions: Every element in $B$ must be mapped to by at least one element from $A$. This requires $m \ge n$. The number of surjective functions can be found using PIE or Stirling Numbers of the Second Kind.

The number of surjective functions from a set of size $m$ to a set of size $n$ is:

where $S(m, n)$ is a Stirling number of the second kind.
Alternatively, using PIE:

Idempotent Functions ($f \circ f = f$):
A function $f: X \to X$ such that $f(f(x)) = f(x)$ for all $x \in X$.
If $y$ is in the range of $f$ (i.e., $y=f(x)$ for some $x$), then $f(y)=y$. This means all elements in the range are fixed points.
To count idempotent functions:
Step 1: Choose the $k$ elements that form the range. $\binom{n}{k}$ ways.
Step 2: For each of these $k$ range elements, they must map to themselves (fixed points). $k^k$ maps.
Step 3: For the remaining $n-k$ elements in the domain (not in the range), each must map to one of the $k$ chosen range elements. $k^{n-k}$ ways.
So, for a fixed range size $k$: $\binom{n}{k} k^{n-k}$.
Sum this over all possible range sizes $k$ from $1$ to $n$: $\sum_{k=1}^{n} \binom{n}{k} k^{n-k}$.

Worked Example (Idempotent Functions):

Problem: Let $S$ be the set of all functions from $\{1,2,3\}$ to $\{1,2,3\}$ such that $f \circ f = f$. Compute the number of functions $f \in S$.

Solution:

Step 1: Use the formula $\sum_{k=1}^{n} \binom{n}{k} k^{n-k}$ for $n=3$.

Step 2: Calculate for $k=1$:
Range size 1: Choose 1 element for range $\binom{3}{1}$. The 3 domain elements map to this 1 range element.

Step 3: Calculate for $k=2$:
Range size 2: Choose 2 elements for range $\binom{3}{2}$. The 3 domain elements must map to these 2 range elements, with the 2 range elements being fixed points.

Step 4: Calculate for $k=3$:
Range size 3: Choose 3 elements for range $\binom{3}{3}$. The 3 domain elements map to these 3 range elements, with the 3 range elements being fixed points. This implies a bijection to the range itself.

Step 5: Sum the results.

Answer: \boxed{10}

---

4.4. Catalan Numbers

Catalan numbers ($C_n$) are a sequence of natural numbers that appear in various counting problems, often involving recursive structures.

For binary trees with $n$ nodes, the formula is $C_n$.
$C_0 = 1$ (empty tree)
$C_1 = 1$ (single root)
$C_2 = \frac{1}{3}\binom{4}{2} = \frac{1}{3} \times 6 = 2$
$C_3 = \frac{1}{4}\binom{6}{3} = \frac{1}{4} \times 20 = 5$
$C_4 = \frac{1}{5}\binom{8}{4} = \frac{1}{5} \times 70 = 14$

The diagram shows the 5 binary trees with 3 nodes ($C_3=5$).

---

4.5. Permutation Cycles and Order

A permutation can be decomposed into disjoint cycles. For example, $\sigma = (1\ 2\ 3)(4\ 5)$.

• Cycle Length: The number of elements in a cycle.
• Order of a Permutation: The smallest positive integer $k$ such that $\sigma^k$ is the identity permutation. It is the least common multiple (LCM) of the lengths of its disjoint cycles.

Worked Example:

Problem: Consider the permutation

Find its cycle decomposition and order.

Solution:

Step 1: Trace the cycles.
Start with 1: $1 \to 2 \to 3 \to 4 \to 5 \to 1$. This forms a cycle $(1\ 2\ 3\ 4\ 5)$.
The remaining element is 6: $6 \to 6$. This forms a cycle $(6)$.

Step 2: Write the cycle decomposition.

Step 3: Find the lengths of the disjoint cycles.
Lengths are 5 and 1.

Step 4: Calculate the LCM of the cycle lengths.

Answer: \boxed{\text{Cycle decomposition is } (1\ 2\ 3\ 4\ 5)(6), \text{ and its order is } 5.}

---

Problem-Solving Strategies

---

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="A committee of 7 members is to be formed from 10 men and 8 women. How many committees can be formed if there must be at least 3 men and at least 3 women?" options=["$\binom{10}{3}\binom{8}{4} + \binom{10}{4}\binom{8}{3}$","$\binom{10}{3}\binom{8}{4} + \binom{10}{4}\binom{8}{3} + \binom{10}{5}\binom{8}{2}$","$\binom{10}{3}\binom{8}{4} + \binom{10}{4}\binom{8}{3} + \binom{10}{5}\binom{8}{2} + \binom{10}{2}\binom{8}{5}$","$\binom{18}{7} - (\text{committees with <3 men or <3 women})$"] answer="$\binom{10}{3}\binom{8}{4} + \binom{10}{4}\binom{8}{3}$" hint="Consider the possible valid combinations of men and women that sum to 7, satisfying the minimums for both genders." solution="Let $M$ be the number of men and $W$ be the number of women chosen. We need $M+W=7$, with $M \ge 3$ and $W \ge 3$.

Possible combinations for $(M, W)$:

If $M=3$, then $W=4$. Number of ways: $\binom{10}{3}\binom{8}{4}$

If $M=4$, then $W=3$. Number of ways: $\binom{10}{4}\binom{8}{3}$

If $M=2$, $W=5$, but this violates $M \ge 3$.
If $M=5$, $W=2$, but this violates $W \ge 3$.

So, these are the only two valid cases. Since these cases are mutually exclusive, we add the number of ways for each case.

Total ways = $\binom{10}{3}\binom{8}{4} + \binom{10}{4}\binom{8}{3}$"
:::

:::question type="NAT" question="Six distinct books are to be arranged on a shelf. Three specific books (A, B, C) must always be kept together in that specific order (ABC). How many distinct arrangements are possible?" answer="24" hint="Treat the fixed sequence of books as a single unit." solution="Step 1: Treat the three specific books (A, B, C) as a single block 'ABC'.
Step 2: Now we are arranging this block 'ABC' and the remaining $6-3=3$ books. So, we are arranging 4 items (the block and 3 individual books).
Step 3: The number of ways to arrange these 4 distinct items is $4!$.

Since the order of A, B, C within their block is fixed as 'ABC', there is only 1 way to arrange them internally."
:::

:::question type="MSQ" question="Which of the following statements about permutations and combinations are true?" options=["The number of ways to choose $k$ items from $n$ distinct items is $\binom{n}{k}$.","The number of ways to arrange $n$ distinct items in a line is $n!$.","The number of ways to distribute $k$ identical items into $n$ distinct bins such that each bin gets at least one item is $\binom{k-1}{n-1}$.","The number of bijective functions from a set of size $m$ to a set of size $n$ is $n^m$." ] answer="A,B,C" hint="Review the definitions and formulas for basic combinations, linear permutations, Stars and Bars with minimums, and bijective functions." solution="A. True. This is the definition of combinations.
B. True. This is the definition of linear permutations of $n$ distinct items.
C. True. This is the formula for Stars and Bars with the constraint that each bin receives at least one item.
D. False. The number of bijective functions from a set of size $m$ to a set of size $n$ is $m!$ if $m=n$, and 0 otherwise. $n^m$ is the total number of functions from a set of size $m$ to a set of size $n$."
:::

:::question type="SUB" question="Derive the formula for the number of ways to distribute $k$ identical items into $n$ distinct bins using the Stars and Bars method, assuming each bin can be empty." answer="The number of ways is $\binom{k+n-1}{k}$ or $\binom{k+n-1}{n-1}$." hint="Represent the identical items as 'stars' and the divisions between bins as 'bars'. Consider how many positions are available for stars and bars." solution="Step 1: Represent the $k$ identical items as $k$ 'stars' (*).

Step 2: To divide these $k$ stars into $n$ distinct bins, we need $n-1$ 'bars' (|). For example, if $n=3$, we need $2$ bars to create 3 bins.

Step 3: Imagine we have a total of $k$ stars and $n-1$ bars. These $k + (n-1)$ symbols must be arranged in a line. The arrangement of these symbols uniquely determines the distribution of stars into bins. For instance, stars before the first bar go into bin 1, stars between the first and second bar go into bin 2, and so on.

Step 4: The total number of positions for these symbols is $k + n - 1$. We need to choose $k$ of these positions to be stars (the remaining $n-1$ positions will automatically be bars), OR we need to choose $n-1$ of these positions to be bars (the remaining $k$ positions will automatically be stars).

Step 5: Using the combination formula, the number of ways to choose $k$ positions for stars from $k+n-1$ total positions is $\binom{k+n-1}{k}$.
Alternatively, the number of ways to choose $n-1$ positions for bars from $k+n-1$ total positions is $\binom{k+n-1}{n-1}$.

Since $\binom{N}{K} = \binom{N}{N-K}$, these two expressions are equivalent:

Thus, the formula for distributing $k$ identical items into $n$ distinct bins is $\binom{k+n-1}{k}$ or $\binom{k+n-1}{n-1}$."
:::

:::question type="MCQ" question="In a round-robin chess tournament with 8 players, each player plays every other player exactly once. How many games are played in total?" options=["16","28","56","64"] answer="28" hint="The order of players in a game doesn't matter (Player A vs Player B is the same as Player B vs Player A)." solution="Step 1: Identify $n$ (total players) and $k$ (players in each game).
Here, $n=8$ players. Each game involves 2 players, so $k=2$.
Step 2: Determine if order matters.
In a chess game between two players, the order in which they are chosen does not matter (Player 1 vs Player 2 is the same game as Player 2 vs Player 1). Therefore, this is a combination problem.
Step 3: Apply the combination formula $\binom{n}{k}$.

Step 4: Calculate the value.

Total games played are 28."
:::

:::question type="NAT" question="A 5-digit number is to be formed using the digits {0, 1, 2, 3, 4} without repetition. How many such numbers are even?" answer="60" hint="An even number must end in an even digit (0, 2, or 4). Consider cases based on the last digit and the first digit." solution="A 5-digit number cannot start with 0. An even number must end with an even digit (0, 2, 4).

Case 1: The number ends with 0.
- Last digit: 1 choice (0)
- First digit: 4 choices (1, 2, 3, 4, since 0 is used and it cannot be 0)
- Remaining 3 digits: $4-1=3$ digits left for the remaining $5-2=3$ positions. These can be arranged in $3!$ ways.
- Number of ways: $1 \times 4 \times 3! = 1 \times 4 \times 6 = 24$

Case 2: The number ends with 2.
- Last digit: 1 choice (2)
- First digit: 3 choices (1, 3, 4, since 0 cannot be the first digit and 2 is used)
- Remaining 3 digits: $5-2=3$ digits left for the remaining 3 positions. These can be arranged in $3!$ ways.
- Number of ways: $1 \times 3 \times 3! = 1 \times 3 \times 6 = 18$

Case 3: The number ends with 4.
- Last digit: 1 choice (4)
- First digit: 3 choices (1, 2, 3, since 0 cannot be the first digit and 4 is used)
- Remaining 3 digits: $5-2=3$ digits left for the remaining 3 positions. These can be arranged in $3!$ ways.
- Number of ways: $1 \times 3 \times 3! = 1 \times 3 \times 6 = 18$

Total even numbers = Sum of ways from all cases (Addition Principle).

"
:::

---

Summary

---

What's Next?

---

---

Part 3: The Binomial Theorem

Introduction

The Binomial Theorem is a fundamental principle in combinatorics and algebra, providing a systematic method for expanding expressions of the form $(x+y)^n$ for any non-negative integer $n$. It is essential for understanding polynomial expansions, probability distributions, and various counting problems. This topic builds foundational skills in manipulating algebraic expressions and understanding combinatorial identities, which are critical for advanced topics in discrete mathematics and data science applications, such as analyzing algorithms involving selections or distributions.

This section will thoroughly cover the definition of binomial coefficients, the Binomial Theorem itself, and its generalization, the Multinomial Theorem. Mastery of these concepts is crucial for solving problems involving combinations, probability calculations, and coefficient extraction in polynomial series, frequently encountered in CMI examinations.

---

---

Key Concepts

1. Properties of Binomial Coefficients

Binomial coefficients possess several important properties that simplify calculations and derivations.

Property 1: Symmetry

Proof:

Step 1: Start with the definition of $\binom{n}{k}$

Step 2: Start with the definition of $\binom{n}{n-k}$

Step 3: Simplify the denominator for $\binom{n}{n-k}$

Step 4: Compare the two expressions
Since $k!(n-k)! = (n-k)!k!$, we have $\binom{n}{k} = \binom{n}{n-k}$.

Property 2: Base Cases

Proof:

Step 1: For $\binom{n}{0}$, apply the definition

Step 2: Use the convention $0! = 1$

Step 3: For $\binom{n}{n}$, apply the definition

Step 4: Simplify the expression

Property 3: Pascal's Identity

Proof (Combinatorial Argument):
Consider a set $S$ of $n$ distinct items. We want to choose $k$ items from $S$. The total number of ways to do this is $\binom{n}{k}$.

Let's pick one specific item from the set, say item 'A'. When choosing $k$ items from $S$, there are two mutually exclusive possibilities:

Item 'A' is included in the selection: If 'A' is included, we need to choose $k-1$ additional items from the remaining $n-1$ items (all items except 'A'). The number of ways to do this is $\binom{n-1}{k-1}$.

Item 'A' is NOT included in the selection: If 'A' is not included, we need to choose all $k$ items from the remaining $n-1$ items (all items except 'A'). The number of ways to do this is $\binom{n-1}{k}$.

Since these two cases cover all possibilities and are mutually exclusive, the total number of ways to choose $k$ items from $n$ is the sum of the ways in these two cases:

This completes the combinatorial proof.

---

2. The Binomial Theorem

The Binomial Theorem provides a formula for the algebraic expansion of powers of a binomial $(x+y)^n$.

Proof (Combinatorial Argument):
Consider the expansion of $(x+y)^n$:

When we expand this product, each term in the result is obtained by choosing either $x$ or $y$ from each of the $n$ factors. A generic term will be of the form $x^{n-k}y^k$, where $k$ is the number of times $y$ is chosen (and $n-k$ is the number of times $x$ is chosen).

To find the coefficient of $x^{n-k}y^k$, we need to determine how many ways we can choose $y$ from $k$ of the $n$ factors (and $x$ from the remaining $n-k$ factors). This is precisely the definition of a binomial coefficient: the number of ways to choose $k$ positions for $y$ out of $n$ available positions is $\binom{n}{k}$.

Therefore, the coefficient of $x^{n-k}y^k$ is $\binom{n}{k}$, leading to the Binomial Theorem:

General Term:
The $(k+1)$-th term in the expansion of $(x+y)^n$ is given by $T_{k+1} = \binom{n}{k} x^{n-k} y^k$.

Worked Example: Expanding a Binomial

Problem: Expand $(2a - 3b)^3$.

Solution:

Step 1: Identify $n, x, y$
Here, $n=3$, $x=2a$, and $y=-3b$.

Step 2: Apply the Binomial Theorem formula

Step 3: Expand for each value of $k$ from $0$ to $3$

For $k=0$:

For $k=1$:

For $k=2$:

For $k=3$:

Step 4: Sum the terms

Answer: $\boxed{8a^3 - 36a^2b + 54ab^2 - 27b^3}$

---

3. The Multinomial Theorem

The Binomial Theorem is a special case of the Multinomial Theorem, which provides a formula for expanding powers of a sum with more than two terms. This is particularly relevant when dealing with expressions like $(x_1 + x_2 + \dots + x_k)^n$.

Combinatorial Interpretation of Multinomial Coefficients:
The multinomial coefficient $\frac{n!}{n_1!n_2!\dots n_k!}$ represents the number of ways to arrange $n$ objects where there are $n_1$ identical objects of type 1, $n_2$ identical objects of type 2, ..., $n_k$ identical objects of type $k$, and $n_1 + n_2 + \dots + n_k = n$.

Alternatively, it represents the number of ways to partition a set of $n$ distinct items into $k$ distinct subsets of sizes $n_1, n_2, \dots, n_k$.

Worked Example: Finding a Specific Coefficient in a Trinomial Expansion

Problem: Find the coefficient of $a^2 b^3 c^1$ in the expansion of $(a + b + c)^6$.

Solution:

Step 1: Identify $n, k$ and the desired exponents
Here, $n=6$, and we have $k=3$ terms ($a, b, c$).
We want the term $a^{n_1} b^{n_2} c^{n_3}$ where $n_1=2, n_2=3, n_3=1$.

Step 2: Verify that the exponents sum to $n$
$n_1 + n_2 + n_3 = 2 + 3 + 1 = 6$. This matches $n=6$.

Step 3: Apply the Multinomial Theorem to find the coefficient
The coefficient is $\frac{n!}{n_1!n_2!n_3!}$.

Step 4: Calculate the factorial values

Step 5: Substitute and calculate

Answer: $\boxed{60}$

Worked Example: Finding a Specific Coefficient with Internal Coefficients (Similar to PYQ concept)

Problem: What is the coefficient of $x^4$ in the expansion of $(1 + 2x + x^2)^3$?

Solution:

Step 1: Identify $n, k$ and the terms in the base
Here, $n=3$. The base has $k=3$ terms: $1$, $2x$, and $x^2$.
Let $y_1=1$, $y_2=2x$, $y_3=x^2$.
The expansion is $(y_1 + y_2 + y_3)^3$.
A general term in the expansion is $\frac{3!}{n_1!n_2!n_3!} (y_1)^{n_1} (y_2)^{n_2} (y_3)^{n_3}$, where $n_1+n_2+n_3=3$.

Step 2: Substitute the terms back in
The general term is $\frac{3!}{n_1!n_2!n_3!} (1)^{n_1} (2x)^{n_2} (x^2)^{n_3}$.
This simplifies to $\frac{3!}{n_1!n_2!n_3!} (2^{n_2}) x^{n_2 + 2n_3}$.

Step 3: Set up the conditions for the desired term
We need the coefficient of $x^4$, so the power of $x$ must be $4$:

And the sum of exponents must be $n$:

Also, $n_1, n_2, n_3$ must be non-negative integers.

Step 4: Find all possible combinations of $(n_1, n_2, n_3)$ that satisfy both conditions
We can systematically list possibilities for $n_3$ (since it has a multiplier of 2):

Case 1: $n_3 = 0$
From $n_2 + 2n_3 = 4 \Rightarrow n_2 + 0 = 4 \Rightarrow n_2 = 4$.
From $n_1 + n_2 + n_3 = 3 \Rightarrow n_1 + 4 + 0 = 3 \Rightarrow n_1 = -1$.
This is not a valid combination as $n_1$ must be non-negative.

Case 2: $n_3 = 1$
From $n_2 + 2n_3 = 4 \Rightarrow n_2 + 2(1) = 4 \Rightarrow n_2 = 2$.
From $n_1 + n_2 + n_3 = 3 \Rightarrow n_1 + 2 + 1 = 3 \Rightarrow n_1 = 0$.
This gives the valid combination $(n_1, n_2, n_3) = (0, 2, 1)$.

Case 3: $n_3 = 2$
From $n_2 + 2n_3 = 4 \Rightarrow n_2 + 2(2) = 4 \Rightarrow n_2 = 0$.
From $n_1 + n_2 + n_3 = 3 \Rightarrow n_1 + 0 + 2 = 3 \Rightarrow n_1 = 1$.
This gives the valid combination $(n_1, n_2, n_3) = (1, 0, 2)$.

Case 4: $n_3 \ge 3$
If $n_3=3$, then $n_2+2(3)=4 \Rightarrow n_2 = -2$, which is not valid. So no more cases.

The valid combinations are $(0, 2, 1)$ and $(1, 0, 2)$.

Step 5: Calculate the coefficient for each valid combination and sum them

For $(n_1, n_2, n_3) = (0, 2, 1)$:
Coefficient term is $\frac{3!}{0!2!1!} (2^{2}) = \frac{6}{1 \cdot 2 \cdot 1} \cdot 4 = 3 \cdot 4 = 12$.

For $(n_1, n_2, n_3) = (1, 0, 2)$:
Coefficient term is $\frac{3!}{1!0!2!} (2^{0}) = \frac{6}{1 \cdot 1 \cdot 2} \cdot 1 = 3 \cdot 1 = 3$.

Step 6: Sum the coefficients
Total coefficient of $x^4 = 12 + 3 = 15$.

Answer: $\boxed{15}$

---

4. Sums Involving Binomial Coefficients

Various identities involve sums of binomial coefficients. These are frequently tested for their direct application or as steps in proofs.

Identity 1: Sum of all Binomial Coefficients

Proof (Combinatorial Argument):
Consider a set with $n$ elements. The total number of subsets of this set is $2^n$ (each element can either be in a subset or not in a subset).
Alternatively, we can count the number of subsets by size:

• Number of subsets of size $0$ is $\binom{n}{0}$.


• Number of subsets of size $1$ is $\binom{n}{1}$.


• ...


• Number of subsets of size $n$ is $\binom{n}{n}$.

Summing these counts gives the total number of subsets:

Since both methods count the same quantity, we have $\sum_{k=0}^n \binom{n}{k} = 2^n$.

Proof (Using Binomial Theorem):
Set $x=1$ and $y=1$ in the Binomial Theorem $(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k$:

Identity 2: Alternating Sum of Binomial Coefficients

Proof (Using Binomial Theorem):
Set $x=1$ and $y=-1$ in the Binomial Theorem $(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k$:

For $n \ge 1$, $0^n = 0$. Thus, $\sum_{k=0}^n (-1)^k \binom{n}{k} = 0$.

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="What is the coefficient of $x^3y^4$ in the expansion of $(2x - y)^7$?" options=["-140","140","-280","280"] answer="280" hint="Use the general term formula for binomial expansion: $T_{k+1} = \binom{n}{k} x^{n-k} y^k$. Identify $n$, the first term, and the second term carefully." solution="Step 1: Identify $n$, $X$, and $Y$.
The expression is $(2x - y)^7$.
Here, $n=7$. The first term is $X = 2x$. The second term is $Y = -y$.

Step 2: Determine the value of $k$ for the desired term.
We are looking for the coefficient of $x^3y^4$.
In the general term $\binom{n}{k} X^{n-k} Y^k$, the power of $Y$ is $k$. So, $y^k$ means $k=4$.
The power of $X$ is $n-k = 7-4 = 3$. This means $(2x)^3$.
This matches the desired $x^3$ and $y^4$.

Step 3: Substitute these values into the general term formula.
The term is $\binom{7}{4} (2x)^{7-4} (-y)^4$.

Step 4: Calculate the binomial coefficient.

Step 5: Simplify the powers of the terms.

Step 6: Multiply all parts to find the complete term.

The coefficient of $x^3y^4$ is $280$.
Answer: $\boxed{280}$"
:::

:::question type="NAT" question="In the expansion of $(1 + x + x^2)^5$, what is the coefficient of $x^3$?" answer="30" hint="Use the Multinomial Theorem. Systematically find all combinations of exponents $(n_1, n_2, n_3)$ that sum to $5$ and result in $x^3$." solution="Step 1: Identify $n$ and the terms.
The expression is $(1 + x + x^2)^5$. Here $n=5$.
Let $y_1=1$, $y_2=x$, $y_3=x^2$.
A general term in the expansion is $\frac{5!}{n_1!n_2!n_3!} (y_1)^{n_1} (y_2)^{n_2} (y_3)^{n_3}$, where $n_1+n_2+n_3=5$.

Step 2: Substitute the terms and simplify for the power of $x$.
The general term is $\frac{5!}{n_1!n_2!n_3!} (1)^{n_1} (x)^{n_2} (x^2)^{n_3} = \frac{5!}{n_1!n_2!n_3!} x^{n_2+2n_3}$.

Step 3: Set up the system of equations.
We need the coefficient of $x^3$, so the power of $x$ must be $3$:

And the sum of exponents must be $5$:

All $n_i$ must be non-negative integers.

Step 4: Find all valid combinations of $(n_1, n_2, n_3)$.
Iterate through possible values for $n_3$ (since it has a multiplier):

Case 1: $n_3 = 0$
From $n_2 + 2n_3 = 3 \Rightarrow n_2 + 0 = 3 \Rightarrow n_2 = 3$.
From $n_1 + n_2 + n_3 = 5 \Rightarrow n_1 + 3 + 0 = 5 \Rightarrow n_1 = 2$.
Combination: $(n_1, n_2, n_3) = (2, 3, 0)$.

Case 2: $n_3 = 1$
From $n_2 + 2n_3 = 3 \Rightarrow n_2 + 2(1) = 3 \Rightarrow n_2 = 1$.
From $n_1 + n_2 + n_3 = 5 \Rightarrow n_1 + 1 + 1 = 5 \Rightarrow n_1 = 3$.
Combination: $(n_1, n_2, n_3) = (3, 1, 1)$.

Case 3: $n_3 = 2$
From $n_2 + 2n_3 = 3 \Rightarrow n_2 + 2(2) = 3 \Rightarrow n_2 = -1$.
This is not valid as $n_2$ must be non-negative. No further cases are possible for $n_3$.

The valid combinations are $(2, 3, 0)$ and $(3, 1, 1)$.

Step 5: Calculate the coefficient for each combination and sum them.

For $(n_1, n_2, n_3) = (2, 3, 0)$:
Coefficient term is $\frac{5!}{2!3!0!} = \frac{120}{2 \cdot 6 \cdot 1} = \frac{120}{12} = 10$.

For $(n_1, n_2, n_3) = (3, 1, 1)$:
Coefficient term is $\frac{5!}{3!1!1!} = \frac{120}{6 \cdot 1 \cdot 1} = \frac{120}{6} = 20$.

Step 6: Sum the coefficients.
Total coefficient of $x^3 = 10 + 20 = 30$.
Answer: $\boxed{30}$"
:::

:::question type="MCQ" question="Which of the following statements about binomial coefficients is/are true?" options=["$\binom{n}{k} = \binom{n}{n-k}$","$\binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{n} = 2^n$","$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$","All of the above"] answer="All of the above" hint="Recall the fundamental properties and identities of binomial coefficients." solution="Statements A, B, and C correspond to the fundamental properties of binomial coefficients discussed:
A. $\binom{n}{k} = \binom{n}{n-k}$ is the Symmetry Property. This is true.
B. $\binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{n} = 2^n$ is the Sum of All Binomial Coefficients Identity. This is true.
C. $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ is Pascal's Identity. This is true.
Since A, B, and C are all true, option D is the correct answer.
Answer: $\boxed{\text{All of the above}}$"
:::

:::question type="SUB" question="Prove the identity $\sum_{k=0}^n k \binom{n}{k} = n 2^{n-1}$ for $n \ge 1$ using the Binomial Theorem by differentiation." answer="n 2^{n-1}" hint="Consider the binomial expansion of $(1+x)^n$. Differentiate both sides with respect to $x$, then substitute a suitable value for $x$." solution="Step 1: Start with the Binomial Theorem expansion for $(1+x)^n$.

Step 2: Differentiate both sides with respect to $x$.
Differentiating the left side:

Differentiating the right side term by term:

Note that for $k=0$, the term $0 \cdot \binom{n}{0} x^{-1}$ is $0$, so the sum effectively starts from $k=1$.

Step 3: Equate the differentiated expressions.

Step 4: Substitute $x=1$ into the equation.

Step 5: Adjust the summation index.
Since the term for $k=0$ in $\sum_{k=0}^n k \binom{n}{k}$ is $0 \cdot \binom{n}{0} = 0$, the sum from $k=1$ is equivalent to the sum from $k=0$:

Step 6: Conclude the proof.
Therefore, we have proved the identity:

Answer: $\boxed{n 2^{n-1}}$"
:::

---

Summary

---

What's Next?

Here's the chapter conclusion for "Counting Techniques" for CMI preparation:

---

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="How many distinct permutations of the letters of the word 'MISSISSIPPI' have at least two 'S's adjacent?" options=["27300","34650","7350","20000"] answer="27300" hint="Consider the total permutations and subtract permutations where no two 'S's are adjacent. For 'no two adjacent', use the gap method." solution="Let the letters be M $(1)$, I $(4)$, S $(4)$, P $(2)$. Total letters = $11$.

Step 1: Calculate total distinct permutations.
The total number of distinct permutations of 'MISSISSIPPI' is given by the multinomial coefficient formula:

Step 2: Calculate permutations where no two 'S's are adjacent.
To ensure no two 'S's are adjacent, we first arrange the other letters (M, I, I, I, I, P, P) and then place the 'S's in the gaps created.
Number of other letters = $1+4+2 = 7$.
Permutations of these 7 letters:

These $7$ letters create $7+1=8$ possible gaps where the 'S's can be placed:
`_` L `_` L `_` L `_` L `_` L `_` L `_` L `_`
We need to choose $4$ of these $8$ gaps for the $4$ 'S's. Since the 'S's are identical, the order of choosing the gaps doesn't matter, and placing them in the chosen gaps is unique.
Number of ways to choose $4$ gaps from $8$:

So, the number of permutations where no two 'S's are adjacent is $105 \times 70 = 7350$.

Step 3: Calculate permutations where at least two 'S's are adjacent.
This is found by subtracting the "no two 'S's adjacent" case from the total permutations:

Answer: $\boxed{27300}$"
:::

:::question type="NAT" question="Find the number of non-negative integer solutions to the equation $x_1 + x_2 + x_3 = 10$ such that $x_1 \le 4$ and $x_2 \ge 2$." answer="35" hint="First, apply the lower bound constraint. Then, use complementary counting for the upper bound constraint." solution="We are looking for non-negative integer solutions to $x_1 + x_2 + x_3 = 10$ with conditions $x_1 \le 4$ and $x_2 \ge 2$.

Step 1: Apply the lower bound constraint.
Let $x_2' = x_2 - 2$. Since $x_2 \ge 2$, we have $x_2' \ge 0$.
Substitute $x_2 = x_2' + 2$ into the equation:
$x_1 + (x_2' + 2) + x_3 = 10$
$x_1 + x_2' + x_3 = 8$
Now we need to find non-negative integer solutions to this new equation, subject to $x_1 \le 4$.

Step 2: Find total non-negative solutions without the upper bound.
Using Stars and Bars for $x_1 + x_2' + x_3 = 8$ (where $x_1, x_2', x_3 \ge 0$):
Number of solutions = $\binom{n+k-1}{k-1} = \binom{8+3-1}{3-1} = \binom{10}{2} = \frac{10 \cdot 9}{2} = 45$.

Step 3: Apply the upper bound constraint using complementary counting.
We need $x_1 \le 4$. It's easier to count the solutions where $x_1 \ge 5$ and subtract them from the total.
Let $x_1' = x_1 - 5$. Since $x_1 \ge 5$, $x_1' \ge 0$.
Substitute $x_1 = x_1' + 5$ into $x_1 + x_2' + x_3 = 8$:
$(x_1' + 5) + x_2' + x_3 = 8$
$x_1' + x_2' + x_3 = 3$
Now, find the number of non-negative integer solutions to this equation:
Number of solutions = $\binom{3+3-1}{3-1} = \binom{5}{2} = \frac{5 \cdot 4}{2} = 10$.

Step 4: Subtract to find the desired solutions.
The number of solutions satisfying $x_1 \le 4$ and $x_2 \ge 2$ (and $x_3 \ge 0$) is:
Total solutions (from Step 2) - Solutions where $x_1 \ge 5$ (from Step 3)
$45 - 10 = 35$.
Answer: $\boxed{35}$"
:::

:::question type="MCQ" question="What is the value of the sum $\sum_{k=0}^{n} k \binom{n}{k}$?" options=["$2^n$","$n2^n$","$n2^{n-1}$","$(n+1)2^n$"] answer="$n2^{n-1}$" hint="Consider the Binomial Theorem and differentiation, or a combinatorial argument." solution="We need to evaluate the sum $S = \sum_{k=0}^{n} k \binom{n}{k}$.

Method 1: Using the Binomial Theorem and Differentiation
Recall the Binomial Theorem:

Differentiate both sides with respect to $x$:


Now, substitute $x=1$ into the equation:


So, the sum is $n2^{n-1}$.

Method 2: Combinatorial Argument
Consider a group of $n$ people. We want to form a committee of any size and select a leader for that committee.
* Approach 1: Choose the leader first. There are $n$ choices for the leader. Once the leader is chosen, the remaining $n-1$ people can either be in the committee or not. For each of the $n-1$ people, there are $2$ choices (in or out). So, there are $n \cdot 2^{n-1}$ ways to choose a leader and form a committee around them.
* Approach 2: Choose the committee first.
If the committee has $k$ members, there are $\binom{n}{k}$ ways to choose the $k$ members.
Once the $k$ members are chosen, there are $k$ ways to choose a leader from them.
So, for a committee of size $k$, there are $k \binom{n}{k}$ ways.
Summing over all possible committee sizes $k$ from $0$ to $n$:

Since both approaches count the same thing, they must be equal:

Answer: $\boxed{n2^{n-1}}$"
:::

:::question type="NAT" question="A group consists of $4$ married couples. How many ways are there to form a committee of $4$ people such that no two members of the committee are married to each other?" answer="16" hint="Since no two members can be married, each person selected must come from a different couple." solution="We have $4$ married couples, which means there are $4 \times 2 = 8$ people in total. Let the couples be $(H_1, W_1), (H_2, W_2), (H_3, W_3), (H_4, W_4)$.
We need to form a committee of $4$ people such that no two members are married to each other. This implies that if a husband is selected, his wife cannot be selected, and vice versa.

To satisfy the condition, each of the $4$ committee members must come from a different couple.
Step 1: Choose the $4$ couples from which the committee members will be drawn.
Since there are exactly $4$ couples, we must choose all $4$ couples. There is $\binom{4}{4} = 1$ way to do this.

Step 2: From each chosen couple, select one person.
For the first couple chosen, there are $2$ options (either the husband or the wife).
For the second couple chosen, there are $2$ options.
For the third couple chosen, there are $2$ options.
For the fourth couple chosen, there are $2$ options.
So, the number of ways to select one person from each of the $4$ chosen couples is $2 \times 2 \times 2 \times 2 = 2^4 = 16$.

Step 3: Total ways.
The total number of ways to form the committee is the product of the ways from Step 1 and Step 2:
$1 \times 16 = 16$.
Answer: $\boxed{16}$"
:::

---

What's Next?