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 |
Sample practice problem
From the free practice sample - 77 guided problems cover this topic in interactive practice.
A restaurant offers 3 appetizers and 5 main courses. How many different meals (one appetizer + one main course) are possible?
- 8
- 15
- 2
- 35
Show answer
Answer: 15
By the product rule, the number of meals = 3 × 5 = 15. Each of the 3 appetizers can be combined with each of the 5 main courses.