1. Permutations and Combinations
Definition of Permutation
[!IMPORTANT]
A permutation is an arrangement of objects in a specific order.
The number of permutations of $n$ distinct objects taken $r$ at a time is the number of ordered arrangements possible.
The formal permutation formula is:
$$ \text{Number of permutations} = {}^nP_r = \frac{n!}{(n - r)!} $$
where $n! = n \times (n - 1) \dots 1$ and $0! = 1$.
Worked Example (Simple Permutation)
Q. Find the number of ways to arrange 4 people in a row out of 6.
Step 1: $n = 6,\ r = 4$
Step 2: Use the formula
$$ {}^6P_4 = \frac{6!}{(6-4)!} $$
$$ = \frac{6 \times 5 \times 4 \times 3 \times 2 \times 1}{2 \times 1} $$
$$ = \frac{720}{2} = 360 $$
[!TIP]
Always check: ORDER matters in permutation questions.
Permutations with Repetition Allowed
When objects can be repeated, the formula is:
$$ \text{Number of permutations with repetition} = n^r $$
where $n$ is number of objects to choose from, and $r$ is positions.
Worked Example (Permutation with Repetition)
Q. How many 3-letter codes can be made from letters A, B, C, D, E (repetition allowed)?
$n = 5$, $r = 3$
So,
$$ \text{Number of codes} = 5^3 = 125 $$
Circular Permutations
[!IMPORTANT]
Circular permutation is the arrangement of objects around a circle, where only the relative order matters (rotations are not counted as different).
- For $n$ distinct objects around a circle:
$$ \text{Number of circular permutations} = (n-1)! $$
- If the arrangement is a necklace/ring (mirror images considered same):
$$ \text{Number of distinct arrangements} = \frac{(n-1)!}{2} $$
This diagram shows 5 objects arranged in a circle. Rotating the arrangement does not make a new permutation.
Worked Example (Circular Permutation)
Q. In how many ways can 6 friends be seated around a circular table?
Step 1: Use $(n-1)!$
$$ \text{Number of seatings} = (6-1)! = 5! = 120 $$
[!TIP]
For circular tables, subtract 1 before taking factorial.
Definition of Combination
[!IMPORTANT]
A combination is a selection of objects where the order does NOT matter.
The formula is:
$$ \text{Number of combinations} = {}^nC_r = \frac{n!}{(r!\,(n-r)!)} $$
Worked Example (Combination)
Q. How many ways can a team of 3 be chosen from 8 people?
$n = 8,\ r = 3$
$$ {}^8C_3 = \frac{8!}{3! \ 5!} $$
$$ = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} $$
$$ = \frac{336}{6} = 56 $$
Combinations with Repetition
For combinations when objects can be chosen more than once:
$$ \text{Number of combinations with repetition} = {}^{n+r-1}C_r = \frac{(n + r -1)!}{r! \ (n-1)!} $$
Worked Example (Combination with Repetition)
Q. How many ways can you choose 4 candies from 3 types (with unlimited supply)?
$n=3$, $r=4$
$$ \text{Ways} = {}^{3+4-1}C_4 = {}^6C_4 = \frac{6!}{4! \ 2!} $$
$$ = \frac{720}{24 \times 2} = \frac{720}{48} = 15 $$
[!TIP]
For 'with repetition' always add $r-1$ to $n$ before using the $C$ formula.
Properties and Basic Identities of Permutations & Combinations
Key Permutation & Combination Identities
-
Symmetry in combinations: ${}^nC_r = {}^nC_{n-r}$
Proof:
From definition:
$$ {}^nC_r = \frac{n!}{r!(n - r)!} $$
Replace $r$ with $n - r$:
$$ {}^nC_{n - r} = \frac{n!}{(n - r)!r!} = {}^nC_r $$
$\boxed{{}^nC_r = {}^nC_{n-r}}$
- Addition Theorem:
$$ {}^nC_r + {}^nC_{r - 1} = {}^{n+1}C_r $$
Proof:
$$ {}^nC_r + {}^nC_{r - 1} = \frac{n!}{r!(n - r)!} + \frac{n!}{(r-1)!(n - r + 1)!} $$
Combine with common denominator, rearrange and simplify to show:
$$ = \frac{(n+1)!}{r!(n+1-r)!} = {}^{n+1}C_r $$
$\boxed{{}^nC_r + {}^nC_{r-1} = {}^{n+1}C_r}$
Comparison Table: Permutations vs Combinations
| Aspect | Permutation | Combination |
|---|---|---|
| Order | Matters | Does not matter |
| Formula | $\frac{n!}{(n - r)!}$ | $\frac{n!}{r!(n - r)!}$ |
| Notation | ${}^nP_r$ or $P(n, r)$ | ${}^nC_r$ or $C(n, r)$ |
| Examples | Arranging books, seating people | Forming teams, choosing cards |
| **With repetition (r objects) | $n^r$ | ${}^{n + r - 1}C_r$ |
Applications of Permutations and Combinations
Permutations and combinations solve problems in counting, probability, and arrangements.
Sample Numerical Problems
- How many 5-digit numbers can be made using digits 1–6, no digit repeated?
$n = 6, r = 5$
Order matters $\to$ permutation.
$$ \text{Ways} = 6P5 = \frac{6!}{(6-5)!} = \frac{720}{1} = 720 $$
- How many ways can a committee of 4 be chosen from 10 people?
$n = 10, r = 4$ (order doesn't matter)
$$ \text{Ways} = {}^{10}C_4 = \frac{10!}{4!6!} = \frac{5040}{24 \times 6} = 210 $$
2. Binomial Theorem and Multinomial Coefficients
Statement of Binomial Theorem
[!IMPORTANT]
Binomial Theorem:
For any integer $n \ge 0$, and any real numbers $a$ and $b$,
$$ > (a + b)^n = \sum_{r=0}^{n} {}^nC_r \, a^{n-r} b^r > $$
Derivation (Proof by Induction)
Base Case: $n = 1$
$$ (a + b)^1 = a + b = {}^1C_0 a^1 b^0 + {}^1C_1 a^0 b^1 $$
Inductive Step:
Assume true for $n = k$:
$$ (a + b)^k = \sum_{r=0}^{k} {}^kC_r a^{k-r} b^r $$
For $n = k+1$:
$$ (a + b)^{k+1} = (a + b) \cdot (a + b)^k = (a + b) \left[\sum_{r=0}^{k} {}^kC_r a^{k-r} b^r\right] $$
Expanding,
$$ = \sum_{r=0}^{k} {}^kC_r a^{k+1-r} b^r + \sum_{r=0}^{k} {}^kC_r a^{k-r} b^{r+1} $$
Adjust indices and combine like powers using the Pascal rule:
$$ {}^{k+1}C_r = {}^kC_r + {}^kC_{r-1} $$
Thus, Binomial Theorem is proved by induction.
General Term (rth Term) in Binomial Expansion
[!IMPORTANT]
The general (rth) term in $(a + b)^n$ is:
$$ > T_{r+1} = {}^nC_r \, a^{n - r} b^r,\quad 0 \leq r \leq n > $$
Derivation
Each term corresponds to choosing $r$ times $b$ and $n - r$ times $a$. The coefficient is the number of such ways:
$$ T_{r+1} = \text{coefficient}\times a \text{ power } b \text{ power} = {}^nC_r\, a^{n-r}\, b^r $$
[!TIP]
r = 0 gives the first term.
r = n gives the last term.
Example (General Term)
Find the 4th term in expansion of $(2x + 3)^5$:
Use $T_{4} = {}^5C_{3} (2x)^{5-3} (3)^3$
Compute:
-
${}^5C_3 = 10$
-
$(2x)^2 = 4x^2$
-
$3^3 = 27$
So,
$$ T_4 = 10 \times 4x^2 \times 27 = 10 \times 108 x^2 = 1080 x^2 $$
Properties of Binomial Coefficients
- Symmetry:
$$ {}^nC_r = {}^nC_{n - r} $$
- Sum of all coefficients:
$$ \sum_{r=0}^n {}^nC_r = 2^n $$
Proof (by substituting $a=1$, $b=1$ in Binomial Theorem):
$$ (1 + 1)^n = \sum_{r=0}^{n} {}^nC_r 1^{n - r} 1^{r} = 2^n $$
$\boxed{\sum_{r=0}^n {}^nC_r = 2^n}$
- Pascal’s Rule:
$$ {}^nC_r + {}^nC_{r - 1} = {}^{n+1}C_r $$
(See proof in section 1.)
Comparison Table: Properties of Binomial Coefficients
| Property | Statement |
|---|---|
| Symmetry | ${}^nC_r = {}^nC_{n - r}$ |
| Pascal's Rule | ${}^nC_r + {}^nC_{r-1} = {}^{n+1}C_r$ |
| Sum of All Coefficients | $\sum_{r=0}^n {}^nC_r = 2^n$ |
Simple Problems Using Binomial Theorem
Q. Find the expansion of $(x + 2)^3$ using Binomial Theorem.
$$ (x + 2)^3 = {}^3C_0 x^3 2^0 + {}^3C_1 x^2 2^1 + {}^3C_2 x^1 2^2 + {}^3C_3 x^0 2^3 $$
$$ = 1 \cdot x^3 + 3 \cdot x^2 \cdot 2 + 3 \cdot x \cdot 4 + 1 \cdot 8 $$
$$ = x^3 + 6x^2 + 12x + 8 $$
Multinomial Theorem
[!IMPORTANT]
Multinomial Theorem:
For $(x_1 + x_2 + \dots + x_m)^n$,
$$ > (x_1 + x_2 + \dots + x_m)^n = \sum \frac{n!}{k_1! k_2! \dots k_m!} \, x_1^{k_1}\, x_2^{k_2} \cdots x_m^{k_m} > $$
where the sum is over all non-negative integers $k_1, k_2, ..., k_m$ such that $k_1 + k_2 + \dots + k_m = n$.
Definition of Multinomial Coefficient
[!IMPORTANT]
The multinomial coefficient for the term $x_1^{k_1} x_2^{k_2} \dots x_m^{k_m}$ in the expansion is:
$$ > \boxed{ > \frac{n!}{k_1! k_2! \dots k_m!} > } > $$
- It counts the number of ways to assign in total $n$ factors, with $k_i$ allocated to $x_i$, for $i = 1,2,\dots, m$.
Derivation of Multinomial Formula
Each term in the expansion corresponds to choosing $k_1$ $x_1$’s, $k_2$ $x_2$'s, ..., $k_m$ $x_m$'s out of $n$ total, so the total arrangements:
$$ \text{Ways} = \frac{n!}{k_1! k_2! \dots k_m!} $$
where $k_1 + k_2 + \cdots + k_m = n$.
Applications of Multinomial Coefficients
Used when objects are of more than two types.
Sample Numerical Problem
Q. How many terms are there in the expansion of $(x + y + z)^4$? Find the coefficient of $x^2 y z$
Number of terms:
Set $k_1 + k_2 + k_3 = 4$, $k_i\geq 0$, the number of integer solutions is:
$$ = {}^{4+3-1}C_{3-1} = {}^6C_2 = 15 $$
Coefficient of $x^2 y z$:
$k_1=2$, $k_2=1$, $k_3=1$, $n=4$
$$ \text{Coefficient} = \frac{4!}{2!1!1!} = \frac{24}{2 \times 1 \times 1} = 12 $$
[!TIP]
- For multinomial expansions, the sum of the powers in each term equals $n$.
- For exam numericals, always write the general multinomial term and substitute powers.
End of Unit 7 (Combinatorics) — Exam-Ready Short Notes