Lesson 8 — Intermediate

Permutations & Combinations

Combinatorics matlab ginne ki maths — "kitne tarike se ho sakta hai". Is lesson mein seekhenge addition-multiplication principles, permutations (order matter), combinations (sirf selection), circular arrangements aur repeated letters wale special cases — sab worked examples ke saath.

Counting ke 2 principles

Ek hi line se decide karo: kya dono kaam ek saath ho sakte hain? Haan (AND) → multiplication. Ya koi EK hai (OR) → addition. Ye do rules har question mein lagte hain.

Permutations — order matter karta hai

PERMUTATION = arrangement, order matter karta hai

P(n, r) = n! / (n − r)!   → n cheezon se r chun kar order mein

Example: 5 alag books mein se 2 shelf pe rakhne
P(5, 2) = 5! / 3! = 5 × 4 = 20 tarike

Poora arrange: n! = n × (n−1) × ... × 1
5 books → 5! = 120     (0! = 1 by definition)

Repetition allowed ho toh: n^r
4-digit number, digits repeat = 10^4 = 10000

Combinations — sirf selection

Combination mein order matter nahi — sirf kaun-kaun chahiye:

COMBINATION = selection, order nahi

C(n, r) = n! / (r! × (n − r)!)  = nCr

Example: 15 khiladiyon mein se 11 ki team (order nahi)
C(15, 11) = C(15, 4) = 1365 tarike
[ C(n, r) = C(n, n−r) — chhota side aasaan ]

Worked: C(5, 2) = 5! / (2! × 3!) = 120 / (2 × 6) = 10

Team chunna = combination
11 khiladiyon ka batting order = permutation = 11!

Ye do line sabse important hain: team = C, batting order = P. Aur identity C(n,r) = C(n,n−r) se calculation aksar chhoti ho jaati hai — 11 ki jagah 4 count karo.

Special cases — circular, repeated letters, division

CIRCULAR arrangement: (n − 1)!  (round table — rotation same)
  6 log round table = 5! = 120

REPEATED letters: n! / (f1! × f2! × ...)
  MISSISSIPPI = 11! / (4! 4! 2!) = 34650
  (M=1, I=4, S=4, P=2 — repeat wale sab factor mein)

DIVISION principle: jab double counting ho, utna divide karo

Identities (yaad rakho):
  C(n, r) = C(n, n − r)
  P(n, r) = C(n, r) × r!
  n! = n × (n − 1)!
  Σ k (1 se n) = n(n + 1)/2

• At least wale questions: "kam se kam 1" = total − (jo bilkul nahi) — complement count karo.
• Distribution: n alag objects r boxes mein = r^n (boxes distinct hona zaroori).
• Bijections: n elements ke n arrangements = n! — isi liye bijections bhi n! hote hain.
• GATE tip: formula ratne se pehle 2 examples solve karo — confusion khud khatam ho jaayegi.

Exercise

Common mistakes

• P aur C ka mix: Team chunna = C (selection), team ko order mein lagana = P (arrangement). Question ka last word hi batata hai kaunsa lagana hai.
• Repeated letters mein divide bhool jaana: MISSISSIPPI jaise words mein repeat hone wale letters ki frequency ka factorial neeche aata hai — warna answer 5 crore+ aa jaata hai jo galat hai.
• Circular ko linear samajhna: Round table mein (n−1)! hota hai, straight line mein n!. Rotation same count hota hai — isi liye ek kam.

4 duty chunna (order nahi) = C(15, 4) = 1365
11 ki dance team (order nahi) = C(15, 11) = 1365
Agar duties alag-alag hon (duty1,2,3,4) = P(15,4) = 32760
Order matters? → P. Sirf group? → C.