Combinations — nCr, Pascal's triangle

WHAT is a combination?

WHY do we need a separate idea from permutations? A permutation $^nP_r$ counts arrangements — it cares who is 1st, 2nd, 3rd. But if you just want a committee or a hand of cards, the internal order is meaningless. Combinations strip that away.

HOW to derive $\binom{n}{r}$ from scratch

We already know (from permutations) the number of ordered selections of $r$ from $n$ : $^nP_r = \underbrace{n(n-1)(n-2)\cdots(n-r+1)}_{r \text{ factors}} = \frac{n!}{(n-r)!}$

Key overcounting observation: every unordered group of $r$ items has been counted once for each of its own orderings. A group of $r$ items can be arranged in $r!$ ways.

So each combination was counted $r!$ times inside $^nP_r$ . To undo that, divide:

$\boxed{\ \binom{n}{r} = \frac{^nP_r}{r!} = \frac{n!}{r!\,(n-r)!}\ }$

Pascal's Triangle — WHY it works

Figure — Combinations — nCr, Pascal's triangle

Arrange the numbers $\binom{n}{r}$ in a triangle: row $n$ , position $r$ .

n=0:            1
n=1:          1   1
n=2:        1   2   1
n=3:      1   3   3   1
n=4:    1   4   6   4   1
n=5:  1   5  10  10   5   1

Derivation by a story (WHY it's true): Pick one special person, say Ravi, from the $n$ people. Every committee of size $r$ falls into exactly one of two cases:

Ravi is IN the committee: then we need $r-1$ more from the remaining $n-1$ ⇒ $\binom{n-1}{r-1}$ ways.
Ravi is OUT: we need all $r$ from the remaining $n-1$ ⇒ $\binom{n-1}{r}$ ways.

These cases don't overlap and cover everything, so we add them. That's Pascal's rule — no algebra needed, just clean case-splitting.

Worked example Prove Pascal's rule algebraically

Take $\binom{n-1}{r-1}+\binom{n-1}{r}$ and get common denominator $r!(n-r)!$ : $\frac{(n-1)!}{(r-1)!(n-r)!} + \frac{(n-1)!}{r!(n-1-r)!}$ Multiply first by $\tfrac{r}{r}$ , second by $\tfrac{n-r}{n-r}$ : $\frac{(n-1)!\,r + (n-1)!\,(n-r)}{r!(n-r)!} = \frac{(n-1)!\,[\,r+n-r\,]}{r!(n-r)!} = \frac{n\cdot(n-1)!}{r!(n-r)!} = \frac{n!}{r!(n-r)!} = \binom{n}{r}.$ Why this step? Forcing a common denominator lets the two $(n-1)!$ terms merge; the bracket collapsing to $n$ is the moment the magic happens.

Worked examples

Recall Feynman: explain to a 12-year-old

Imagine you have 5 different candies and can put 3 in your pocket. You don't care what order you grab them — a pocket with chocolate, mint, lemon is the same pocket however you grabbed them. So first count all the ordered grabs, then realize you counted each pocket $3\times2\times1=6$ times (all the orders of the same 3 candies), and divide by 6. That divide-by-the-shuffles is the whole trick! Pascal's triangle is just: to fill any box, add the two boxes leaning over it — because a new candy is either in your pocket or not.

Active recall

What does

\binom{n}{r}

count?

Number of ways to choose

r

items from

n

distinct items when order does NOT matter, no repetition.

Formula for

\binom{n}{r}

\dfrac{n!}{r!\,(n-r)!} = \dfrac{^nP_r}{r!}

Why divide

^nP_r

r!

Each unordered group of

r

items is counted

r!

times in the ordered count (once per internal arrangement); dividing removes that ordering.

Symmetry identity for combinations?

\binom{n}{r}=\binom{n}{n-r}

— choosing

r

to keep = choosing

n-r

to discard.

State Pascal's Rule.

\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}

Story-proof of Pascal's Rule?

Fix one special item: either it's chosen (

\binom{n-1}{r-1}

) or not (

\binom{n-1}{r}

); disjoint & exhaustive, so add.

Value of

\binom{n}{0}

1

(exactly one way to choose nothing; uses

0!=1

\binom{7}{3}=?

\dfrac{7\cdot6\cdot5}{6}=35

How to count "at least one" selections fast?

Total minus the complement ("none of that type"). e.g.

\binom{10}{4}-\binom{6}{4}

Which is bigger: use small or large

r

to compute?

Convert to smaller

r

via symmetry to minimize multiplications.

Connections

Permutations — nPr — combinations are permutations divided by $r!$ .
Factorials and 0! — the engine behind every formula here.
Binomial Theorem — $\binom{n}{r}$ are exactly the binomial coefficients in $(a+b)^n$ .
Probability — counting outcomes — combinations count equally-likely unordered outcomes.
Pascal's Triangle patterns — row sums $=2^n$ , hockey-stick, Fibonacci diagonals.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, combination ka matlab hai — group chunna jahan order matter nahi karta. Agar tum 7 doston me se 3 ka committee banate ho, to {Amit, Bina, Chetan} aur {Chetan, Amit, Bina} ek hi committee hai, kyunki inme koi "1st, 2nd" nahi hota. Isliye pehle hum ordered count nikalte hain ( $^nP_r$ ), phir har group ko $r!$ baar extra gina hai (uske andar ke saare arrangements), to $r!$ se divide kar dete hain. Bas yahi hai formula: $\binom{n}{r}=\frac{n!}{r!(n-r)!}$ .

Ek badiya shortcut hai symmetry: $\binom{n}{r}=\binom{n}{n-r}$ . Jab tum $r$ cheezein rakhne ke liye chunte ho, tab automatically baaki $n-r$ chhodne ke liye chun lete ho — do naam, ek hi count. Isliye $\binom{100}{98}$ likhne ki jagah $\binom{100}{2}=4950$ nikaalo, seconds me ho jayega. Yahi 80/20 trick hai — hamesha chhote $r$ pe convert karo.

Pascal's triangle ka jaadu bhi simple story hai. Kisi ek khaas bande (maan lo Ravi) ko fix karo. Committee me ya to Ravi hai — to baaki $r-1$ log $n-1$ me se aayenge — ya Ravi nahi hai — to poore $r$ log $n-1$ me se. Ye do cases alag-alag hain aur sab kuch cover karte hain, isliye add karo: $\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}$ . Triangle me har number apne upar wale do numbers ka sum hota hai — bas isi wajah se.

Sabse common galti: committee ke liye permutation use kar lena. Test simple hai — "do log aapas me swap karne se naya answer banta hai?" Committee me NAHI, isliye combination. Aur yaad rakho $\binom{n}{0}=1$ , kyunki "kuch na chunna" bhi ek tareeka hai (empty set), zero nahi.

Combinations — nCr, Pascal's triangle

WHAT is a combination?

HOW to derive $\binom{n}{r}$ from scratch

Pascal's Triangle — WHY it works

Worked examples

Active recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Statistics & Probability — Intermediate

Connections