Combinations and Permutations Deep Dive

Fundamental Counting Principle

If event A can occur in m ways and event B in n ways:

Total ways for both: m × n

Extends to multiple events: m × n × p × ...

Example: Outfit Choices

3 shirts, 4 pants, 2 pairs of shoes

Total outfits:

3 × 4 × 2 = 24 outfits

Factorials

n! = n × (n-1) × (n-2) × ... × 2 × 1

Special case: 0! = 1

Examples:

5! = 5 × 4 × 3 × 2 × 1 = 120
3! = 6
10! = 3,628,800

Permutations (Order Matters)

Permutation: Arrangement where order matters

Formula (n objects, r chosen):

P(n, r) = n! / (n-r)!

All n objects: P(n, n) = n!

Example: Race Podium

10 runners, top 3 positions (gold, silver, bronze)

Calculate:

P`(10, 3)` = 10! / 7!
         = 10 × 9 × 8
         = 720 ways

Combinations (Order Doesn't Matter)

Combination: Selection where order doesn't matter

Formula:

C(n, r) = n! / [r!(n-r)!]

Also written: (n choose r) or ₙCᵣ

Example: Committee Selection

Choose 3 people from 8 for committee

Calculate:

C`(8, 3)` = 8! / (3! × 5!)
        = (8 × 7 × 6) / (3 × 2 × 1)
        = 336 / 6
        = 56 ways

Permutations vs Combinations

Key question: Does order matter?

Permutations: Yes (arrangements, rankings, passwords)

Combinations: No (teams, committees, selections)

Example: Compare

5 books, choose 3

Permutations: P(5,3) = 60 (different orders counted)

Combinations: C(5,3) = 10 (orders not counted)

Relationship: P(n,r) = r! × C(n,r)

Permutations with Repetition

When objects can repeat:

nʳ (n choices, r positions)

Example: PIN Code

4-digit PIN (0-9, repetition allowed)

Calculate:

10⁴ = 10,000 possible PINs

Permutations of Identical Objects

When some objects identical:

Formula: n! / (n₁! × n₂! × ... × nₖ!)

Where nᵢ = count of each identical type

Example: Letters in MISSISSIPPI

11 letters: 1M, 4I, 4S, 2P

Calculate:

11! / (1! × 4! × 4! × 2!)
= 39,916,800 / (1 × 24 × 24 × 2)
= 39,916,800 / 1,152
= 34,650 arrangements

Circular Permutations

Arranging objects in circle:

Formula: (n-1)!

Reason: Fix one position to eliminate rotational duplicates

Example: Round Table

6 people around circular table

Calculate:

(6-1)! = 5! = 120 arrangements

If direction matters (clockwise vs counterclockwise): 5! / 2

Combinations with Repetition

Stars and bars method

Formula: C(n+r-1, r)

Choose r items from n types (repetition allowed)

Example: Fruit Selection

Choose 4 fruits from 3 types (apples, bananas, oranges) Repetition allowed

Calculate:

C(3+4-1, 4) = C`(6, 4)`
             = 15 ways

Could be: AAAA, AAAB, AABB, etc.

Distributing Identical Objects

Distribute n identical objects into k distinct boxes

Formula: C(n+k-1, k-1)

Example: Candy Distribution

Give 10 identical candies to 3 children

Calculate:

C(10+3-1, 3-1) = C`(12, 2)`
                = 66 ways

Complementary Counting

Sometimes easier to count opposite, then subtract

Total - Unwanted = Desired

Example: At Least One

Flip coin 5 times. Probability of at least one head?

Total outcomes: 2⁵ = 32

No heads (all tails): 1

At least one head: 32 - 1 = 31

Probability: 31/32

Inclusion-Exclusion Principle

For overlapping sets:

|A ∪ B| = |A| + |B| - |A ∩ B|

Three sets: |A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|

Example: Students Taking Courses

30 students

• 18 take math
• 15 take science
• 10 take both

How many take math OR science?

Calculate:

18 + 15 - 10 = 23 students

Derangements

Permutations where no element in original position

Formula: D(n) ≈ n! / e

Exact: Complex recursive formula

Example: Hat Check Problem

4 people, 4 hats. None gets own hat back?

D(4) = 9 derangements

Pascal's Triangle

Binomial coefficients arranged:

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

Entry (n, r) = C(n, r)

Property: C(n,r) = C(n-1,r-1) + C(n-1,r)

Multinomial Coefficients

Divide n objects into groups:

n! / (n₁! × n₂! × ... × nₖ!)

Example: Team Division

12 players divide into 3 teams of 4

Calculate:

12! / (4! × 4! × 4!)
= 479,001,600 / 13,824
= 34,650 ways

Pigeonhole Principle

If n+1 objects in n holes, at least one hole has 2+ objects

Generalizes: ⌈(n+1)/k⌉ objects in some hole if n+1 objects in k holes

Example: Birthday Problem

13 people, 12 months

At least 2 share birth month (pigeonhole principle)

Applications: Probability

Probability = Favorable outcomes / Total outcomes

Use counting to find both

Example: Poker Hand

Probability of full house?

Total 5-card hands: C(52, 5) = 2,598,960

Full houses: 3744 (calculation omitted)

Probability: 3744/2,598,960 ≈ 0.00144

Applications: Cryptography

Password strength: Number of possible combinations

Example: 8-character password (62 choices: a-z, A-Z, 0-9)

Total: 62⁸ ≈ 218 trillion possibilities

Practice