Combinations — nCr, Pascal's triangle: Exercises

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

Shuru karne se pehle, un do main tools ko yaad karo jinka hum poore time use karenge. Ek combination $(r n)$ count karta hai ki $n$ cheezon mein se $r$ cheezein kitne tareekon se choose ki ja sakti hain jab order matter nahi karta. Iska formula hai:

Level 1 — Recognition

Yahan goal sirf yeh decide karna hai ki kaunsa idea lagta hai aur value read karni hai, heavy arithmetic nahi karni.

L1.1

Batao ki har situation ek combination hai (order irrelevant) ya permutation (order matters): (a) 8 mein se pizza ke liye 3 toppings choose karna; (b) 8 runners mein se 3 ko gold, silver, bronze dena; (c) 5-card poker hand deal karna.

Recall Solution

WHAT hum har baar poochhte hain: "kya do chosen items ko swap karne se outcome badal jaata hai?" (a) Pizza pe toppings — mushroom-then-onion wahi pizza hai jaisi onion-then-mushroom ⇒ order irrelevant ⇒ combination, $(3 8)$ . (b) Gold/silver/bronze alag-alag prizes hain — do runners ko swap karne se baadal jaata hai ki kisne gold jeeta ⇒ order matters ⇒ permutation, $^{8} P_{3}$ . (Dekho Permutations — nPr.) (c) Ek poker hand cards ka set hota hai; unhe haath mein rearrange karna same hand hai ⇒ combination, $(5 52)$ .

L1.2

Inhe seedha definition se read karo (lamba multiplication nahi): $(0 6)$ , $(6 6)$ , $(1 6)$ , $(8 9)$ .

Recall Solution

$(0 6) = 1$ : kuch bhi choose na karne ka exactly ek tarika hai (empty set). $0! = 1$ use karta hai.
$(6 6) = 1$ : sabko choose karne ka exactly ek tarika hai.
$(1 6) = 6$ : chhe mein se ek item choose karna — chhe choices.
$(8 9) = (1 9) = 9$ symmetry se (8 ko rakhne ke liye choose karna = 1 ko hatane ke liye choose karna).

L1.3

Pascal's triangle ki row $n = 5$ mein, kaunsi entry $(2 5)$ hai, aur yeh kya hai? Neeche di gayi picture use karo.

Figure — Combinations — nCr, Pascal's triangle

Recall Solution

Rows upar se $n = 0, 1, 2, \dots$ se number hoti hain; positions baayein se $r = 0, 1, 2, \dots$ se. Toh $(2 5)$ row 5, position 2 hai, highlighted coral cell. Iska value $10$ hai. Check karo: $(2 5) = \frac{5 \cdot 4}{2 \cdot 1} = 10$ . ✓

Level 2 — Application

Ab plug in karo aur compute karo, falling-factor shortcut use karke: sirf $^{n} P_{r}$ ke top ke $r$ falling factors likho aur $r!$ se divide karo. Kabhi bhi poora factorial expand mat karo.

L2.1

$(4 9)$ compute karo.

Recall Solution

WHAT: upar $r = 4$ falling factors lo, $4!$ se divide karo. $(4 9) = \frac{9 \cdot 8 \cdot 7 \cdot 6}{4 !} = \frac{3024}{24} = 126.$ WHY shortcut: $(4 9) = \frac{9 !}{4 ! 5 !}$ , aur $5!$ upar se $9!$ ki tail $5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$ ko cancel kar deta hai, sirf $9 \cdot 8 \cdot 7 \cdot 6$ upar bachta hai.

L2.2

12 logon mein se 4 ka committee choose kiya jaata hai. Kitne committees possible hain?

Recall Solution

Committee mein order irrelevant hai ⇒ combination. $(4 12) = \frac{12 \cdot 11 \cdot 10 \cdot 9}{24} = \frac{11880}{24} = 495.$

L2.3

$(47 50)$ smart tarike se compute karo.

Recall Solution

$47$ bada hai; symmetry se chote $r$ mein convert karo: $(47 50) = (3 50)$ . $(3 50) = \frac{50 \cdot 49 \cdot 48}{6} = \frac{117600}{6} = 19600.$ WHY: 47 ko rakhne ke liye choose karna wahi decision hai jaisi 3 ko discard karne ke liye choose karna, aur 3 factors 47 factors se behtar hain.

Level 3 — Analysis

Inhe case-split ya complement ki zaroorat hai. Compute karne se pehle structure decide karo.

L3.1

6 men aur 5 women mein se exactly 2 men wala 4 ka committee banao.

Recall Solution

WHAT: committee do independent stages mein banti hai — pehle men pick karo, phir women.

6 mein se 2 men choose karo: $(2 6) = \frac{6 \cdot 5}{2} = 15$ .
Baaki 2 members (women) 5 mein se choose karo: $(2 5) = \frac{5 \cdot 4}{2} = 10$ . WHY multiply: men ki har choice, women ki har choice ke saath independently pair ho sakti hai ⇒ multiply karo. $15 \times 10 = 150.$

L3.2

Ek standard deck mein se, kitne 5-card hands mein kam se kam ek ace hota hai? (4 aces hain, 48 non-aces hain.)

Recall Solution

WHY complement use karein: "kam se kam ek ace" 1, 2, 3, ya 4 aces mein split hota hai — chaar cases. Ulta, "koi ace nahi," ek single count hai. Ise total mein se subtract karo.

Total hands: $(5 52) = 2598960$ .
No-ace hands (48 non-aces mein se saare 5): $(5 48) = \frac{48 \cdot 47 \cdot 46 \cdot 45 \cdot 44}{120} = 1712304$ . $Kam se kam ek ace = 2598960 - 1712304 = 886 656.$

L3.3

10 logon mein se 4-person groups mein se kitne mein Amit aur Bina dono shamil hain?

Recall Solution

WHAT: Amit aur Bina ko force in karo, phir baki bharo. Agar dono already chosen hain, toh baaki $10 - 2 = 8$ logon mein se $4 - 2 = 2$ aur chahiye. $(2 8) = \frac{8 \cdot 7}{2} = 28.$

Level 4 — Synthesis

Kai tools combine karo: complements, case-splits, aur Pascal / binomial identities.

L4.1

7 boys aur 4 girls mein se kam se kam 2 girls ke saath 5 ka team choose kiya jaata hai. Kitne tarike hain?

Recall Solution

WHY case-split (complement nahi): sirf 4 girls ke saath "kam se kam 2 girls" ka matlab girls $= 2, 3, 4$ — teen saaf cases, aur complement ("0 ya 1 girl") bhi do cases hain, toh dono tarike theek hain. Girl-count se split karo:

2 girls, 3 boys: $(2 4) (3 7) = 6 \times 35 = 210$ .
3 girls, 2 boys: $(3 4) (2 7) = 4 \times 21 = 84$ .
4 girls, 1 boy: $(4 4) (1 7) = 1 \times 7 = 7$ . Yeh disjoint aur exhaustive hain ⇒ add karo: $210 + 84 + 7 = 301.$

L4.2

Row-sum identity $\sum_{r = 0}^{n} (r n) = 2^{n}$ use karke, 6-element set ke non-empty subsets ki number nikalte hain.

Recall Solution

WHY $2^{n}$ : har element independently subset mein ya toh IN hai ya OUT — 2 choices each, $n$ elements ⇒ $2^{n}$ total subsets. Yeh saare $(r n)$ ke sum ke barabar hai kyunki hum subsets ko size $r$ ke hisaab se bhi count kar sakte hain aur $r$ pe add kar sakte hain. (Dekho Pascal's Triangle patterns.) Total subsets: $2^{6} = 64$ . Ek empty subset hata do: $64 - 1 = 63.$

L4.3

$(3 6)$ ke liye numerically Pascal's rule verify karo: dikhao ki $(3 6) = (2 5) + (3 5)$ .

Recall Solution

$(3 6) = \frac{6 \cdot 5 \cdot 4}{6} = 20.$ Right-hand side: $(2 5) = 10$ aur $(3 5) = (2 5) = 10$ , toh $10 + 10 = 20$ . ✓ WHY kaam karta hai (story): ek person, maan lo Ravi, fix karo. 6 mein se 3 ke committees mein ya toh Ravi hota hai (phir doosre 5 mein se 2 aur ⇒ $(2 5)$ ) ya nahi hota (doosre 5 mein se 3 ⇒ $(3 5)$ ). Disjoint aur exhaustive ⇒ add karo.

Level 5 — Mastery

Identities ko khud prove karo aur unse reason karo.

L5.1

Symmetry $(r n) = (n - r n)$ ko formula se prove karo, aur counting mein ek sentence mein explain karo.

Recall Solution

Algebra: formula mein $r$ ki jagah $n - r$ rakho: $(n - r n) = \frac{n !}{( n - r )! ( n - ( n - r ) ) !} = \frac{n !}{( n - r )! r !} = (r n) .$ Denominator mein wahi do factorials hain bas swap hue, toh values equal hain. Counting sentence: $r$ items rakhne ke liye choose karna wahi decision hai jaisi $n - r$ items chhod dene ke liye choose karna — ek action, do naam.

L5.2

Ek chote case ke liye hockey-stick identity prove karo: $(2 2) + (2 3) + (2 4) + (2 5) = (3 6) .$ Numerically confirm karo aur Pascal's rule se explain karo.

Recall Solution

Numeric check: $1 + 3 + 6 + 10 = 20 = (3 6)$ . ✓ WHY (Pascal ke saath telescoping): Pascal's rule kehta hai $(3 k) = (2 k - 1) + (3 k - 1)$ , yaani $(2 k - 1) = (3 k) - (3 k - 1)$ . $k = 3, 4, 5, 6$ ke liye sum karne se $(3 k - 1)$ terms ek chain mein cancel ho jaate hain (telescope), aur $(3 6) - (3 2) = (3 6) - 0 = (3 6)$ bachta hai. Geometrically yeh "hockey stick" hai: triangle mein entries ki ek diagonal run, uske end ke neeche-aur-baayein wali entry tak sum hoti hai.

L5.3

Dikhao ki $r = 0 \sum n (r n) = 2^{n}$ Binomial Theorem use karke, aur $n = 4$ ke liye check karo.

Recall Solution

Binomial Theorem kehta hai $(a + b)^{n} = \sum_{r = 0}^{n} (r n) a^{n - r} b^{r}$ . WHY $a = b = 1$ set karein: isse har power 1 ke barabar ho jaati hai, toh har term sirf uska coefficient $(r n)$ hota hai, aur left side $2^{n}$ ban jaata hai. Isliye $2^{n} = (1 + 1)^{n} = \sum_{r = 0}^{n} (r n) .$ Check $n = 4$ : $1 + 4 + 6 + 4 + 1 = 16 = 2^{4}$ . ✓ (Yeh wahi row-sum hai jo L4.2 mein use hua — dekho Probability — counting outcomes kyunki $2^{n}$ saare yes/no outcomes count karta hai.)

Recall Final self-check (saare answers)

L2.1 $126$ · L2.2 $495$ · L2.3 $19600$ · L3.1 $150$ · L3.2 $886656$ · L3.3 $28$ · L4.1 $301$ · L4.2 $63$ · L4.3 $20 = 10 + 10$ · L5.2 $20$ · L5.3 $16$ .

Connections

Permutations — nPr — L1 ordered vs unordered counts ko distinguish karta hai.
Factorials and 0! — har shortcut aur $(0 n) = 1$ edge case ko power deta hai.
Binomial Theorem — L5.3 row sums $2^{n}$ ke liye ise use karta hai.
Probability — counting outcomes — subset counts probabilities ko feed karte hain.
Pascal's Triangle patterns — L1.3, L4.2, L5.2 rows, row-sums, hockey-stick use karte hain.