Combinatorics
Counting objects without listing them: binomials, Catalan numbers and inclusion-exclusion.
10 articles~59 min total
0/10
Fundamentals
- Binomial CoefficientsCount subsets with C(n, k): Pascal's triangle, exact big-integer formulas, and O(1) queries modulo a prime with precomputed factorials.6 minIntermediate
- Catalan NumbersThe sequence 1, 1, 2, 5, 14, 42, … that counts balanced brackets, binary trees, paths under a diagonal and many more objects.6 minIntermediate
- Power of a Divisor in a FactorialFind the largest x such that k^x divides n!, using Legendre's formula for primes and the prime factorization of k for composites.4 minIntermediate
Techniques
- The Inclusion-Exclusion PrincipleCount the elements of a union by alternately adding and subtracting intersections; derangements, coprime counts and multiples in a range.7 minAdvanced
- Stars and BarsCount the ways to distribute identical items into distinct boxes, with lower and upper bounds.4 minIntermediate
- Burnside's Lemma and Pólya EnumerationCount objects up to symmetry (necklaces, colorings of a cube or a torus) by averaging the number of fixed colorings over the symmetry group.8 minAdvanced
- Generating All k-CombinationsList all k-subsets of {1..n} in lexicographic order with the next-combination step, and in a Gray-code order where neighbours differ by exchanging one element.6 minIntermediate
Tasks
- Placing Bishops on a ChessboardCount the ways to place k non-attacking bishops on an n×n board with a DP over diagonals, treating the two square colors independently.4 minIntermediate
- Balanced Bracket SequencesValidate, count, enumerate, rank and unrank balanced bracket sequences, with one or several types of brackets.9 minAdvanced
- Counting Labeled GraphsCount all labeled graphs, the connected ones, and those with exactly k components, by the standard 'root vertex' recurrences.5 minIntermediate