Episode 8 — Aptitude and Reasoning / 8.14 — Permutations and Combinations
8.14 Quick Revision -- Permutations and Combinations
Core Formulas at a Glance
+--------------------------------------------+----------------------------------+
| Concept | Formula |
+--------------------------------------------+----------------------------------+
| Factorial | n! = n(n-1)(n-2)...1 |
| 0! | 1 |
| Permutation (nPr) | n! / (n-r)! |
| Combination (nCr) | n! / [r!(n-r)!] |
| Relation: P and C | nPr = r! x nCr |
| Symmetry | nCr = nC(n-r) |
| Pascal's Identity | nCr + nC(r-1) = (n+1)Cr |
| Sum of combinations | nC0+nC1+...+nCn = 2^n |
+--------------------------------------------+----------------------------------+
Arrangement Formulas
+--------------------------------------------+----------------------------------+
| Scenario | Formula |
+--------------------------------------------+----------------------------------+
| n distinct objects in a line | n! |
| r objects from n distinct (no repeat) | nPr = n!/(n-r)! |
| With identical items (p,q,r... same) | n! / (p! x q! x r! x ...) |
| r positions, n types, repeat allowed | n^r |
| Circular arrangement | (n-1)! |
| Necklace/bracelet | (n-1)! / 2 |
+--------------------------------------------+----------------------------------+
Selection Formulas
+--------------------------------------------+----------------------------------+
| Scenario | Formula |
+--------------------------------------------+----------------------------------+
| Choose r from n distinct | nCr |
| Always include k specific items | (n-k)C(r-k) |
| Always exclude k specific items | (n-k)Cr |
| At least 1 | Total - None |
| Subsets of n elements | 2^n |
| Non-empty subsets | 2^n - 1 |
+--------------------------------------------+----------------------------------+
Distribution Formulas (Stars and Bars)
+--------------------------------------------+----------------------------------+
| Scenario | Formula |
+--------------------------------------------+----------------------------------+
| n identical into r distinct (>=0 each) | (n+r-1)C(r-1) |
| n identical into r distinct (>=1 each) | (n-1)C(r-1) |
| n distinct into r distinct groups | r^n |
| n people into groups of a,b,c | n! / (a! x b! x c!) |
| Equal unnamed groups of size k, m groups | n! / [(k!)^m x m!] |
+--------------------------------------------+----------------------------------+
Geometry Shortcuts
+--------------------------------------------+----------------------------------+
| Scenario | Formula |
+--------------------------------------------+----------------------------------+
| Lines from n points (no 3 collinear) | nC2 |
| Triangles from n points (no 3 collinear) | nC3 |
| Diagonals of n-gon | n(n-3)/2 |
| With m collinear: triangles | nC3 - mC3 |
| With m collinear: lines | nC2 - mC2 + 1 |
| Max intersections of n lines | nC2 |
+--------------------------------------------+----------------------------------+
Memorize These Values
Factorials: nC2 shortcut: Powers of 2:
1! = 1 nC2 = n(n-1)/2 2^1 = 2
2! = 2 2^2 = 4
3! = 6 3C2 = 3 2^3 = 8
4! = 24 4C2 = 6 2^4 = 16
5! = 120 5C2 = 10 2^5 = 32
6! = 720 6C2 = 15 2^6 = 64
7! = 5,040 7C2 = 21 2^7 = 128
8! = 40,320 8C2 = 28 2^8 = 256
9! = 362,880 9C2 = 36 2^9 = 512
10! = 3,628,800 10C2 = 45 2^10 = 1024
Decision Flowchart
Does ORDER matter?
|
+-- YES --> PERMUTATION (nPr)
| |
| +-- All distinct? --> n! or nPr
| +-- Repeats? --> n! / (p!q!...)
| +-- Circular? --> (n-1)!
|
+-- NO --> COMBINATION (nCr)
|
+-- Restrictions?
+-- Must include k --> (n-k)C(r-k)
+-- Must exclude k --> (n-k)Cr
+-- At least type --> Total - complement
Common Keyword Mapping
Arrangement, sequence, rank, order, PIN, password --> Permutation
Committee, team, group, selection, hand of cards --> Combination
Distribute, share, divide equally --> Stars and Bars / Grouping
Around a table, circular seating --> (n-1)!
Necklace, bracelet, garland --> (n-1)!/2
No two adjacent, alternating --> Gap method
Together / as a unit --> Bundle + internal arrangement
Top 5 Exam Traps
1. Forgetting first digit != 0 in number problems.
2. Confusing circular with linear (use (n-1)!, not n!).
3. Not dividing by m! when groups are unnamed/identical.
4. Mixing up "at least" with "exactly."
5. Forgetting internal arrangement when items are bundled.
Return to: 8.14 README