Permutations — nPr, arrangements with restrictions: Visual walkthrough

2.7.10 · D2 · Maths › Statistics & Probability — Intermediate › Permutations — nPr, arrangements with restrictions

Yeh page parent note ki central derivation ka slow-motion replay hai. Agar koi symbol aata hai, pehle hum usse define karte hain.

Step 1 — Hum actually count kar kya rahe hain?

KYA. Hamare paas distinct objects ka ek set hai. "Distinct" ka matlab sirf yeh hai ki aap unhe alag-alag pehchaan sako — jaise 5 alag letters $A, B, C, D, E$ , na ki 5 ek-jaisi marbles. Hum unhe ek row of positions mein kuch line up karna chahte hain, aur hum order ki parwah karte hain.

KYUN. Order hi permutation ka poora point hai. Row $A B$ ek alag line-up hai $B A$ se, chahe same do letters use hui hon. Agar hum order ki parwah nahi karte, toh hum ek group select kar rahe hote, jo ek alag subject hai (Combinations — nCr).

PICTURE. Figure dekhein: same do tiles ko do alag orders mein rakhne se do alag arrangements milte hain. Yeh "same tiles se do alag pictures" — exactly yahi reason hai ki order kyun matter karta hai.

Figure — Permutations — nPr, arrangements with restrictions

Step 2 — Har cheez ke neeche ek rule: choices ko multiply karo

KYA. Maano pehli position $3$ tareekon se fill ho sakti hai, aur in mein se har ek ke liye, doosri position $2$ tareekon se fill ho sakti hai. Toh complete rows ki sankhya $3 \times 2 = 6$ hai.

KYUN. Yeh Fundamental Counting Principle hai: jab aap ek decision karte hain aur phir doosra, totals multiply hote hain (aap unhe add nahi karte). Ise ek branching tree ki tarah socho — har pehla choice apna poora set of second choices sprout karta hai.

PICTURE. Neeche ka tree $3$ branches se start hota hai. Har branch $2$ mein split hoti hai. Neeche leaves count karne par $3 \times 2 = 6$ milta hai — har leaf ek finished arrangement hai.

first-slot choices 3 \times second-slot choices, for each first 2 = finished rows (leaves) 6

Step 3 — Choices ko position-by-position shrink hote dekhein

KYA. Ab $n$ distinct objects mein se $r$ positions fill karo, koi repeat nahi (ek baar letter use ho gaya, toh gaya). Left to right fill karo aur record karo ki har step par kitne available hain.

KYUN. "No repeats" yahi wajah hai ki count exactly ek baar har baar girta hai. Yeh single shrinking-by-one behaviour hi poore formula ka engine hai.

PICTURE. Neeche boxes ki row har box ke upar available count dikhati hai: $n$ , phir $n - 1$ , phir $n - 2$ , … Daayein taraf bache hue tiles ka pool physically har box par ek tile se shrink hota hai.

Position	Available choices	Ek kam kyun?
1st	$n$	abhi tak kuch use nahi hua
2nd	$n - 1$	ek object ab placed hai
3rd	$n - 2$	do placed hain
$\dots$	$\dots$	$\dots$
$r$ -th	$n - r + 1$	$r - 1$ already placed hain

Step 4 — Boxes ko multiply karo: raw formula

KYA. Step 2 ka multiply-rule Step 3 ke saare boxes par apply karo:

n P_{r} = box 1 n \cdot box 2 (n - 1) \cdot box 3 (n - 2) \dots box r (n - r + 1)

KYUN. Har box ek independent decision hai pehle wale decisions ko given, isliye counting principle se unke choice-counts multiply hote hain. Symbol $n P_{r}$ (padho " $n$ permute $r$ ") is product ka sirf ek naam hai.

PICTURE. Figure boxes ko stack karta hai aur unke beech ek bada $\times$ draw karta hai, saath mein descending numbers $n, n - 1, \dots$ likhe hain. Yeh product hai, visible banaya gaya.

Step 5 — Factorials se compress karo (smart trick)

KYA. Ek factorial $n!$ ka matlab hai " $n$ se $1$ tak har whole number ko multiply karo": $n! = n (n - 1) \dots 2 \cdot 1$ . Hamara raw product jaldi ruk jaata hai — yeh $n - r + 1$ par ruk jaata hai aur "tail" $(n - r) (n - r - 1) \dots 1$ tak kabhi nahi pahunchta.

KYUN. Hum ek tidy closed form chahte hain. Trick: missing tail $(n - r)!$ se multiply aur divide karo. Ek hi cheez se multiply aur divide karne par kuch nahi badalta, lekin yeh top ko ek poora factorial ban'ne deta hai.

PICTURE. Neeche, poora ladder $n!$ top se bottom tak drawn hai. Coral part woh piece hai jo hum actually chahte hain ( $n P_{r}$ ); mint part leftover tail $(n - r)!$ hai. Divide karne par mint tail cut ho jaati hai.

n P_{r} = what we want (coral) n (n - 1) \dots (n - r + 1) \cdot \frac{( n - r )! tail (mint)}{same tail, divides out ( n - r )!} = \frac{n !}{( n - r )!}

Apne running example $n = 5, r = 3$ par verify karte hain:

5 P_{3} = \frac{5 !}{( 5 - 3 )!} = \frac{5 !}{2 !} = \frac{120}{2} = 60, aur 5 \cdot 4 \cdot 3 = 60. ✓

Step 6 — Edge case A: har position fill karna ( $r = n$ )

KYA. Agar aap saare objects arrange karo, toh $r = n$ ? Formula deta hai

n P_{n} = \frac{n !}{( n - n )!} = \frac{n !}{0 !} .

KYUN. Hume $0!$ ko samajhna hoga. Rule hai $0! = 1$ (dekho Factorials and 0!). Is se, $n P_{n} = \frac{n !}{1} = n!$ — saare $n$ objects arrange karne ke $n!$ orders hain, jo exactly Step 4 predict karta hai (boxes $n, n - 1, \dots, 1$ tak count down karte hain).

PICTURE. Figure saare boxes fill karta hai; leftover pool empty ho jaata hai, aur descending numbers $1$ tak poore neeche pahunchte hain.

Step 7 — Edge case B: koi bhi position fill nahi karna ( $r = 0$ )

KYA. Zero positions fill karo:

n P_{0} = \frac{n !}{( n - 0 )!} = \frac{n !}{n !} = 1.

KYUN. Exactly ek empty arrangement hai — blank row. Zero nahi (woh matlab hota "impossible"); kuch nahi karna ek valid outcome hai. Formula agree karta hai: top aur bottom identical hain, isliye cancel hokar $1$ ho jaate hain.

PICTURE. Koi box nahi ki ek empty row, labelled "1 tarika: the empty line-up." Poora pool side mein untouched rakha hai.

Recall Quick self-test

$n P_{0} = 1$ kyun hai aur $0$ kyun nahi? ::: Kyunki "kuch arrange nahi karna" exactly ek tarike se possible hai (empty arrangement); $0$ ka matlab hota impossible. $7 P_{7}$ kya hai? ::: $7! = 5040$ , kyunki $(7 - 7)! = 0! = 1$ .

Ek-picture summary

Upar ki saari cheez ek single diagram mein compress ki gayi hai: row of boxes → shrinking choices → multiply → unused tail cancel → clean formula. Isse left to right trace karo.

Step 3: choices shrink n, n - 1, \dots, n - r + 1 \times (Step 4) raw product n (n - 1) \dots (n - r + 1) \times \frac{( n - r )!}{( n - r )!} (Step 5) \frac{n !}{( n - r )!}

Recall Feynman retelling — poori walkthrough ek 12-saal ke bachche ko explain karo

Socho apne doston ko photo ke liye line up kar rahe ho lekin unke liye sirf thodi jagah hai. Row mein pehli jagah ke liye, koi bhi dost wahan khad ho sakta hai — yeh bahut saari choices hain, ise $n$ kaho. Ek baar koi khada ho gaya, woh use ho gaya, isliye agli jagah ke liye ek kam dost bachta hai, phir ek aur kam. Saari possible photos count karne ke liye bas har jagah "kitne bache hain" multiply karo — kyunki har pehla choice apna fresh set of second choices carry karta hai (yahi branching tree hai). Boxes multiply karo aur $5 \times 4 \times 3$ jaisi ek chain milti hai. Mathematicians ko tidy formulas pasand hain, isliye woh notice karte hain ki yeh chain sirf $n!$ ka top part hai (poora countdown $n$ se $1$ tak) aur bottom part cut off hai. Ise cleanly cut karne ke liye woh "jo dost photo mein nahi aaye" unke factorial se divide karte hain, $(n - r)!$ . Isse neat $\frac{n !}{( n - r )!}$ milta hai. Aur weird cases theek behave karte hain: sab ko photograph karo aur $n!$ milta hai (kyunki $0! = 1$ se divide karna kuch nahi karta); kisi ko nahi photograph karo aur exactly ek tarika hai — empty photo.

Connections

Fundamental Counting Principle — Step 2 ka multiply-rule yahi principle hai.
Factorials and 0! — Steps 5–7 $0! = 1$ par rely karte hain.
Combinations — nCr — jab order matter karna band ho jaaye, $r!$ se divide karo: $n C_{r} = \frac{n P _{r}}{r !}$ .
Circular Permutations — same shrinking idea, ek ring mein bend ki gayi.
Permutations with Repetition — kya badalta hai jab saare objects distinct nahi hote.
Probability — Equally Likely Outcomes — yeh counts numerators aur denominators ban jaate hain.