PGDDSA Study · Semester 1

Core Titles

Key headlines and terms for quick recall

Factorial $n! = n(n-1)\cdots 1$
Permutation $^nP_r = \dfrac{n!}{(n-r)!}$ (order matters)
Combination $^nC_r = \binom{n}{r} = \dfrac{n!}{r!(n-r)!}$ (order doesn't)
Circular permutations of $n$ : $(n-1)!$
Permutations with repetition $\dfrac{n!}{n_1! n_2! \cdots n_k!}$
Binomial theorem
Pascal's identity $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$

Basic Idea

What it is, why it matters, how it works

Counting rule of thumb

Order matters → permutation
Order doesn't matter → combination

Permutations

Number of ways to arrange $r$ items chosen from $n$ distinct items: $^nP_r = \frac{n!}{(n-r)!}$ Special case: arranging all $n$ items uses $n!$ ways.

Circular arrangements of $n$ distinct objects: $(n-1)!$ — fix one object and arrange the rest.

Permutations with repetition — $n$ objects, where $n_i$ are of type $i$ : $\frac{n!}{n_1!\,n_2!\,\cdots\,n_k!}$ Example: arrangements of the letters in "BANANA" = $\dfrac{6!}{3!\,2!\,1!} = 60$ .

Combinations

Number of ways to choose $r$ items from $n$ : $^nC_r = \binom{n}{r} = \frac{n!}{r!(n-r)!}$

Key identities:

$\binom{n}{r} = \binom{n}{n-r}$
Pascal's rule: $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$
$\sum_{r=0}^{n} \binom{n}{r} = 2^n$

Binomial theorem

$(x+y)^n = \sum_{r=0}^{n} \binom{n}{r} x^{n-r} y^{r}$

Why this matters in Data Science

Sample-space sizes in probability, feature combinations in ML, $k$ -fold splits, model selection grids, A/B test arrangements.

Mind Map

Visual structure of the concept

COUNTING
├── Order MATTERS → Permutation
│   ├── ⁿPᵣ = n! / (n−r)!
│   ├── All n items: n!
│   ├── Circular: (n−1)!
│   └── With repetition: n! / Π nᵢ!
├── Order DOESN'T matter → Combination
│   ├── ⁿCᵣ = n! / r!(n−r)!
│   ├── ⁿCᵣ = ⁿCₙ₋ᵣ
│   ├── Pascal: ⁿCᵣ = ⁿ⁻¹Cᵣ₋₁ + ⁿ⁻¹Cᵣ
│   └── Sum: Σ ⁿCᵣ = 2ⁿ
└── Binomial theorem (x+y)ⁿ = Σ ⁿCᵣ xⁿ⁻ʳ yʳ

Exam Q&A

Part A (2 marks) and Part B (20 marks) style questions

Part A (2 marks each)

Q1. State the formula for $^nP_r$ and $^nC_r$ . $^nP_r = \dfrac{n!}{(n-r)!}$ and $^nC_r = \dfrac{n!}{r!(n-r)!}$ .

Q2. How many ways can 5 people be seated around a round table? Circular permutations: $(5-1)! = 24$ .

Q3. State Pascal's identity. $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$ .

Q4. How many arrangements of the letters in MISSISSIPPI? $\dfrac{11!}{4!\,4!\,2!\,1!} = 34650$ .

Part B (20 marks)

Q. State and prove the Binomial theorem. Use it to find the coefficient of $x^5 y^3$ in $(2x + 3y)^8$ .

Statement. For any non-negative integer $n$ : $(x+y)^n = \sum_{r=0}^{n} \binom{n}{r} x^{n-r} y^r$

Proof by induction on $n$ .

Base $n=0$ : LHS = 1, RHS = $\binom{0}{0} x^0 y^0 = 1$ . ✓

Step. Assume the theorem for $n=k$ : $(x+y)^k = \sum_{r=0}^{k}\binom{k}{r}x^{k-r}y^r$ .

Then $(x+y)^{k+1} = (x+y)\sum_{r=0}^{k}\binom{k}{r}x^{k-r}y^r = \sum_{r=0}^{k}\binom{k}{r}x^{k+1-r}y^r + \sum_{r=0}^{k}\binom{k}{r}x^{k-r}y^{r+1}.$

Shifting indices and using Pascal's identity $\binom{k}{r-1} + \binom{k}{r} = \binom{k+1}{r}$ : $(x+y)^{k+1} = \sum_{r=0}^{k+1}\binom{k+1}{r}x^{k+1-r}y^r. \quad \blacksquare$

Application — coefficient of $x^5 y^3$ in $(2x + 3y)^8$ .

General term: $\binom{8}{r}(2x)^{8-r}(3y)^{r}$ . For $x^5 y^3$ we need $r=3$ :

$\binom{8}{3}(2x)^5 (3y)^3 = 56 \cdot 32 x^5 \cdot 27 y^3 = 56 \cdot 32 \cdot 27 \; x^5 y^3 = 48384 \, x^5 y^3.$

Coefficient = 48384.

Permutations and Combinations