Math, number theory, and combinatorics · HTML
Multiply independent stages; unordered choice gives C(n,k); overlapping properties use |A∪B|=sum singles-sum intersections+... .
Recognition signals
- Only the number of outcomes is needed
- Objects divide into roles or stages
- Order relevance can be stated clearly
- Duplicate counting needs correction
- Constraints become set selection
False friends
| Signal | Why it is different |
|---|
| Selections have strong state dependence | If one choice changes future options, DP is usually safer than a closed combination formula. |
| Applying permutations to indistinguishable objects | Clarify labels, repetition, and ordering before choosing a formula. |
Core invariant
Every valid outcome maps to one counting representation, or to a known fixed multiplicity that is explicitly corrected.
State, transition, and processing order
| Item | Definition |
|---|
| State | Category sizes, remaining choices, binomial or factorial tables, and inclusion-exclusion subsets. |
| Transition | Multiply independent stages, add disjoint cases, and alternate signs over intersections when cases overlap. |
| Frontier / order | Processed categories are compressed to a count; unprocessed categories affect only remaining parameters. |
Python skeleton
def binomial_table(n):
c = [[0]*(n+1) for _ in range(n+1)]
for i in range(n+1):
c[i][0] = c[i][i] = 1
for k in range(1, i):
c[i][k] = c[i-1][k-1] + c[i-1][k]
return c
def inclusion_exclusion(universe_size, bad_intersections):
# map nonempty subset mask -> size of intersection of those bad sets
good = universe_size
for mask, size in bad_intersections.items():
bits = mask.bit_count()
good += (-1 if bits % 2 else 1) * size
return good
Correctness sketch
- Pascal recurrence partitions choices by whether one designated object is selected.
- The product rule bijects each outcome with one tuple of stage choices.
- In inclusion-exclusion, an object in k bad sets has total bad-union contribution one after alternating binomial terms.
- An object in no bad set retains only its initial good contribution.
Complexity
| Time | Space | Parameters |
|---|
| O(n²) for a binomial table; O(2^k) for k-property inclusion-exclusion | O(n²), reducible to O(n) for one row | n object scale and k inclusion-exclusion properties |
Edge cases
- C(n,0)=C(n,n)=1
- C(n,k)=0 outside 0<=k<=n
- An empty product is one
- Decide whether order matters
- Division modulo M needs an inverse
Error patterns
| Pattern | Why it fails / fix |
|---|
| Confusing permutations and combinations | Ask whether swapping selected objects creates a new outcome. |
| Adding overlapping cases directly | Shared outcomes are counted repeatedly without inclusion-exclusion. |
| Ordinary division under a modulus | Modular division requires an existing inverse. |
Selection and exclusion rules
- Count-only with independent structure: start with sum/product rules.
- Unordered subsets use combinations; ordered arrangements use permutations.
- Few overlapping properties: inclusion-exclusion.
- Choices alter future state: dynamic programming.
Original micro-example
| Part | Detail |
|---|
| Result | C(5,2)×3=30 outcomes. |
| Scenario | Choose two unordered teas from five, then one cup from three. |
| Walkthrough | Tea order adds no outcome; cup choice is independent, so stage counts multiply. |
Recall prompts
My notes