Episode 8 — Aptitude and Reasoning / 8.14 — Permutations and Combinations

8.14.b Tips, Tricks, and Shortcuts -- Permutations and Combinations

1. When to Use Permutations vs Combinations

This is the single most important decision in any P&C problem. Master this and you solve half the battle.

The One-Question Test

"If I rearrange the selected items, does it create a different outcome?"

  • Yes --> Permutation (order matters)
  • No --> Combination (order does not matter)

Keyword Cheat Sheet

PERMUTATION keywords (order matters):
  arrange, order, rank, sequence, password, PIN, code,
  first-second-third, president/VP/secretary, digits,
  seating arrangement, word formation, schedule, itinerary

COMBINATION keywords (order does NOT matter):
  choose, select, pick, committee, team, group, hand (cards),
  sample, delegation, collection, subset, donate, distribute

Quick Decision Flowchart

Problem asks to count ways?
    |
    v
Are positions/ranks being assigned?
    |          |
   YES         NO
    |          |
    v          v
  Use P      Are items being merely selected/grouped?
               |          |
              YES         NO
               |          |
               v          v
             Use C     Reread problem carefully

2. Pascal's Triangle

Pascal's triangle gives you nCr values instantly for small n without any calculation.

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 6:        1   6  15  20  15   6   1
Row 7:      1   7  21  35  35  21   7   1
Row 8:    1   8  28  56  70  56  28   8   1
Row 9:  1   9  36  84 126 126  84  36   9   1
Row10:1  10  45 120 210 252 210 120  45  10   1

How to Read

  • Row n, Position r (both starting from 0) gives nCr.
  • Example: Row 8, Position 3 = 8C3 = 56

How to Build

Each number = sum of the two numbers directly above it.

Pascal's Identity: nCr = (n-1)C(r-1) + (n-1)Cr

Useful Observations from Pascal's Triangle

1. Each row sums to 2^n.
   Row 4: 1+4+6+4+1 = 16 = 2^4

2. Each row is symmetric.
   nCr = nC(n-r)

3. The second element in each row equals n.
   nC1 = n

4. The third element gives triangular numbers.
   nC2 = n(n-1)/2

3. Common Patterns and Shortcuts

Shortcut 1: Compute nCr Quickly by Cancellation

Never expand full factorials. Instead, use the shorthand:

nCr = [n x (n-1) x (n-2) x ... x (n-r+1)] / r!

Take the SMALLER of r and (n-r) to minimize work.

Example: 20C17

20C17 = 20C3          (since 20C17 = 20C3, and 3 is smaller)
      = (20 x 19 x 18) / (3 x 2 x 1)
      = 6840 / 6
      = 1140

Shortcut 2: nC2 Formula

This comes up extremely often (handshakes, line segments, matches, etc.):

nC2 = n(n-1) / 2

Example: Handshakes among 15 people = 15C2 = 15 x 14 / 2 = 105

Shortcut 3: Total Subsets

The total number of subsets of a set with n elements:

Total subsets = 2^n
Non-empty subsets = 2^n - 1

Shortcut 4: Derangements (No Item in Original Position)

D(n) = n! x [1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n/n!]

Quick values:

D(1) = 0
D(2) = 1
D(3) = 2
D(4) = 9
D(5) = 44
D(6) = 265

Shortcut 5: Number of Diagonals in a Polygon

Diagonals = nC2 - n = n(n-1)/2 - n = n(n-3)/2

Example: Decagon (10 sides): 10(10-3)/2 = 10 x 7/2 = 35

4. Word Formation Tricks

Trick 1: Total Words from n Distinct Letters (All Used)

Total words = n!

Trick 2: Words with Vowels Together

Treat all vowels as a single unit. Arrange the unit + consonants. Then arrange vowels within the unit.

Example: Words from "ORANGE" with vowels (O, A, E) together.

Step 1: Treat (OAE) as one unit. Units = {(OAE), R, N, G} = 4 units
         Arrange 4 units = 4! = 24

Step 2: Arrange vowels within the unit = 3! = 6

Total = 24 x 6 = 144

Trick 3: Words with Vowels Never Together

Words with vowels never together = Total words - Words with vowels together

OR use the Gap Method:

  1. Arrange consonants first.
  2. Place vowels in the gaps (including ends) between consonants.
Example: Words from "ORANGE" with no two vowels adjacent.

Step 1: Arrange consonants R, N, G = 3! = 6
        Gaps: _R_N_G_ = 4 gaps

Step 2: Place 3 vowels in 4 gaps = 4P3 = 24

Total = 6 x 24 = 144

Trick 4: Words with Letters in Alphabetical Order

If n distinct letters must appear in alphabetical (or any fixed) order:

Total arrangements / n! (for n letters that must be in order)

Or more precisely: for a specific subset of k letters that must be in order among all n letter positions:

n! / k!

Trick 5: Words Beginning with a Specific Letter

Fix that letter in the first position, arrange the rest.

Example: Words from "TIGER" starting with T.

Fix T at position 1. Arrange I, G, E, R = 4! = 24

5. Number Formation Tricks

Forming Numbers from Given Digits

Example: How many 3-digit numbers from {1, 2, 3, 4, 5} (no repetition)?

Hundreds place: 5 choices
Tens place: 4 choices
Units place: 3 choices

Total = 5 x 4 x 3 = 60

Even Numbers

The units digit must be even. Fix the units digit first, then fill remaining positions.

Numbers Greater Than a Given Value

Work digit by digit from the leftmost position.

Numbers Divisible by 5

Units digit must be 0 or 5. Fix it, then count the rest.

Trick for "0" in Digit Problems

When 0 is among the available digits and the number cannot start with 0:

Step 1: Count total numbers (ignoring the restriction).
Step 2: Subtract numbers that start with 0.

OR fix the first digit (must be non-zero) separately.

Example: 4-digit numbers from {0, 1, 2, 3, 4} (no repetition).

Thousands place: 4 choices (1, 2, 3, 4 -- not 0)
Hundreds place: 4 choices (remaining 4 digits including 0)
Tens place: 3 choices
Units place: 2 choices

Total = 4 x 4 x 3 x 2 = 96

6. Seating Arrangement Tricks

Circular Table

n people around a table = (n-1)!

Two People Must Sit Together

Treat them as one unit. Then:

Ways = (n-1-1)! x 2! = (n-2)! x 2

(the x2 accounts for their internal arrangement)

Two People Must NOT Sit Together

Ways = Total - Together
     = (n-1)! - (n-2)! x 2

Men and Women Alternating (Circular)

Fix one group (say men) in circle = (m-1)!
Arrange other group in gaps = m!      (since there are exactly m gaps)

Total = (m-1)! x m!

(Valid only when number of men = number of women = m)

7. Distribution and Grouping Shortcuts

Distributing n Distinct Objects into r Distinct Groups

Each object can go into any of the r groups:

Total = r^n

Distributing n Identical Objects into r Distinct Groups (Non-Negative)

(n + r - 1)C(r - 1)

Dividing n People into Groups of Given Sizes

Into groups of sizes a, b, c (where a + b + c = n):

n! / (a! x b! x c!)

If groups are of equal size k and the groups are indistinguishable:

n! / [(k!)^m x m!]

where m = n/k is the number of groups.

8. Geometric Application Shortcuts

Lines from n Points (No 3 Collinear)

Lines = nC2

Triangles from n Points (No 3 Collinear)

Triangles = nC3

With Collinear Points

If m points out of n are collinear:

Triangles = nC3 - mC3
Lines = nC2 - mC2 + 1     (the +1 is for the one line through collinear points)

Intersections of Lines

Maximum intersections of n lines (no two parallel, no three concurrent):

Intersections = nC2

9. Common Mistakes to Avoid

Mistake 1: Confusing P and C.
Fix: Always ask "does order matter?"

Mistake 2: Forgetting the restriction that first digit cannot be 0.
Fix: Handle the leftmost digit separately.

Mistake 3: Not accounting for identical items.
Fix: Divide by the factorial of each group of identical items.

Mistake 4: Double counting in "at least" problems.
Fix: Use complementary counting: At least 1 = Total - None.

Mistake 5: Circular vs. linear confusion.
Fix: Circular uses (n-1)!, linear uses n!

Mistake 6: Overcounting when dividing into equal groups.
Fix: Divide by m! if m groups are interchangeable.

Mistake 7: Forgetting the internal arrangement.
Fix: When grouping items as a block, multiply by the arrangements within the block.

10. Speed Techniques for Exams

Technique 1: Use nCr = nC(n-r) to Simplify

Always compute the version with the smaller r.

Technique 2: Memorize Small Combination Values

nC2 = n(n-1)/2
nC3 = n(n-1)(n-2)/6

Technique 3: Quick nCr Computation via Step-by-Step Division

10C4 = (10 x 9 x 8 x 7) / (4 x 3 x 2 x 1)

Compute step-by-step, cancelling as you go:
= 10/1 x 9/2 x 8/3 x 7/4
= 10 x 4.5 x 2.666... x 1.75

Or better, cancel factors:
= (10 x 9 x 8 x 7) / 24
= 5040 / 24
= 210

Technique 4: Verify Using Small Cases

If unsure of a formula, test it with very small numbers (n=3, r=2) where you can manually count.

Technique 5: Parity Check

nCr is odd if and only if every bit of r (in binary) is also set in n. (Lucas' theorem)

Previous: 8.14.a Concepts and Formulas | Next: 8.14.c Solved Examples