Counting & Combinatorics
Reference · Always free
Learn systematic counting techniques: the sum and product rules, permutations, combinations, the pigeonhole principle, and recurrence relations.
Concepts in this topic
- Counting Principles — Master the sum rule, product rule, and other fundamental counting techniques
- Permutations & Combinations — Count ordered and unordered selections from a set
- Pigeonhole Principle — Prove existence results using the pigeonhole principle
- Recurrence Relations — Define sequences recursively and solve recurrence relations
Key formulas & identities
| Name | Formula | Meaning |
|---|---|---|
| Permutation Formula | P(n, r) = n! / (n - r)! | Number of ways to arrange r items chosen from n distinct items (order matters) |
| Combination Formula | C(n, r) = n! / (r! × (n - r)!) | Number of ways to choose r items from n items without regard to order |
| Binomial Theorem | (x + y)ⁿ = ∑ₖ₌₀ⁿ C(n,k) × xⁿ⁻ᵏ × yᵏ | Expansion of a binomial raised to a positive integer power |
| Stars and Bars | C(n + r - 1, r - 1) | Number of ways to distribute n identical objects into r distinct bins |
| Pigeonhole Principle | N objects in k boxes ⟹ at least one box has ⌈N/k⌉ objects | If more objects than categories, some category must contain multiple objects |
| Inclusion-Exclusion (Three Sets) | |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C| | Counting the union of three sets by alternately adding and subtracting intersections |
| Permutations with Repetition | n! / (n₁! × n₂! × ... × nₖ!) | Arrangements of n objects where nᵢ are identical of type i |
| Sum Rule | |A ∪ B| = |A| + |B| when A ∩ B = ∅ | If two tasks are mutually exclusive, total ways is the sum of individual ways |