Combinations — nCr, Pascal's triangle — Hinglish notes

2.7.11 · Maths › Statistics & Probability — Intermediate

Combination KYA hota hai?

Permutations se alag idea ki ZAROORAT kyun hai? Ek permutation $^{n} P_{r}$ arrangements count karta hai — use fark padta hai kaun 1st, 2nd, 3rd hai. Lekin agar tum sirf ek committee ya hand of cards chahte ho, toh internal order meaningless hai. Combinations woh hata dete hain.

$(r n)$ ko scratch se KAISE derive karein

Humein pehle se pata hai (permutations se) $n$ mein se $r$ ke ordered selections ki sankhya: $^{n} P_{r} = r factors n (n - 1) (n - 2) \dots (n - r + 1) = \frac{n !}{( n - r )!}$

Key overcounting observation: $r$ items ke har ek unordered group ko apni khud ki har ordering ke liye ek baar count kiya gaya hai. $r$ items ke ek group ko $r!$ tarike se arrange kiya ja sakta hai.

Toh har ek combination ko $^{n} P_{r}$ ke andar $r!$ baar count kiya gaya tha. Usse undo karne ke liye, divide karo:

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

Pascal's Triangle — YEH KYU kaam karta hai

Figure — Combinations — nCr, Pascal's triangle

$(r n)$ numbers ko ek triangle mein arrange karo: 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

Ek story se derivation (YEH sach kyun hai): $n$ logon mein se ek special person, maano Ravi, ko pick karo. $r$ size ki har committee exactly do cases mein se ek mein aati hai:

Ravi committee mein IN hai: toh remaining $n - 1$ mein se $r - 1$ aur chahiye ⇒ $(r - 1 n - 1)$ tarike.
Ravi OUT hai: remaining $n - 1$ mein se saare $r$ chahiye ⇒ $(r n - 1)$ tarike.

Yeh cases overlap nahi karte aur sab kuch cover karte hain, toh hum add karte hain. Yahi Pascal's rule hai — koi algebra nahi chahiye, bas clean case-splitting.

Worked examples

Recall Feynman: 12-year-old ko samjhao

Socho tumhare paas 5 alag-alag candies hain aur 3 apni pocket mein rakh sakte ho. Tumhe fark nahi karta tum unhe kis order mein uthate ho — chocolate, mint, lemon wali pocket wahi pocket hai chahe tum unhe kisi bhi tarike se uthao. Toh pehle saare ordered grabs count karo, phir realize karo ki tumne har pocket ko $3 \times 2 \times 1 = 6$ baar count kiya (same 3 candies ke saare orders), aur 6 se divide karo. Woh divide-by-the-shuffles hi poora trick hai! Pascal's triangle bas yeh hai: koi bhi box fill karne ke liye, uske upar jhuke hue do boxes ko add karo — kyunki ek naya candy ya toh tumhari pocket mein hai ya nahi.

Active recall

(r n)

kya count karta hai?

n

distinct items mein se

r

items choose karne ke tarike jab order matter NAHI karta, koi repetition nahi.

(r n)

ka formula?

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

^{n} P_{r}

r!

se kyun divide karte hain?

r

items ka har unordered group ordered count mein

r!

baar count hota hai (har internal arrangement ke liye ek baar); divide karne se woh ordering remove hoti hai.

Combinations ke liye symmetry identity?

(r n) = (n - r n)

—

r

rakhne ke liye choose karna =

n - r

discard karne ke liye choose karna.

Pascal's Rule state karo.

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

Pascal's Rule ka story-proof?

Ek special item fix karo: ya toh woh chosen hai (

(r - 1 n - 1)

) ya nahi (

(r n - 1)

); disjoint & exhaustive, toh add karo.

(0 n)

ki value?

1

(kuch bhi choose nahi karne ka exactly ek tarika;

0! = 1

use karta hai).

(3 7) = ?

\frac{7 \cdot 6 \cdot 5}{6} = 35

"At least one" selections fast count kaise karein?

Total minus complement ("us type ka koi nahi"). e.g.

(4 10) - (4 6)

Compute karne ke liye chhhota ya bada

r

use karein?

Multiplications kam karne ke liye symmetry ke zariye chhhote

r

mein convert karo.

Connections

Permutations — nPr — combinations permutations hain $r!$ se divide karke.
Factorials and 0! — yahan har formula ke peeche ka engine.
Binomial Theorem — $(r n)$ exactly $(a + b)^{n}$ mein binomial coefficients hain.
Probability — counting outcomes — combinations equally-likely unordered outcomes count karte hain.
Pascal's Triangle patterns — row sums $= 2^{n}$ , hockey-stick, Fibonacci diagonals.