Permutations and Combinations

Counting might seem elementary, but systematic counting of complex arrangements is profoundly important. This chapter answers the question: "In how many ways can we arrange or select objects?" A password lock might have millions of combinations; a lottery's odds depend on counting. Permutations count arrangements where order matters; combinations count selections where order doesn't. These concepts underpin probability theory (chapter-14-probability), statistics, and combinatorial optimization. Understanding counting principles reveals hidden mathematical structure in seemingly chaotic situations.

The Fundamental Counting Principle

Start simple. If you have 3 shirts and 2 pants, how many outfits can you wear? For each shirt choice, you have 2 pant choices: 3 × 2 = 6 outfits.

This is the Fundamental Counting Principle: If one task can be done in m ways and another in n ways, both tasks can be done together in m × n ways.

If you then have 4 shoe choices, the total becomes 3 × 2 × 4 = 24 outfits.

Permutations: When Order Matters

A permutation is an arrangement where order matters. How many ways can three people (Alice, Bob, Carol) stand in a line?

• First position: 3 choices
• Second position: 2 remaining choices
• Third position: 1 remaining choice

Total: 3 × 2 × 1 = 6 arrangements. (ABC, ACB, BAC, BCA, CAB, CBA)

This product 3 × 2 × 1 is called 3 factorial, written 3!, meaning "the product of all positive integers from 1 to 3."

General formula for permutations of n distinct objects: n! = n × (n-1) × (n-2) × ... × 2 × 1

Permutations of r objects selected from n: P(n,r) = n! / (n-r)!

For example, selecting 2 people from 5 to stand in line: P(5,2) = 5! / 3! = (5 × 4 × 3!) / 3! = 5 × 4 = 20

The insight: We have 5 choices for first position, 4 for second. No need to multiply through to 1; we stop when we've chosen r people.

Combinations: When Order Doesn't Matter

A combination is a selection where order doesn't matter. How many ways can we choose 2 people from 5 for a committee?

This is different from permutations. Selecting Alice and Bob is the same as selecting Bob and Alice—they're on the same committee.

Permutations count ordered selections; combinations count unordered selections. If we found 20 permutations of 2 from 5, we've overcounted. Each pair appears in 2 different permutations (AB and BA), so we divide by 2.

General formula for combinations of r from n: C(n,r) = n! / [r! × (n-r)!]

Also written as "n choose r."

C(5,2) = 5! / (2! × 3!) = (5 × 4) / (2 × 1) = 10

The 10 committees are: {AB, AC, AD, AE, BC, BD, BE, CD, CE, DE}

The Permutation-Combination Relationship

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

Permutations count each combination multiple times (once for each way to arrange r objects). Multiplying by r! accounts for these arrangements.

Factorial Properties and Special Cases

• 0! = 1 (by definition, making many formulas work smoothly)
• 1! = 1
• n! grows extremely rapidly: 10! = 3,628,800

Symmetry property: C(n,r) = C(n, n-r)

Choosing r objects is the same as choosing which (n-r) to leave behind. Selecting 2 people from 5 for a committee is the same as selecting 3 people to exclude: C(5,2) = C(5,3) = 10.

Permutations with Repetition

If some objects are identical, overcounting occurs. How many arrangements of the letters in "BALLOON"?

There are 7 letters. If all were distinct, we'd have 7! arrangements. But there are 2 L's and 2 O's, creating duplicates.

Permutations with repetition: n! / (n₁! × n₂! × ... × nₖ!)

Where n₁, n₂, ..., nₖ are the frequencies of repeated objects.

For BALLOON: 7! / (2! × 2!) = 5040 / 4 = 1260 distinct arrangements

Circular Permutations

Arranging people around a circular table is different from arranging in a line. Rotations of the same arrangement are identical.

Circular permutations of n objects: (n-1)!

For 5 people around a table: (5-1)! = 4! = 24 (compared to 5! = 120 for a line).

Real-World Applications

Lottery odds depend on combinations. Passwords and PIN codes use permutations. Tournament scheduling requires counting matchups. Genetics uses combinations to count trait distributions. The pharmaceutical industry counts drug compound possibilities. Encryption relies on the difficulty of counting solutions.

Key Formulas

• Factorial: n! = n × (n-1) × ... × 2 × 1
• Permutations: P(n,r) = n! / (n-r)!
• Combinations: C(n,r) = n! / [r! × (n-r)!]
• With repetition: n! / (n₁! × n₂! × ... × nₖ!)
• Circular: (n-1)!

Socratic Questions

1. Why does the formula for combinations divide by r!, while the formula for permutations doesn't? What mathematical principle is this division representing?

1. Consider selecting 3 people from 10 for a committee versus arranging 3 of those 10 in order. Why is the permutation count exactly 6 times the combination count? Does this ratio always hold?

1. The number of permutations of n objects is n!. Why does this grow so explosively as n increases? What does this explosive growth tell us about arranging larger sets?

1. In the formula C(n,r) = C(n, n-r), what's the intuition behind this symmetry? Why is choosing which r objects to include the same as choosing which n-r to exclude?

1. How would you count the number of ways to arrange letters in a word with repeated letters? Why can't you simply use n!? What role does dividing by factorial values of repetition counts play?