Counting and Combinatorics

Counting Foundations

Combinatorics answers "how many ways?" for passwords, committees, and outcomes. Two basic rules build everything:

Common pitfall: Mixing up sum and product rules. Remember that "and" multiplies while "or" adds. Reaching for the wrong operation severely inflates or deflates your total count.

Permutations vs Combinations

The vital distinction is order. Rearranging chosen items creates a Permutation ($P(n,k)$) if order matters, but a Combination ($\binom{n}{k}$) if order is irrelevant.

• Permutation: $P(n,k) = \frac{n!}{(n-k)!}$. Counting ordered arrangements like race podiums or passwords.
• Combination: $\binom{n}{k} = \frac{n!}{k!(n-k)!}$. Unordered selections like committees or poker hands.

Common pitfall: Using permutations when order doesn't matter. Combinations divide by $k!$ to remove duplicate orderings.