Combinations — nCr, Pascal's triangle: Visual walkthrough

2.7.11 · D2 · Maths › Statistics & Probability — Intermediate › Combinations — nCr, Pascal's triangle

Yeh parent topic hai, poora pictures ke through dekha gaya. Agar factorial ya permutation jaisa koi word naya hai, toh hum ise yahan build karte hain — kuch bhi assume nahi kiya gaya hai.

Step 1 — "Choosing" ka matlab kya hai (order vs no-order)

KYA HAI. Hamare paas $n$ distinct objects hain. Distinct matlab alag-alag pehchaane ja sakne wale — teen alag candies, paanch alag log. Hum unme se $r$ ka ek chota sa pile pick karna chahte hain. Is page ka poora sawaal yeh hai: kitne alag-alag piles possible hain?

ORDER ki tension kyun. Yahan do alag sawaal chhupe hue hain:

Ordered: "kaun 1st hai, kaun 2nd, kaun 3rd?" — ek line-up.
Unordered: "kaun sirf pile mein HAI?" — pile ka koi aage-peeche nahi hota.

Ek combination unordered sawaal ka jawaab deta hai. Jis symbol ko hum dhundh rahe hain woh hai

$(r n)$

jo zor se padha jata hai " $n$ choose $r$ ". Yahan $n$ (upar ka number) hai humein jitne mein se pick karna hai, aur $r$ (neeche ka number) hai hum kitne lete hain. Abhi sirf itna hi matlab hai — ek count.

PICTURE. Figure dekho: wohi teen candies right side pe ek pile banati hain, lekin left side pe six line-ups. Combinations sirf ek pile count karti hai; chheh line-ups wohi hain jinhe hume divide karna seekhna hai.

Figure — Combinations — nCr, Pascal's triangle

Step 2 — Pehle ORDERED picks count karo (yahi $^{n} P_{r}$ hai)

KYA HAI. Order ko un-count karne se pehle, hum order ke saath count karte hain. Socho $r$ khaali slots bhar rahe ho, left se right, objects uthake.

Order se kyun shuru karein. Ordered picking aasaan hai — yeh bas ek chain of multiplications hai, har slot ke liye ek factor. Is ordered count ko permutation kehte hain, likha jaata hai $^{n} P_{r}$ (dekho Permutations — nPr).

PICTURE. Figure mein $r$ slots fill hote dikhaaye gaye hain:

$^{n} P_{r} = slot 1: any of n n \times slot 2: one used up (n - 1) \times slot 3 (n - 2) \times \dots \times slot r (n - r + 1)$

Term by term: pehle slot mein $n$ choices hain; ek object place hone ke baad woh chala jaata hai, toh doosre slot mein $n - 1$ hain; aur aage bhi aise hi. $r$ slots fill karne ke baad humne $r$ objects use kar liye, isliye last factor $n - r + 1$ hai ( $n$ se shuru karke $r$ steps neeche).

Step 3 — Overcounting ko pakdo

KYA HAI. Ek fixed pile lo, maano ${A, B, C}$ . Hamare kitne ordered line-ups ne isi pile ko produce kiya?

Yeh kyun sabse zaroori baat hai. Har unordered pile ko utni baar count kiya gaya jitni tarah uske apne members line up ho sakte hain. Toh $^{n} P_{r}$ pile-count nahi hai — yeh pile-count zyada hai internal orderings ki sankhya ke barabar.

PICTURE. Figure mein pile ${A, B, C}$ centre mein hai aur uske chhe line-ups bahar ki taraf fan karke hain: $A B C, A C B, B A C, B C A, C A B, C B A$ . Chhe spokes, ek hub. Har hub (pile) ke utne hi spokes hote hain.

Kitne spokes? $r$ chosen objects ko apne andar line up karne ke tarike — woh hai $^{r} P_{r} = r!$ .

Step 4 — Order divide karo: master formula

KYA HAI. Agar har pile $^{n} P_{r}$ ke andar exactly $r!$ baar count hui thi, toh sahi pile-count wapas paane ke liye hum bas $r!$ se divide kar dete hain.

Division kyun, subtraction kyun nahi. Overcount multiplicative hai: total ordered $=$ (piles) $\times$ ( $r!$ ). Multiplication ko undo karna division hai. Subtraction sirf ek fixed amount hatata, har-pile ka factor nahi.

PICTURE. Figure mein hub-and-spoke cloud collapse hoti dikhayi gayi hai: bahut saare spokes ek dot mein simat jaate hain — $r!$ line-ups ko "un-shuffle" karke wapas ek pile banate hain.

$(r n) = \frac{^{n} P _{r}}{r !} = \frac{1}{r !} \cdot \frac{n !}{( n - r )!} = \frac{n !}{r ! ( n - r )!}$

Term by term:

$n!$ — sab kuch jo hum arrange kar sakte the,
$(n - r)!$ — un objects ki tail jo nahi pick ki gayi, divide out isliye ki humne unhe kabhi choose nahi kiya,
$r!$ — pile ki internal orderings, divide out isliye ki humein order ki parwah nahi.

Step 5 — Degenerate cases (inhe kabhi skip mat karo)

KYA HAI. Machine ko uske edges pe test karo: $r = 0$ , $r = n$ , aur $r = 1$ .

KYUN. Jis formula pe tumhara bharosa ho, woh extremes pe bhi sane answers deni chahiye. Agar wahan toot jaaye, toh galat hai.

PICTURE. Figure mein teen chote scenes hain: ek khali pile, ek "sab lo" pile, aur ek single-object pile.

$r = 0$ (kuch mat chuno): $(0 n) = \frac{n !}{0 ! n !} = \frac{n !}{1 \cdot n !} = 1$ . Exactly ek khaali pile hoti hai. Iske liye $0! = 1$ zaroori hai — yahi wajah hai ki woh convention exist karta hai (dekho Factorials and 0!).
$r = n$ (sab chuno): $(n n) = \frac{n !}{n ! 0 !} = 1$ . Exactly ek tarika sab lene ka.
$r = 1$ : $(1 n) = \frac{n !}{1 ! ( n - 1 )!} = n$ . Ek object pick karna $=$ $n$ choices. Obvious — acha, formula manta hai.

Step 6 — Hidden symmetry $(r n) = (n - r n)$

KYA HAI. Yeh choose karna ki kaun se $r$ rakhne hain, same kaam hai jaise choose karna ki kaun se $n - r$ chhod dene hain. Ek decision, do naam.

Yeh kyun hold karna chahiye. Formula dekho: $r$ aur $n - r$ swap karne se donon denominators $r!$ aur $(n - r)!$ swap ho jaate hain — lekin multiplication ko order ki parwah nahi hoti, toh value same rehti hai.

$(r n) = \frac{n !}{r ! ( n - r )!} = \frac{n !}{( n - r )! r !} = (n - r n)$

PICTURE. Figure mein $n$ objects ko ek dividing line se split kiya gaya hai: left side sab "rakha gaya" ( $r$ ), right side sab "phenka gaya" ( $n - r$ ). Line slide karo toh ek side doosri ka mirror ban jaati hai.

Step 7 — Answers stack karo: Pascal's Triangle

KYA HAI. $(r n)$ ko ek grid mein rakho — row $n$ , position $r$ — aur numbers ka ek triangle appear hota hai.

Yeh khud kyun build hota hai. Ek special object fix karo (ise Ravi kaho). Size $r$ ki koi bhi pile ya toh Ravi ko contain karti hai ya nahi — do non-overlapping, sab-cover cases:

Ravi IN hai: baaki $r - 1$ bache hue $n - 1$ mein se choose karo → $(r - 1 n - 1)$ .
Ravi OUT hai: saare $r$ bache hue $n - 1$ mein se choose karo → $(r n - 1)$ .

Disjoint cases add karo:

$(r n) = (r - 1 n - 1) + (r n - 1)$

Toh har entry seedha uske upar wale do numbers ka sum hai. Isliye triangle simple addition se grow karta hai — ek baar top rows exist ho jaayein toh koi formula nahi chahiye (dekho Pascal's Triangle patterns aur Binomial Theorem).

PICTURE. Figure mein triangle dikhaya gaya hai jisme do parents $(r - 1 n - 1)$ aur $(r n - 1)$ apne child $(r n)$ mein flow kar rahe hain, aur saath mein Ravi-in / Ravi-out split bhi hai.

Ek-picture summary

KYA HAI. Ek figure poora safar compress karta hai: ordered picks ( $^{n} P_{r}$ ) → har pile ke $r!$ line-ups collapse karo → divide karo → $(r n)$ → Pascal's Triangle mein stack karo.

Recall Feynman retelling (simple words mein)

Maano tum $5$ alag candies mein se $3$ pocket kar sakte ho. Pehle pretend karo order matter karta hai aur unhe ek line mein pakdo: $5 \times 4 \times 3 = 60$ line-ups. Lekin pocket ko order ki parwah nahi — wohi $3$ candies $3 \times 2 \times 1 = 6$ tarike se line up ho sakti hain, aur saatho $6$ usi pocket ko describe karte hain. Toh maine $6$ se zyada count kar liya. Divide karo: $60/6 = 10$ pockets. Yeh "shuffles-se-divide-karna" hi combination formula hai. Agar main $0$ candies pocket karun toh exactly $1$ tarika hai (khaali pocket) — isliye $0! = 1$ hota hai. Aur Pascal's triangle bas yahi hai: koi bhi box fill karne ke liye, ek special candy pick karo; ya toh woh pocket mein hai ya nahi, toh box ke upar jhuke donon boxes add kar do. Order-strip, phir case-split — poora subject do moves mein.

Divide, subtract nahi — kyun?

Overcount multiplicative hai: ordered

=

piles

\times r!

. Multiplication undo karna matlab division hai.

Formula mein

(n - r)!

ka role?

Yeh un objects ki tail cancel karta hai jo kabhi choose nahi ki gayi, sirf

^{n} P_{r}

r

falling factors bachte hain.

(2 6) = ?

\frac{6 \cdot 5}{2} = 15

Connections

Permutations — nPr — Step 2 hi $^{n} P_{r}$ hai; combinations bas uska order strip karti hain.
Factorials and 0! — Step 5 ko $(0 n) = 1$ banane ke liye $0! = 1$ chahiye.
Binomial Theorem — yeh triangle entries $(a + b)^{n}$ ke coefficients hain.
Pascal's Triangle patterns — Step 7 ka addition law har pattern generate karta hai.
Probability — counting outcomes — piles equally-likely unordered outcomes hote hain.