Pascal's triangle — combinatorial interpretation

3.3.12 · Maths › Sequences & Series

Pascal's triangle KYA hai?

Row 0:            1
Row 1:          1   1
Row 2:        1   2   1
Row 3:      1   3   3   1
Row 4:    1   4   6   4   1
Row 5:  1   5   10  10  5   1

Row 4, position 2 hai $6 = (2 4)$ : 4 mein se 2 items choose karne ke 6 tareeqe hain.

$(k n) = \frac{n !}{k ! ( n - k )!}$ KYU? (Scratch se derive karo)

Step 1 — ordered selections count karo. 1st item choose karo: $n$ tareeqe. 2nd: $n - 1$ tareeqe. ... $k$ -th: $n - k + 1$ tareeqe. $ordered = n (n - 1) \dots (n - k + 1) = \frac{n !}{( n - k )!}$ Yeh step kyun? Har pick ek option hata deta hai, isliye counts har baar 1 se girte hain.

Step 2 — ordering hatao. $k$ items ka koi bhi fixed set $k!$ alag-alag orders mein arrange ho sakta hai, jinhe humne alag-alag count kiya tha. $(k n) = \frac{ordered}{k !} = \frac{n !}{k ! ( n - k )!}$ Yeh step kyun? Humein sets chahiye the, sequences nahi; size $k$ ka ek set $k!$ baar count hua tha.

HAR entry upar wali do entries ka sum KYU hoti hai? (Pascal's rule)

Combinatorial proof (sachcha tareeqa). ${1, 2, \dots, n}$ mein se size $k$ ke subsets count karo. Element $n$ pe focus karo:

Subsets jo $n$ contain karte hain: baaki $k - 1$ members remaining $n - 1$ elements mein se aate hain → $(k - 1 n - 1)$ tareeqe.
Subsets jo $n$ contain nahi karte: saare $k$ members remaining $n - 1$ elements mein se aate hain → $(k n - 1)$ tareeqe.

Yeh do cases mutually exclusive hain aur har subset cover karte hain, isliye inhe add karo (Addition Principle): $(k n) = (k - 1 n - 1) + (k n - 1)$

Yeh kyun kaam karta hai: har possible selection ya toh $n$ use karta hai ya nahi karta — koi overlap nahi, koi gap nahi.

Figure — Pascal's triangle — combinatorial interpretation

HAR row ka sum $2^{n}$ KYU hota hai?

Combinatorial proof. Left side har size $k = 0, 1, \dots, n$ ke subsets count karta hai — yaani ek $n$ -element set ke saare subsets. Lekin hum saare subsets seedha bhi count kar sakte hain: $n$ elements mein se har ek ke liye decide karo andar ya bahar (2 choices), jo deta hai $2^{n}$ . Ek hi cheez ke do counts barabar honge.

Algebraic cross-check. Binomial Theorem $(x + y)^{n} = \sum (k n) x^{n - k} y^{k}$ mein $x = y = 1$ rakkho: $2^{n} = (1 + 1)^{n} = \sum_{k = 0}^{n} (k n) .$

Worked examples

Steel-manned mistakes

Recall Feynman: ek 12-saal ke bachche ko samjhao

Socho tumhare paas kuch khilone hain aur tum jaanna chahte ho kitne alag-alag mutthi bhar khilone tum utha sakte ho. Pascal's triangle ek cheat-sheet hai jahan har number kehta hai "itne tareeqe se mutthi bhar sakte ho." Cool trick yeh hai: koi naya number bharne ke liye, bas uske upar baithne wale do numbers add karo — kyunki koi bhi naya khilona ya tumhari mutthi mein hai ya nahi hai, aur yeh do possibilities exactly woh do numbers hain jo upar hain. Poori row add karo aur tumhe milta hai har size ki mutthi bhar ke kitne tareeqe hain: $2$ apne aap se multiply hota hai ek baar har khilone ke liye, kyunki har khilona haan-ya-na kehta hai.

Flashcards

Pascal's triangle ki row

n

, position

k

ki entry kya hoti hai?

(k n)

, yaani

n

mein se

k

items choose karne ke tareeqon ki sankhya.

(k n)

ka formula batao.

\frac{n !}{k ! ( n - k )!}

Combination formula mein

k!

se kyun divide karte hain?

Ordered picks har set ko uske

k!

orderings ki wajah se over-count karte hain; humein unordered sets chahiye.

Pascal's rule batao.

(k n) = (k - 1 n - 1) + (k n - 1)

Pascal's rule ka combinatorial proof do.

Element

n

fix karo: usse contain karne wale subsets

(k - 1 n - 1)

+ nahi contain karne wale subsets

(k n - 1)

; disjoint aur exhaustive.

(k n) = (n - k n)

kyun?

Kaun se

k

lene hain yeh choose karna = kaun se

n - k

chhodne hain yeh choose karna.

\sum_{k = 0}^{n} (k n)

kya hai aur kyun?

2^{n}

; yeh saare subsets count karta hai (har element andar ya bahar).

n \geq 1

ke liye

\sum_{k = 0}^{n} (- 1)^{k} (k n)

kya hai?

0

; even-sized aur odd-sized subsets sankhya mein barabar hain.

^{n} P_{k}

aur

(k n)

mein fark?

^{n} P_{k}

ordered selections count karta hai;

(k n) =^{n} P_{k} / k!

unordered count karta hai.

Connections

Binomial Theorem — $(x + y)^{n}$ mein coefficients triangle ki rows hain.
Combinations and Permutations — $(k n)$ vs $^{n} P_{k}$ .
Addition and Multiplication Principles — dono proofs ki neenv.
Factorials — formula ka building block.
Hockey Stick Identity — triangle mein ek aur diagonal-sum pattern.
Fibonacci numbers — Pascal's triangle ke shallow diagonals Fibonacci mein sum hote hain.