Chapter 6 - Permutations and Combinations
1. Introduction - Counting Arrangements and Selections
Counting is about how many ways we can arrange or select things. 3 books A,B,C arrange on shelf 3! =6 ways ABC ACB BAC BCA CAB CBA. Order matters.
Permutation order matters AB different BA, Combination order does not matter AB same BA same team.
Fundamental Principle: One job m ways second n ways both together m×n multiplication principle. 3 shirts 2 pants outfits 3×2=6 combinations.
Addition: One job m ways or another n ways not both together total m+n ways. 3 bus routes or 2 train routes total 5 ways.
2. Fundamental Principle - Multiplication and Addition
Multiplication: Event A m ways Event B n ways following A both together m×n ways.
Example 1: 4 ways home to market 3 ways market to college total 4×3=12 ways home to college via market.
Example 2: 2-digit numbers from 1,2,3 without repetition tens 3 choices ones 2 remaining total 3×2=6 numbers 12,13,21,23,31,32.
Example 3: 3-digit numbers 0-9 without repetition hundreds cannot be 0 9 choices 1-9 tens 9 remaining including 0 ones 8 remaining total 9×9×8=648.
Addition: Work A m ways Work B n ways mutually exclusive cannot together either A or B m+n ways. Choose boy 5 or girl 4 total 9 ways.
3. Factorial n! and Permutation Formula nPr
Factorial n! = n×(n-1)×...×2×1 product down to 1. Example 5!=120 4!=24 3!=6 2!=2 1!=1 Special 0!=1 by definition empty product 1 way arrange nothing.
Factorials grow fast 6!=720 7!=5040 8!=40320 10!=3628800.
Permutation nPr = n!/(n-r)! arrangement r from n order matters. Example 5P2=5!/3!=5×4=20 ways choose arrange 2 from 5 AB different BA. 7P3=7!/4!=7×6×5=210 ways choose 3 seats from 7.
Special n=r nPn=n!/(n-n)!=n!/0!=n! arrangement all n items n! ways.
4. Permutations - Order Matters
Permutation arrangement order important AB different BA.
Seating 5 friends 3 chairs First chair 5 choices second 4 remaining third 3 remaining total 5×4×3=60=5P3.
Race podium 8 athletes first second third place 8P3=8×7×6=336 ways gold silver bronze different.
Passwords 4-digit from 0-9 without repetition 10P4=10×9×8×7=5040 each arrangement different code.
Bookshelf 6 books all 6!=720 ways. Number plates 2 letters from 26 without repetition 26P2=650.
Key tip If rearranging gives new outcome different arrangement → permutation order matters.
5. Combinations - Order Does Not Matter
Combination selection order does NOT matter AB same BA same group.
Formula nCr=n!/(r!(n-r)!)=nPr/r! because permutation counts order r! times more each group r can be arranged r! ways.
Team selection 5 players how many 3-person teams? Order does not matter ABC same CBA same team 5C3=5!/(3!2!)=10 teams.
4 people choose 2 team 4C2=6 teams AB AC AD BC BD CD 6 unique groups order swapped same group.
Lottery Choose 6 from 49 49C6=13,983,816 tickets massive why odds low. Handshake 10 people 10C2=45 handshakes AB same BA.
Difference: Permutation nPr order matters arrangement lineup race podium password, Combination nCr order does not matter selection group team lottery.
6. Properties and Identities
nCr=nC(n-r) choosing r same as choosing n-r to leave behind Example 5C3=5C2 both 10.
nC0=1 choose nothing nCn=1 choose all nC1=n choose 1 from n.
nCr+nC(r-1)=(n+1)Cr Pascal identity Pascal triangle each entry sum two above.
Pascal triangle Row n contains nC0 nC1 nC2 ... nCn Example Row 4: 1 4 6 4 1.
nPr=n×(n-1)P(r-1) recursion n!=n×(n-1)! factorial.
Trick nCr maximum when r=n/2 middle row largest.
7. Practical Examples Around Us
Seating Classroom 30 students 5 front seats 30P5=30×29×28×27×26 massive.
Mobile password 4-digit PIN 0-9 with repetition allowed each digit 10 choices total 10^4=10000 PINs with repetition without 10P4=5040.
Car plates MH-01-AB-1234 count possible plates.
Lottery 49C6=13,983,816 why jackpot hard. Team selection 11 from 20 20C11 teams committee 3 from 10 10C3=120 committees.
Handshakes 12 people party each handshake once each other 12C2=66.
Bookshelf 5 books 5!=120 ways. Race 100m 8 runners gold silver bronze 8P3=336 podiums. Phone numbers 10-digit first cannot 0 counting multiplication principle.
8. Formulas Short Tricks
0!=1 by definition 1!=1 n! = n×(n-1)! nPr=n!/(n-r)!=n×(n-1)×...×(n-r+1) product r terms starting n descending nCr=n!/(r!(n-r)!)=nPr/r! nCr=nC(n-r) nC0=1 nCn=1 nC1=n nCr+nC(r-1)=(n+1)Cr Pascal nPn=n! Trick identify permutation vs combination If after rearranging pick you get new outcome different → permutation order matters lineup race password seating number plate If same group same team same selection → combination order does not matter selection group team lottery committee handshake Quick reference 5!=120 6!=720 7!=5040 8!=40320 grows quickly Without repetition use P and C factorial division with repetition m^n multiplication principle.
