Combinatorics

Fundamental Principles

1. Rule of Sum: If a task can be done in one of n₁ ways AND in one of n₂ ways, where none of the set of n₁ ways is the same as any of the set of n₂ ways, then there are n₁ + n₂ ways to do the task.

2. Rule of Product: If a procedure can be broken down into a sequence of two tasks, and there are n₁ ways to do the first task and for each of these ways, there are n₂ ways to do the second task, then there are n₁ * n₂ ways to do the procedure.

Permutations

A permutation is an arrangement of objects in a specific order.

The number of permutations of n distinct objects is n! (n factorial).

The number of arrangements of r objects taken from n distinct objects (where order matters) is given by:

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

Combinations

A combination is a selection of items from a set that has distinct members, such that the order of selection does not matter.

The number of ways to choose r objects from a set of n distinct objects (where order doesn't matter) is given by the binomial coefficient, read as "n choose r":

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

These values can be precomputed using Pascal's Triangle identity: C(n, r) = C(n-1, r-1) + C(n-1, r), often in the context of modular arithmetic to prevent overflow.

Applications in Algorithms

• Counting Paths on a Grid: The number of paths from (0,0) to (m,n) moving only right or down is C(m+n, m).
• Probability Problems: Calculating probabilities often involves dividing the number of favorable outcomes by the total number of outcomes, both of which are counting problems.
• Dynamic Programming: Many DP state definitions are based on combinatorial properties (e.g., number of ways to make change).
• Binomial Theorem: Used in various mathematical proofs and calculations. (x+y)ⁿ = Σ C(n,k) * x^(n-k) * y^k