Permutations & Combinations

Definition

Factorial

The factorial of a non-negative integer n, written n!, is the product of all positive integers from 1 to n: n! = n × (n-1) × (n-2) × ... × 2 × 1

Special case: 0! = 1 (by convention).

Examples: 5! = 120, 4! = 24, 3! = 6, 1! = 1.

Definition

Permutation

A permutation is an ordered arrangement of objects. The number of ways to arrange r objects chosen from n distinct objects is:

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

The order matters: choosing A then B is different from choosing B then A.

Example

Permutation Example

How many ways can we award gold, silver, and bronze medals to 3 of 10 runners?

Order matters (gold ≠ silver), so we use permutations: P(10, 3) = 10! / 7! = 10 × 9 × 8 = 720 ways.

Definition

Combination

A combination is an unordered selection of objects. The number of ways to choose r objects from n distinct objects is:

C(n, r) = n! / (r! × (n - r)!)

Also written as "n choose r" or (n r) with the binomial coefficient notation. Order does NOT matter: {A, B} is the same as {B, A}.

Example

Combination Example

How many 5-card hands can be dealt from a standard 52-card deck?

Order does not matter, so we use combinations: C(52, 5) = 52! / (5! × 47!) = (52 × 51 × 50 × 49 × 48) / (5 × 4 × 3 × 2 × 1) = 2,598,960.

Note

Permutation vs. Combination

Ask yourself: "Does the order of selection matter?"

Yes → Permutation P(n, r) No → Combination C(n, r)

Note: P(n, r) = C(n, r) × r! because each combination can be arranged in r! ways.

Theorem

Binomial Theorem

For any non-negative integer n:

(x + y)ⁿ = ∑ₖ₌₀ⁿ C(n, k) × xⁿ⁻ᵏ × yᵏ

Example: (x + y)³ = x³ + 3x²y + 3xy² + y³.

The coefficients C(n, 0), C(n, 1), ..., C(n, n) form row n of Pascal's Triangle.