Combinatorics
How many 5-card poker hands are there? (2,598,960.) How many ways can 10 identical candies go to 3 children if nobody gets more than 4? (6.) How many numbers up to 100 are divisible by 2, 3 or 5? (74.) What is modulo 13? (10, computed from three tiny binomials.) How many different necklaces of 6 beads can you make with black and white beads, if turning the necklace doesn't make it different? (14.)
Each of these questions has an answer far too large, or far too repetitive, to find by listing every possibility. Combinatorics is the craft of counting things without listing them: you find a structure (a product of choices, a bijection, a symmetry, an alternating sum) that turns the count into a formula or a short computation.
This lesson is the formula side of counting. Its sibling, Counting & Combinatorial DP, is the recurrence side: it builds Pascal's triangle, Catalan numbers, partitions, Stirling numbers and derangements with DPs and explains how to avoid double counting in loops. Here we take those same objects and ask: what is the closed form, how do we compute it modulo a prime fast, what do we do when is bigger than the prime (Lucas), how do we count with forbidden things (inclusion–exclusion), and how do we count up to symmetry (Burnside). Where the DP lesson already covers a derivation, we link to it instead of repeating it.
Why this exists
Three groups of people need these tools.
- Programmers answering "how many?" questions in contests and interviews. The answer is usually requested "modulo ", because the true number has thousands of digits. You need in after an precomputation, and you need to know which formula applies.
- Engineers estimating sizes. How many test cases does a pairwise configuration matrix have? How many features does a degree-3 polynomial expansion of 10 inputs produce ()? What is the chance two of 10,000 random IDs collide? Combinatorics is how you get those numbers before you build anything (see System Design Math).
- Anyone reasoning about probability. A probability on a finite, uniform space is (favourable outcomes) ÷ (all outcomes). Both are counts. Probability for Engineers and Probability & Expected Value lean on everything here.
Historically, Pascal's 1654 treatise on the arithmetical triangle and his correspondence with Fermat about gambling started modern combinatorics and probability together. Inclusion–exclusion goes back to de Moivre (1718) and Sylvester. Catalan numbers are named after Eugène Catalan (1838), though Euler and Segner counted polygon triangulations a century earlier. Burnside's lemma (1897) was already known to Cauchy and Frobenius; George Pólya (1937) extended it into a theory for counting chemical isomers.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "choose of ", "subsets of size ", "how many teams" | |
| "arrangements", "orderings", "seat of people in a row" | or |
| "arrange the letters of BANANA" (repeated items) | Multinomial |
| answer "modulo ", many queries, | Factorial and inverse-factorial tables |
| with (huge , small prime ) | Lucas' theorem |
| modulo a composite like or | Prime-power factorials + CRT; or Pascal if is small |
| "balanced brackets", "paths that never cross the diagonal", "binary tree shapes", "triangulations" | Catalan numbers |
| "candidate A always strictly ahead in the count" | Ballot theorem |
| "distribute identical items into boxes" | Stars and bars |
| "…with at most per box" | Stars and bars + inclusion–exclusion |
| "divisible by at least one of", "coprime to", "at least one missing", "none in its place" | Inclusion–exclusion |
| "nobody gets their own", "no fixed points" | Derangements |
| "onto", "every box non-empty", "use every colour" | Surjections |
| "rotations count as the same", "necklace", "up to symmetry" | Burnside's lemma (Pólya for weighted versions) |
| "number of ways to make change", "sum of dice equals " | Generating functions (product of polynomials) |
Intuition & first principles
Two rules: add for "or", multiply for "and then"
The Counting DP lesson explains these in detail; here is the one-paragraph version.
- Rule of sum. If a choice is either one of options or one of different options (no overlap), there are choices.
- Rule of product. If you make one choice in ways and then another in ways (and the second count does not depend on which first choice you made), there are outcomes.
A password of 3 lowercase letters then 2 digits: .
Order matters? Repetition allowed? The four basic counts
Pick items from (say the letters A–E). There are four different questions depending on whether order matters and whether you may pick the same letter twice:
| Order matters (sequences) | Order doesn't matter (sets/multisets) | |
|---|---|---|
| Repetition allowed | (AA, AB, BA, …) | (multisets: AA, AB, …) |
| No repetition | (AB, BA, …) | (AB, AC, …) |
The bottom row is linked by a simple argument: each unordered pair {A, B} corresponds to exactly ordered pairs (AB, BA). So . Dividing by the number of orderings that you want to treat as the same is the oldest trick in counting, and Burnside's lemma (later) is its grown-up version for when not every arrangement has the same number of "duplicates".
The top-right cell (multisets) is stars and bars, which we derive below.
Multinomials. The letters of BANANA (one B, three A, two N) can be arranged in distinct ways: orderings of six labelled letters, divided by the ways to shuffle the A's and ways to shuffle the N's that look identical. MISSISSIPPI gives .
A tiny example you can hold in your head
How many 5-card hands from a 52-card deck? Order doesn't matter, no repetition: .
How many of them are a flush (all five the same suit, including straight flushes)? Choose the suit (4 ways), and then choose 5 of its 13 cards (): . Probability .
Two lines, no enumeration. That is the whole game: break the object into a sequence of independent choices, or show it is in one-to-one correspondence (a bijection) with something you already know how to count.
Mechanics
1. Binomial coefficients modulo a prime: factorial tables
. Modulo a prime , division means multiplying by a modular inverse (see Modular Arithmetic). By Fermat's little theorem, for .
The standard precomputation for all (with ):
fact[0] = 1,fact[i] = fact[i-1] * i mod p. multiplications.inv_fact[N-1] = fact[N-1]^(p-2) mod p. One exponentiation, .- Walk down:
inv_fact[i-1] = inv_fact[i] * i mod p, because . multiplications.
Then , in .
Trace with , :
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
fact[i] = | 1 | 1 | 2 | 6 | 11 | 3 | 5 | 9 | 7 | 11 | 6 |
inv_fact[i] | 1 | 1 | 7 | 11 | 6 | 9 | 8 | 3 | 2 | 6 | 11 |
Check one: fact[3] * inv_fact[3] . ✓ Then , and indeed .
With and , the tables take two arrays of integers and a few milliseconds. Results computed by the code below: and .
The tables break when
, so for fact[n] is 0 and the formula returns 0 even when the true binomial is not divisible by . Example: , yet fact[26] . With this never bites ( is far smaller). With a small prime, or a huge , use Lucas' theorem.
Pascal's rule builds the same numbers by addition only. It needs no inverses, so it works modulo any number, including composites, but costs time and memory. The Counting DP lesson builds it and compares the two methods. A few identities worth knowing, each checked numerically in this lesson's scripts:
| Identity | Meaning | Check |
|---|---|---|
| choosing who is in = choosing who is out | ||
| every subset has some size | row 10 sums to 1024 | |
| (Vandermonde) | choose from two groups | |
| (hockey stick) | split by the largest chosen element |
2. Lucas' theorem: for huge
Statement. Write and in base : , . Then
with the convention when . Each factor has , so the factorial tables of size handle them.
Example. . In base 13: , digits ; , digits .
| Digit position | |||
|---|---|---|---|
| 12 | 1 | 12 | |
| 11 | 10 | 11 | |
| 5 | 1 | 5 |
Product . So , which Python's exact math.comb(1000, 300) % 13 confirms. The exact number has 264 digits.
A zero example. : , . The middle digit has , so the product is 0: . ✓ With huge , zeros are the norm: is divisible by 7, 11, 13, 17, 1009, 10007 and 1000003. A non-zero large example the code checks: .
Proof idea. In polynomials with coefficients mod , , because every middle coefficient () has a factor in the numerator and none in the denominator. Repeating, . Now
The coefficient of on the left is . On the right, since base- representations are unique, the only way to build is to take from the -th factor, which has coefficient . Multiply them. ∎
graph LR
A["(1+x)^n"] --> B["split n into base-p digits"]
B --> C["product over i of (1+x^(p^i))^(n_i)"]
C --> D["coefficient of x^k: one term per digit"]
D --> E["product of C(n_i, k_i)"]
The special case. is odd exactly when every binary digit of is the matching digit of , that is, (k & n) == k. Row of Pascal's triangle has odd entries; row 10 () has 4. Colour the odd entries of Pascal's triangle and you get the Sierpiński triangle. (See Bit Manipulation for the submask idea.)
Kummer's theorem (1852) is the companion fact: the exponent of in equals the number of carries when adding and in base . For : in base 3, and ; adding them carries once, so exactly one factor of 3. ✓
3. modulo a composite
When the modulus is not prime (say or ), inverses of many factorials do not exist. Options, from simplest:
- Pascal's triangle mod if a few thousand. Additions only.
- Prime factor the denominator away. For one query with moderate : factor all of over primes up to (Legendre's formula ), subtract exponents, and multiply the remaining prime powers mod . per query, no division at all.
- CRT over prime powers. Write , compute for each with the generalized Lucas method of Granville (1997) (factorials with the -parts stripped, plus Kummer's count of carries), and combine with the Chinese remainder theorem. This handles up to and is what the Library Checker "Binomial Coefficient" problem expects.
We only mention method 3 here; cp-algorithms ("Binomial coefficients", section "Mod prime powers") has a full write-up.
4. Catalan numbers: the reflection argument
The Counting DP lesson derives the Catalan recurrence by splitting a bracket string at the partner of its first bracket. Here is the closed form, with a classic bijective proof.
: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796.
Paths, not brackets. Turn each ( into an up-step and each ) into a down-step . A string of open and close brackets is a lattice path from to . It is balanced exactly when the path never goes below height 0 (a Dyck path). There are paths in total (choose which of the steps go up). We count the bad ones, which touch height .
The reflection trick (usually credited to Désiré André, 1887, although his original argument was a different bijection; the reflection form appears in the 1920s). Take a bad path. Find the first step where it touches . Reflect everything after that point (swap up and down steps). The original path ended at height 0; after the reflection point it had to climb from to , a net , and the reflected part now goes from to . So the new path ends at height : it has up-steps and down-steps.
Conversely, any path with downs and ups ends at , so it must touch ; reflecting after its first touch gives back a bad path ending at 0. The two operations undo each other: a bijection between bad paths and paths with down-steps. There are of those.
For : . For : .
graph LR
A["bad path: (0,0) to (2n,0), touches -1"] -->|"reflect after first touch of -1"| B["path from (0,0) to (2n,-2)"]
B -->|"reflect after first touch of -1"| A
B --> C["n-1 ups, n+1 downs: C(2n, n+1) of them"]
The algebra gives the second form, which is what you compute: modulo , .
Things counted by (each a bijection with Dyck paths): balanced bracket strings with pairs; binary trees with nodes (and BSTs on keys); full binary trees with leaves; ways to parenthesize a product of factors; triangulations of a convex -gon; non-crossing ways to pair up points on a circle; monotone paths in an grid that stay on or below the diagonal; permutations of sortable by one stack. Stanley's Catalan Numbers (2015) lists 214 families.
The ballot theorem (Bertrand, 1887). In an election, A gets votes and B gets . The votes are counted in a uniformly random order. The probability that A is strictly ahead throughout the count is . Same reflection idea: the bad orders (where they are tied at some point) are in bijection, by reflecting the part before the first tie, with orders that start with a B-vote; and every order starting with B is bad. So bad , and good . Brute force agrees: : 2 good orders of 10 (); : 14 of 56 ().
5. Stars and bars
Question. In how many ways can identical items go into distinct boxes? Equivalently, how many solutions does have in non-negative integers?
Picture. Write the items as stars and separate the boxes with bars. For , , the solution is
★★★|★★★★★|★★
Every arrangement of stars and bars in a row is one solution, and every solution is one arrangement. A row of symbols, of which we choose which are bars:
For , : .
Each box at least one (): give one item to each box first, then distribute the remaining freely: . For , : . More generally, a lower bound is handled by pre-placing items.
Upper bounds need inclusion–exclusion. Count solutions of with every . Let "bad event " be . If a set of variables is forced to be , pre-place items: solutions (0 if ). Inclusion–exclusion (next section):
Brute force over all triples finds the same 6: the permutations of and , three each.
Multisets. "Choose items from types with repetition" is stars and bars with boxes (types) and items: . That fills the last cell of the four-counts table: 15 multisets of size 2 from 5 letters. It is also why a degree- polynomial in variables has monomials (add a dummy variable for "unused degree"): 286 for , , the size of scikit-learn's PolynomialFeatures(degree=3) output for 10 inputs.
6. Inclusion–exclusion
The two-set version everyone knows: , because elements in both were counted twice. For three sets:
General form. For sets :
Usually we want the complement, "in none of the sets" (no bad event happens):
with = everything. The art is choosing the bad events so that is easy to count, typically because forcing a set of bad events leaves a free, symmetric problem.
graph TD
A["count objects avoiding all bad events"] --> B["define bad events A_1..A_m"]
B --> C["N(S): objects where every event in S happens"]
C --> D["sum over subsets S of (-1)^|S| N(S)"]
D --> E["prune: if N(S) = 0, all supersets are 0 too"]
Why the signs work. Take an object that lies in exactly of the sets. It is counted in for every inside those , so its total weight is . An object in none of the sets is counted only in , with weight 1. So the sum counts exactly the good objects. ∎ (This is the same identity that makes in Number Theory II.)
Example 1: divisible by at least one of 2, 3, 5, up to 100. and the intersection of "divisible by " and "divisible by " is "divisible by ".
| Subset | lcm | Sign | Running total | |
|---|---|---|---|---|
| {2} | 2 | 50 | + | 50 |
| {3} | 3 | 33 | + | 83 |
| {5} | 5 | 20 | + | 103 |
| {2, 3} | 6 | 16 | − | 87 |
| {2, 5} | 10 | 10 | − | 77 |
| {3, 5} | 15 | 6 | − | 71 |
| {2, 3, 5} | 30 | 3 | + | 74 |
So 74 numbers in are divisible by 2, 3 or 5, and are coprime to 30. Up to 1000 the counts are 734 and 266.
Use lcm, not product. For divisors , the pair means "divisible by 12", not 24. The correct count up to 100 is 36; multiplying instead of taking the lcm gives a wrong answer.
Example 2: derangements. Let = permutations of that fix . Forcing a set of fixed points leaves permutations of the rest, and there are such sets:
For : .
Example 3: surjections. How many functions from a 5-element set onto a 3-element set (every output used)? Bad event : output is missed. Forcing outputs to be missed leaves functions:
In general, surjections from onto number , where is a Stirling number of the second kind: . Brute force over all functions agrees.
Example 4: coprime counting, . Numbers in coprime to avoid "divisible by " for each prime . Inclusion–exclusion over the primes gives ; for : .
Bonferroni inequalities. Stopping the alternating sum early gives alternately upper and lower bounds. For derangements of 4: partial sums bracket the answer 9 ever more tightly. Useful when is too large for terms but you only need an estimate (for example, union bounds in probability).
The cost and the prune
Inclusion–exclusion over events has terms. For divisibility, prune: once the lcm exceeds , every superset contributes , so skip the whole branch. With the first 10 primes and all subsets are live (their product is about ); the count of numbers divisible by at least one of them is . With 20 primes and , most of the branches die early.
7. Derangements
A derangement is a permutation with no fixed point. From the inclusion–exclusion formula above, and the recurrence derived in the Counting DP lesson:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 2 | 9 | 44 | 265 | 1854 | 14833 | 133496 | 1334961 |
There is also the one-term recurrence , which falls out of the alternating-sum formula. The fraction tends to very fast: for a Secret Santa draw among any reasonable number of people, about 37% of uniformly random draws have nobody drawing themselves.
Partial derangements (exactly fixed points) number : choose the fixed points, derange the rest.
8. Stirling numbers in one table
Both kinds count ways to break labelled items into non-empty groups; the Counting DP lesson builds them with recurrences.
| Second kind | First kind (unsigned) | |
|---|---|---|
| Counts | partitions of items into non-empty sets | permutations of items with cycles |
| Recurrence | ||
| Closed form | (surjections ÷ ) | none simple; coefficients of |
| Row , | 1, 15, 25, 10, 1 (sum: Bell number 52) | 24, 50, 35, 10, 1 (sum: ) |
The closed form for is just Example 3 above divided by , since a surjection is an ordered partition into labelled blocks. This is the "twelvefold way" connection: balls into boxes with labelled/unlabelled balls and boxes, with "any", "at most one" or "at least one" per box, gives twelve problems whose answers are , falling factorials, binomials, stars and bars, Stirling numbers, and partition numbers (Stanley, Enumerative Combinatorics, Vol. 1, §1.9).
9. Burnside's lemma: counting up to symmetry
The problem. A necklace has beads, each black or white. Two colourings that differ only by rotating the necklace are the same necklace. How many different necklaces are there?
There are colourings. Dividing by 6 rotations gives , not an integer, because some colourings look the same after a rotation (all-white is unchanged by every rotation; it is not "6 copies" of itself). We need to count orbits: groups of colourings that can be turned into each other.
Burnside's lemma. Let a finite group of symmetries act on a set of objects. Then
where is the set of objects left unchanged by symmetry . In words: the number of distinct objects is the average number of objects each symmetry fixes.
Fixed colourings of a rotation. Rotating by positions splits the positions into cycles, each of length . A colouring is unchanged exactly when every cycle is a single colour. So rotation by fixes colourings.
| Rotation | Cycles | Fixed colourings | |
|---|---|---|---|
| 0 (identity) | 6 | 6 cycles of length 1 | 64 |
| 1 | 1 | 1 cycle of length 6 | 2 |
| 2 | 2 | 2 cycles of length 3 | 4 |
| 3 | 3 | 3 cycles of length 2 | 8 |
| 4 | 2 | 2 cycles of length 3 | 4 |
| 5 | 1 | 1 cycle of length 6 | 2 |
| Sum | 84 |
Necklaces . A brute-force program that lists all 64 colourings and merges rotations finds the same 14. The general formula:
where the second form groups rotations by their gcd (there are rotations with ). Verified by brute force: , , , .
graph TD
A["set X of colourings, group G of symmetries"] --> B["for each symmetry g: count colourings it fixes"]
B --> C["rotation by i: gcd(i,n) cycles, k^gcd fixed"]
C --> D["average over G = number of orbits"]
Bracelets (rotations and flips). The group now has elements. For even , flips pass through two opposite beads (fixing colourings) and pass between beads (fixing ). For , : . One pair of necklaces is merged by flipping: the two "chiral" colourings, which are mirror images of each other.
Why it works (proof sketch). Count pairs with in two ways. By : . By : , where the stabilizer is the set of symmetries fixing . The orbit–stabilizer theorem says . So each orbit contributes . Total . ∎
Pólya's enumeration (one paragraph). Burnside counts all colourings up to symmetry. Pólya's theorem (1937) keeps track of how many of each colour: replace by , where is the cycle length, and read off coefficients. Example: necklaces of 6 beads with exactly 3 black. Identity: . Rotations by 2 or 4 (two 3-cycles): choose which cycle is black, 2 each. Rotation by 3 (three 2-cycles): impossible to get an odd number of black, 0. Rotations by 1 or 5: 0. Total , which brute force confirms. Pólya originally used this to count chemical isomers (how many distinct molecules arise from substituting atoms on a symmetric skeleton).
10. Generating functions: counting by multiplying polynomials
A generating function stores a sequence as the coefficients of a power series . The point: operations on counting problems become algebra on polynomials.
- Choices that add up. One die is . Two dice: square it. The coefficient of is the number of ways to roll sum : for . Multiplying polynomials is the rule of product applied to every pair of terms at once.
- Making change. With coins 1, 2, 5 (unlimited), the number of ways to pay is the coefficient of in , since means "use coin any number of times". For : 10 ways. Expanding this product one factor at a time is exactly the coin-change DP of Knapsack.
- Binomials. : each of items is "out" () or "in" (). Vandermonde's identity is , read coefficient by coefficient.
- Catalan, solved. The recurrence says . Solve the quadratic: , and expanding the square root with Newton's binomial series gives .
- Exponential generating functions handle labelled objects: derangements have EGF , set partitions .
Multiplying two polynomials of degree naively costs . FFT and NTT do it in , which is how serious generating-function computations are done; see FFT & NTT. Wilf's generatingfunctionology is the friendly book-length introduction.
The ladder: brute force → better → optimal
Computing
| Rung | Method | Precompute | Per query | When it fits |
|---|---|---|---|---|
| 1 | Enumerate all -subsets | — | never, except to test | |
| 2 | Recursion without memo | — | exponential | never |
| 3 | Pascal's triangle | time and memory | , any modulus (even composite) | |
| 4 | Multiplicative formula with inverses | — | a few queries, prime | |
| 5 | Factorial + inverse-factorial tables | many queries, (the standard) | ||
| 6 | Lucas on top of tables of size | small prime , huge | ||
| 7 | Granville's prime-power Lucas + CRT | per prime power | composite modulus, huge |
Each step either removes repeated work (2 → 3), removes the quadratic table (3 → 5, using inverses), or removes the limit (5 → 6 → 7).
Counting numbers divisible by at least one of given divisors
| Rung | Method | Time | Limit |
|---|---|---|---|
| 1 | Test every against every divisor | ||
| 2 | Inclusion–exclusion over all subsets | , any | |
| 3 | DFS over subsets with lcm pruning | larger when divisors are big | |
| 4 | Möbius-style dedup (merge divisors that divide each other first) | same, fewer terms | duplicates or nested divisors |
Counting necklaces
| Rung | Method | Time |
|---|---|---|
| 1 | List all colourings, canonicalize each by trying all rotations, count distinct | |
| 2 | Burnside, one term per rotation | with fast powers |
| 3 | Burnside grouped by divisor: |
Correctness
Factorial tables. fact[i] by induction. Since is prime and , , so it is invertible; Fermat gives inv_fact[N-1], and inv_fact[i-1] by induction downward. The binomial formula then holds in the field because it holds over the integers and reduction mod is a ring homomorphism.
Lucas. Proved above via in and uniqueness of base- digits.
Stars and bars. The map "solution star/bar string" is a bijection: the string determines each as the number of stars between consecutive bars, and each solution determines a unique string.
Inclusion–exclusion. Proved above: each object's total weight is , which is 1 for and 0 otherwise.
Catalan via reflection. The reflection map is an involution between "paths to touching " and "paths to " (every path of the second kind touches by the discrete intermediate value property: heights change by 1 per step). So the bad count is .
Burnside. Double counting of fixed pairs plus orbit–stabilizer, as above. For necklaces, rotation by is the permutation , whose cycles are the cosets of the subgroup generated by in ; that subgroup has elements, so there are cycles.
Complexity
| Task | Time | Space |
|---|---|---|
| Factorial tables up to | ||
| One from tables | — | |
| Lucas query | with tables of size | |
| Pascal's triangle up to | , or for one row | |
| Catalan | after tables | |
| Inclusion–exclusion, events | recursion | |
| Burnside necklaces | (or by divisors) | |
| Stars and bars count | one binomial | — |
| Generating-function product, degree | naive, with NTT |
Integer sizes. overflows signed 64-bit at ; is the largest factorial that fits; JavaScript Number is exact only up to , so products of two residues modulo (up to ) need BigInt or a split multiplication.
Implementation
Three groups: binomials modulo a prime with factorial tables and Lucas; inclusion–exclusion for "divisible by at least one"; and Burnside necklace and bracelet counts checked by brute force. Each block asserts the numbers used in this lesson.
: factorial tables and Lucas' theorem
from math import comb
MOD = 1_000_000_007
class Binomial:
"""C(n, k) mod prime p for 0 <= n < size, where size <= p."""
def __init__(self, size: int, p: int = MOD):
assert size <= p, "tables would contain p! = 0"
self.p = p
self.fact = [1] * size
for i in range(1, size):
self.fact[i] = self.fact[i - 1] * i % p
self.inv_fact = [1] * size
self.inv_fact[-1] = pow(self.fact[-1], p - 2, p) # Fermat inverse
for i in range(size - 1, 0, -1):
self.inv_fact[i - 1] = self.inv_fact[i] * i % p
def C(self, n: int, k: int) -> int:
if k < 0 or k > n:
return 0
return self.fact[n] * self.inv_fact[k] % self.p * self.inv_fact[n - k] % self.p
def lucas(n: int, k: int, small: Binomial) -> int:
"""C(n, k) mod small.p for any n, k >= 0, using tables of size p."""
p, res = small.p, 1
while n or k:
ni, ki = n % p, k % p # current base-p digits
if ki > ni:
return 0
res = res * small.C(ni, ki) % p
n //= p
k //= p
return res
if __name__ == "__main__":
big = Binomial(1_000_001)
assert big.C(5, 2) == 10 and big.C(52, 5) == 2_598_960
assert big.C(100_000, 50_000) == 149_033_233
assert big.C(1_000_000, 300_000) == 699_299_087
catalan = big.C(200_000, 100_000) * pow(100_001, MOD - 2, MOD) % MOD
assert catalan == 945_729_344
assert [big.C(2 * n, n) * pow(n + 1, MOD - 2, MOD) % MOD for n in range(8)] == [
1, 1, 2, 5, 14, 42, 132, 429]
assert Binomial(200_001, 998_244_353).C(200_000, 100_000) == 935_629_711
t13 = Binomial(13, 13)
assert t13.fact[:11] == [1, 1, 2, 6, 11, 3, 5, 9, 7, 11, 6]
assert t13.C(10, 3) == 3
assert lucas(1000, 300, t13) == 10 == comb(1000, 300) % 13
assert lucas(26, 13, t13) == 2 # the naive table would say 0
assert lucas(10, 3, Binomial(3, 3)) == 0
assert lucas(10**18, 123_456, Binomial(1_000_003, 1_000_003)) == 245_611
for p in (2, 3, 5, 7, 13): # Lucas vs Pascal's triangle mod p
t = Binomial(p, p)
row = [1]
for n in range(300):
assert all(lucas(n, k, t) == row[k] for k in range(n + 1))
row = [1] + [(row[i] + row[i + 1]) % p for i in range(n)] + [1]
print("binomials and Lucas: all checks passed")
public class Main {
static final long MOD = 1_000_000_007L;
/** C(n, k) mod prime p for 0 <= n < size, size <= p. */
static final class Binomial {
final long p;
final long[] fact, invFact;
Binomial(int size, long p) {
if (size > p) throw new IllegalArgumentException("tables would contain p! = 0");
this.p = p;
fact = new long[size];
invFact = new long[size];
fact[0] = 1;
for (int i = 1; i < size; i++) fact[i] = fact[i - 1] * i % p;
invFact[size - 1] = powMod(fact[size - 1], p - 2, p);
for (int i = size - 1; i > 0; i--) invFact[i - 1] = invFact[i] * i % p;
}
long C(long n, long k) {
if (k < 0 || k > n) return 0;
return fact[(int) n] * invFact[(int) k] % p * invFact[(int) (n - k)] % p;
}
}
static long powMod(long a, long e, long m) {
long r = 1;
a %= m;
for (; e > 0; e >>= 1, a = a * a % m) if ((e & 1) == 1) r = r * a % m;
return r;
}
static long lucas(long n, long k, Binomial small) {
long p = small.p, res = 1;
while (n > 0 || k > 0) {
long ni = n % p, ki = k % p;
if (ki > ni) return 0;
res = res * small.C(ni, ki) % p;
n /= p;
k /= p;
}
return res;
}
static void check(boolean cond, String msg) { if (!cond) throw new AssertionError(msg); }
public static void main(String[] args) {
Binomial big = new Binomial(1_000_001, MOD);
check(big.C(5, 2) == 10 && big.C(52, 5) == 2_598_960, "small");
check(big.C(100_000, 50_000) == 149_033_233, "C(1e5, 5e4)");
check(big.C(1_000_000, 300_000) == 699_299_087, "C(1e6, 3e5)");
long catalan = big.C(200_000, 100_000) * powMod(100_001, MOD - 2, MOD) % MOD;
check(catalan == 945_729_344, "Catalan(1e5)");
check(new Binomial(200_001, 998_244_353L).C(200_000, 100_000) == 935_629_711, "998244353");
Binomial t13 = new Binomial(13, 13);
check(t13.C(10, 3) == 3, "C(10,3) mod 13");
check(lucas(1000, 300, t13) == 10, "Lucas 1000 300");
check(lucas(26, 13, t13) == 2, "Lucas 26 13");
check(lucas(10, 3, new Binomial(3, 3)) == 0, "Lucas zero");
check(lucas(1_000_000_000_000_000_000L, 123_456, new Binomial(1_000_003, 1_000_003)) == 245_611,
"Lucas huge");
for (int p : new int[] {2, 3, 5, 7, 13}) {
Binomial t = new Binomial(p, p);
long[] row = {1};
for (int n = 0; n < 300; n++) {
for (int k = 0; k <= n; k++) check(lucas(n, k, t) == row[k], "pascal " + n + " " + k);
long[] next = new long[n + 2];
next[0] = next[n + 1] = 1;
for (int i = 0; i < n; i++) next[i + 1] = (row[i] + row[i + 1]) % p;
row = next;
}
}
System.out.println("binomials and Lucas: all checks passed");
}
}
#include <cassert>
#include <cstdint>
#include <iostream>
#include <stdexcept>
#include <vector>
using i64 = long long;
const i64 MOD = 1000000007;
i64 pow_mod(i64 a, i64 e, i64 m) {
i64 r = 1;
a %= m;
for (; e > 0; e >>= 1, a = a * a % m)
if (e & 1) r = r * a % m;
return r;
}
// C(n, k) mod prime p for 0 <= n < size, size <= p.
struct Binomial {
i64 p;
std::vector<i64> fact, inv_fact;
Binomial(int size, i64 p_) : p(p_), fact(size), inv_fact(size) {
if (size > p) throw std::invalid_argument("tables would contain p! = 0");
fact[0] = 1;
for (int i = 1; i < size; ++i) fact[i] = fact[i - 1] * i % p;
inv_fact[size - 1] = pow_mod(fact[size - 1], p - 2, p);
for (int i = size - 1; i > 0; --i) inv_fact[i - 1] = inv_fact[i] * i % p;
}
i64 C(i64 n, i64 k) const {
if (k < 0 || k > n) return 0;
return fact[n] * inv_fact[k] % p * inv_fact[n - k] % p;
}
};
i64 lucas(i64 n, i64 k, const Binomial& small) {
i64 p = small.p, res = 1;
while (n > 0 || k > 0) {
i64 ni = n % p, ki = k % p;
if (ki > ni) return 0;
res = res * small.C(ni, ki) % p;
n /= p;
k /= p;
}
return res;
}
int main() {
Binomial big(1000001, MOD);
assert(big.C(5, 2) == 10 && big.C(52, 5) == 2598960);
assert(big.C(100000, 50000) == 149033233);
assert(big.C(1000000, 300000) == 699299087);
assert(big.C(200000, 100000) * pow_mod(100001, MOD - 2, MOD) % MOD == 945729344);
assert(Binomial(200001, 998244353).C(200000, 100000) == 935629711);
Binomial t13(13, 13);
assert(t13.C(10, 3) == 3);
assert(lucas(1000, 300, t13) == 10);
assert(lucas(26, 13, t13) == 2);
assert(lucas(10, 3, Binomial(3, 3)) == 0);
assert(lucas(1000000000000000000LL, 123456, Binomial(1000003, 1000003)) == 245611);
for (int p : {2, 3, 5, 7, 13}) {
Binomial t(p, p);
std::vector<i64> row = {1};
for (int n = 0; n < 300; ++n) {
for (int k = 0; k <= n; ++k) assert(lucas(n, k, t) == row[k]);
std::vector<i64> next(n + 2, 1);
for (int i = 0; i < n; ++i) next[i + 1] = (row[i] + row[i + 1]) % p;
row = next;
}
}
std::cout << "binomials and Lucas: all checks passed\n";
}
// Residues mod ~1e9 multiply to ~1e18 > 2^53, so products go through BigInt.
const mulMod = (a: number, b: number, m: number): number =>
Number((BigInt(a) * BigInt(b)) % BigInt(m));
function powMod(a: number, e: number, m: number): number {
let r = 1;
a %= m;
for (; e > 0; e = Math.floor(e / 2), a = mulMod(a, a, m)) if (e % 2 === 1) r = mulMod(r, a, m);
return r;
}
/** C(n, k) mod prime p for 0 <= n < size, size <= p. */
class Binomial {
readonly p: number;
readonly fact: number[];
readonly invFact: number[];
constructor(size: number, p: number) {
if (size > p) throw new Error("tables would contain p! = 0");
this.p = p;
this.fact = new Array<number>(size);
this.invFact = new Array<number>(size);
this.fact[0] = 1;
for (let i = 1; i < size; i++) this.fact[i] = mulMod(this.fact[i - 1], i, p);
this.invFact[size - 1] = powMod(this.fact[size - 1], p - 2, p);
for (let i = size - 1; i > 0; i--) this.invFact[i - 1] = mulMod(this.invFact[i], i, p);
}
C(n: number, k: number): number {
if (k < 0 || k > n) return 0;
return mulMod(mulMod(this.fact[n], this.invFact[k], this.p), this.invFact[n - k], this.p);
}
}
/** n and k may exceed 2^53, so they are BigInt; digits are small numbers. */
function lucas(n: bigint, k: bigint, small: Binomial): number {
const p = BigInt(small.p);
let res = 1;
while (n > 0n || k > 0n) {
const ni = Number(n % p), ki = Number(k % p);
if (ki > ni) return 0;
res = mulMod(res, small.C(ni, ki), small.p);
n /= p;
k /= p;
}
return res;
}
function assert(cond: boolean, msg: string): void { if (!cond) throw new Error(msg); }
const MOD = 1_000_000_007;
const big = new Binomial(1_000_001, MOD);
assert(big.C(5, 2) === 10 && big.C(52, 5) === 2_598_960, "small");
assert(big.C(100_000, 50_000) === 149_033_233, "C(1e5, 5e4)");
assert(big.C(1_000_000, 300_000) === 699_299_087, "C(1e6, 3e5)");
assert(mulMod(big.C(200_000, 100_000), powMod(100_001, MOD - 2, MOD), MOD) === 945_729_344, "Catalan");
assert(new Binomial(200_001, 998_244_353).C(200_000, 100_000) === 935_629_711, "998244353");
const t13 = new Binomial(13, 13);
assert(t13.C(10, 3) === 3, "C(10,3) mod 13");
assert(lucas(1000n, 300n, t13) === 10, "Lucas 1000 300");
assert(lucas(26n, 13n, t13) === 2, "Lucas 26 13");
assert(lucas(10n, 3n, new Binomial(3, 3)) === 0, "Lucas zero");
assert(lucas(10n ** 18n, 123_456n, new Binomial(1_000_003, 1_000_003)) === 245_611, "Lucas huge");
for (const p of [2, 3, 5, 7, 13]) {
const t = new Binomial(p, p);
let row = [1];
for (let n = 0; n < 300; n++) {
for (let k = 0; k <= n; k++) assert(lucas(BigInt(n), BigInt(k), t) === row[k], `pascal ${n} ${k}`);
const next = new Array<number>(n + 2).fill(1);
for (let i = 0; i < n; i++) next[i + 1] = (row[i] + row[i + 1]) % p;
row = next;
}
}
console.log("binomials and Lucas: all checks passed");
Inclusion–exclusion: numbers divisible by at least one divisor
import random
from math import gcd
def count_divisible_by_any(n: int, divisors: list[int]) -> int:
"""How many x in [1, n] are divisible by at least one of the divisors."""
ds = sorted(set(divisors))
total = 0
def go(start: int, l: int, size: int) -> None:
nonlocal total
for i in range(start, len(ds)):
g = gcd(l, ds[i])
if l // g > n // ds[i]: # lcm would exceed n: this term and all
continue # supersets contribute floor(n/lcm) = 0
nl = l // g * ds[i]
# the subset grows to size + 1: '+' for odd sizes, '-' for even
total += n // nl if size % 2 == 0 else -(n // nl)
go(i + 1, nl, size + 1)
go(0, 1, 0)
return total
def count_coprime(n: int, m: int) -> int:
"""How many x in [1, n] have gcd(x, m) == 1."""
primes, d = [], 2
while d * d <= m:
if m % d == 0:
primes.append(d)
while m % d == 0:
m //= d
d += 1
if m > 1:
primes.append(m)
return n - count_divisible_by_any(n, primes)
if __name__ == "__main__":
assert count_divisible_by_any(100, [2, 3, 5]) == 74
assert count_divisible_by_any(100, [4, 6, 10]) == 36 # lcm, not product
assert count_divisible_by_any(1000, [2, 3, 5]) == 734
assert count_divisible_by_any(100, [1, 7]) == 100
assert count_divisible_by_any(0, [2]) == 0
assert count_coprime(100, 30) == 26 and count_coprime(1000, 30) == 266
assert count_coprime(36, 36) == 12 # phi(36)
first10 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
assert count_divisible_by_any(10**18, first10) == 842_052_776_898_047_765
assert count_divisible_by_any(10**18, [10**18, 10**18 - 1]) == 2
rng = random.Random(7)
for _ in range(300):
n = rng.randrange(0, 3000)
ds = [rng.randrange(1, 60) for _ in range(rng.randrange(1, 7))]
assert count_divisible_by_any(n, ds) == sum(
1 for x in range(1, n + 1) if any(x % d == 0 for d in ds))
print("inclusion-exclusion: all checks passed")
import java.util.Arrays;
import java.util.Random;
public class Main {
static long gcd(long a, long b) { while (b != 0) { long t = a % b; a = b; b = t; } return a; }
static long n;
static long[] ds;
static long total;
static void go(int start, long l, int size) {
for (int i = start; i < ds.length; i++) {
long g = gcd(l, ds[i]);
if (l / g > n / ds[i]) continue; // lcm > n: term and supersets are 0
long nl = l / g * ds[i]; // cannot overflow: nl <= n
total += (size % 2 == 0) ? n / nl : -(n / nl);
go(i + 1, nl, size + 1);
}
}
/** How many x in [1, limit] are divisible by at least one of the divisors (all >= 1). */
static long countDivisibleByAny(long limit, long[] divisors) {
n = limit;
ds = Arrays.stream(divisors).distinct().sorted().toArray();
total = 0;
go(0, 1, 0);
return total;
}
static long countCoprime(long limit, long m) {
long[] primes = new long[64];
int cnt = 0;
for (long d = 2; d * d <= m; d++) {
if (m % d == 0) {
primes[cnt++] = d;
while (m % d == 0) m /= d;
}
}
if (m > 1) primes[cnt++] = m;
return limit - countDivisibleByAny(limit, Arrays.copyOf(primes, cnt));
}
static void check(boolean cond, String msg) { if (!cond) throw new AssertionError(msg); }
public static void main(String[] args) {
check(countDivisibleByAny(100, new long[] {2, 3, 5}) == 74, "2,3,5");
check(countDivisibleByAny(100, new long[] {4, 6, 10}) == 36, "4,6,10");
check(countDivisibleByAny(1000, new long[] {2, 3, 5}) == 734, "1000");
check(countDivisibleByAny(100, new long[] {1, 7}) == 100, "divisor 1");
check(countDivisibleByAny(0, new long[] {2}) == 0, "n = 0");
check(countCoprime(100, 30) == 26 && countCoprime(1000, 30) == 266, "coprime");
check(countCoprime(36, 36) == 12, "phi(36)");
long[] first10 = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
check(countDivisibleByAny(1_000_000_000_000_000_000L, first10) == 842_052_776_898_047_765L,
"first 10 primes");
long e18 = 1_000_000_000_000_000_000L;
check(countDivisibleByAny(e18, new long[] {e18, e18 - 1}) == 2, "huge divisors");
Random rng = new Random(7);
for (int t = 0; t < 300; t++) {
int lim = rng.nextInt(3000);
long[] d = new long[1 + rng.nextInt(6)];
for (int i = 0; i < d.length; i++) d[i] = 1 + rng.nextInt(59);
long brute = 0;
for (int x = 1; x <= lim; x++) {
for (long v : d) if (x % v == 0) { brute++; break; }
}
check(countDivisibleByAny(lim, d) == brute, "random");
}
System.out.println("inclusion-exclusion: all checks passed");
}
}
#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>
using i64 = long long;
// How many x in [1, n] are divisible by at least one of the divisors (all >= 1).
i64 count_divisible_by_any(i64 n, std::vector<i64> ds) {
std::sort(ds.begin(), ds.end());
ds.erase(std::unique(ds.begin(), ds.end()), ds.end());
i64 total = 0;
std::function<void(size_t, i64, int)> go = [&](size_t start, i64 l, int size) {
for (size_t i = start; i < ds.size(); ++i) {
i64 g = std::gcd(l, ds[i]);
if (l / g > n / ds[i]) continue; // lcm > n: term and supersets are 0
i64 nl = l / g * ds[i]; // safe: nl <= n
total += (size % 2 == 0) ? n / nl : -(n / nl);
go(i + 1, nl, size + 1);
}
};
go(0, 1, 0);
return total;
}
i64 count_coprime(i64 n, i64 m) {
std::vector<i64> primes;
for (i64 d = 2; d * d <= m; ++d)
if (m % d == 0) {
primes.push_back(d);
while (m % d == 0) m /= d;
}
if (m > 1) primes.push_back(m);
return n - count_divisible_by_any(n, primes);
}
int main() {
assert(count_divisible_by_any(100, {2, 3, 5}) == 74);
assert(count_divisible_by_any(100, {4, 6, 10}) == 36);
assert(count_divisible_by_any(1000, {2, 3, 5}) == 734);
assert(count_divisible_by_any(100, {1, 7}) == 100);
assert(count_divisible_by_any(0, {2}) == 0);
assert(count_coprime(100, 30) == 26 && count_coprime(1000, 30) == 266);
assert(count_coprime(36, 36) == 12);
const i64 E18 = 1000000000000000000LL;
assert(count_divisible_by_any(E18, {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}) == 842052776898047765LL);
assert(count_divisible_by_any(E18, {E18, E18 - 1}) == 2);
std::mt19937 rng(7);
for (int t = 0; t < 300; ++t) {
i64 n = rng() % 3000;
std::vector<i64> ds(1 + rng() % 6);
for (auto& d : ds) d = 1 + rng() % 59;
i64 brute = 0;
for (i64 x = 1; x <= n; ++x)
if (std::any_of(ds.begin(), ds.end(), [&](i64 d) { return x % d == 0; })) ++brute;
assert(count_divisible_by_any(n, ds) == brute);
}
std::cout << "inclusion-exclusion: all checks passed\n";
}
// BigInt so that n up to 1e18 is exact.
function gcd(a: bigint, b: bigint): bigint {
while (b !== 0n) [a, b] = [b, a % b];
return a;
}
/** How many x in [1, n] are divisible by at least one of the divisors (all >= 1). */
function countDivisibleByAny(n: bigint, divisors: bigint[]): bigint {
const ds = [...new Set(divisors)].sort((a, b) => (a < b ? -1 : a > b ? 1 : 0));
let total = 0n;
const go = (start: number, l: bigint, size: number): void => {
for (let i = start; i < ds.length; i++) {
const g = gcd(l, ds[i]);
if (l / g > n / ds[i]) continue; // lcm > n: term and supersets are 0
const nl = (l / g) * ds[i];
total += size % 2 === 0 ? n / nl : -(n / nl);
go(i + 1, nl, size + 1);
}
};
go(0, 1n, 0);
return total;
}
function countCoprime(n: bigint, m: bigint): bigint {
const primes: bigint[] = [];
for (let d = 2n; d * d <= m; d++) {
if (m % d === 0n) {
primes.push(d);
while (m % d === 0n) m /= d;
}
}
if (m > 1n) primes.push(m);
return n - countDivisibleByAny(n, primes);
}
function assert(cond: boolean, msg: string): void { if (!cond) throw new Error(msg); }
assert(countDivisibleByAny(100n, [2n, 3n, 5n]) === 74n, "2,3,5");
assert(countDivisibleByAny(100n, [4n, 6n, 10n]) === 36n, "4,6,10");
assert(countDivisibleByAny(1000n, [2n, 3n, 5n]) === 734n, "1000");
assert(countDivisibleByAny(100n, [1n, 7n]) === 100n, "divisor 1");
assert(countDivisibleByAny(0n, [2n]) === 0n, "n = 0");
assert(countCoprime(100n, 30n) === 26n && countCoprime(1000n, 30n) === 266n, "coprime");
assert(countCoprime(36n, 36n) === 12n, "phi(36)");
const first10 = [2n, 3n, 5n, 7n, 11n, 13n, 17n, 19n, 23n, 29n];
assert(countDivisibleByAny(10n ** 18n, first10) === 842_052_776_898_047_765n, "first 10 primes");
assert(countDivisibleByAny(10n ** 18n, [10n ** 18n, 10n ** 18n - 1n]) === 2n, "huge divisors");
let seed = 7;
const rand = (m: number): number => {
seed = (seed * 1103515245 + 12345) % 2147483648;
return seed % m;
};
for (let t = 0; t < 300; t++) {
const n = rand(3000);
const ds = Array.from({ length: 1 + rand(6) }, () => 1 + rand(59));
let brute = 0;
for (let x = 1; x <= n; x++) if (ds.some((d) => x % d === 0)) brute++;
assert(countDivisibleByAny(BigInt(n), ds.map(BigInt)) === BigInt(brute), "random");
}
console.log("inclusion-exclusion: all checks passed");
Burnside: necklaces and bracelets
from itertools import product
from math import gcd
MOD = 1_000_000_007
def necklaces(n: int, k: int) -> int:
"""Colourings of n beads with k colours, up to rotation (Burnside)."""
return sum(k ** gcd(i, n) for i in range(n)) // n
def bracelets(n: int, k: int) -> int:
"""Up to rotation and reflection: dihedral group of size 2n."""
rotations = sum(k ** gcd(i, n) for i in range(n))
if n % 2 == 1:
reflections = n * k ** ((n + 1) // 2) # each axis: one bead + (n-1)/2 pairs
else:
reflections = (n // 2) * k ** (n // 2 + 1) + (n // 2) * k ** (n // 2)
return (rotations + reflections) // (2 * n)
def necklaces_mod(n: int, k: int) -> int:
"""Necklace count mod a prime (n not a multiple of MOD), for large n and k."""
s = sum(pow(k, gcd(i, n), MOD) for i in range(n)) % MOD
return s * pow(n, MOD - 2, MOD) % MOD
def brute_orbits(n: int, k: int, flips: bool) -> int:
seen: set[tuple[int, ...]] = set()
orbits = 0
for c in product(range(k), repeat=n):
if c in seen:
continue
orbits += 1
for base in ((c, c[::-1]) if flips else (c,)):
for r in range(n):
seen.add(base[r:] + base[:r])
return orbits
if __name__ == "__main__":
assert [2 ** gcd(i, 6) for i in range(6)] == [64, 2, 4, 8, 4, 2]
assert necklaces(6, 2) == 14 and bracelets(6, 2) == 13
assert necklaces(4, 2) == 6 and necklaces(5, 3) == 51 and necklaces(6, 3) == 130
assert necklaces(8, 2) == 36 and bracelets(5, 3) == 39
for n in range(1, 9):
for k in range(1, 4):
if k ** n <= 7000:
assert necklaces(n, k) == brute_orbits(n, k, False)
assert bracelets(n, k) == brute_orbits(n, k, True)
assert necklaces_mod(12, 3) == 44368 == necklaces(12, 3)
assert necklaces_mod(10**6, 10**6) == 905_621_449
print("Burnside: all checks passed")
import java.util.HashSet;
public class Main {
static final long MOD = 1_000_000_007L;
static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
static long ipow(long b, int e) { long r = 1; while (e-- > 0) r *= b; return r; }
/** Up to rotation (exact; fine while k^n fits in a long). */
static long necklaces(int n, int k) {
long s = 0;
for (int i = 0; i < n; i++) s += ipow(k, gcd(i, n));
return s / n;
}
/** Up to rotation and reflection. */
static long bracelets(int n, int k) {
long rot = 0;
for (int i = 0; i < n; i++) rot += ipow(k, gcd(i, n));
long refl = (n % 2 == 1) ? n * ipow(k, (n + 1) / 2)
: (n / 2) * ipow(k, n / 2 + 1) + (n / 2) * ipow(k, n / 2);
return (rot + refl) / (2L * n);
}
static long powMod(long a, long e, long m) {
long r = 1;
a %= m;
for (; e > 0; e >>= 1, a = a * a % m) if ((e & 1) == 1) r = r * a % m;
return r;
}
static long necklacesMod(int n, long k) {
long s = 0;
for (int i = 0; i < n; i++) s = (s + powMod(k, gcd(i, n), MOD)) % MOD;
return s * powMod(n, MOD - 2, MOD) % MOD;
}
/** Brute force: canonical form = smallest encoding over the symmetry group. */
static long bruteOrbits(int n, int k, boolean flips) {
HashSet<String> seen = new HashSet<>();
int total = (int) ipow(k, n);
int[] c = new int[n];
for (int code = 0; code < total; code++) {
for (int i = 0, x = code; i < n; i++, x /= k) c[i] = x % k;
String best = null;
for (int f = 0; f < (flips ? 2 : 1); f++) {
for (int r = 0; r < n; r++) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
int idx = (r + i) % n;
sb.append(c[f == 0 ? idx : n - 1 - idx]);
}
String s = sb.toString();
if (best == null || s.compareTo(best) < 0) best = s;
}
}
seen.add(best);
}
return seen.size();
}
static void check(boolean cond, String msg) { if (!cond) throw new AssertionError(msg); }
public static void main(String[] args) {
check(necklaces(6, 2) == 14 && bracelets(6, 2) == 13, "n=6, k=2");
check(necklaces(4, 2) == 6 && necklaces(5, 3) == 51 && necklaces(6, 3) == 130, "small");
check(necklaces(8, 2) == 36 && bracelets(5, 3) == 39, "more");
for (int n = 1; n <= 8; n++)
for (int k = 1; k <= 3; k++)
if (ipow(k, n) <= 7000) {
check(necklaces(n, k) == bruteOrbits(n, k, false), "necklace " + n + "," + k);
check(bracelets(n, k) == bruteOrbits(n, k, true), "bracelet " + n + "," + k);
}
check(necklacesMod(12, 3) == 44368, "mod small");
check(necklacesMod(1_000_000, 1_000_000) == 905_621_449, "mod big");
System.out.println("Burnside: all checks passed");
}
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <set>
#include <vector>
using i64 = long long;
const i64 MOD = 1000000007;
i64 ipow(i64 b, int e) { i64 r = 1; while (e-- > 0) r *= b; return r; }
i64 pow_mod(i64 a, i64 e, i64 m) {
i64 r = 1;
a %= m;
for (; e > 0; e >>= 1, a = a * a % m)
if (e & 1) r = r * a % m;
return r;
}
i64 necklaces(int n, int k) { // up to rotation
i64 s = 0;
for (int i = 0; i < n; ++i) s += ipow(k, std::gcd(i, n));
return s / n;
}
i64 bracelets(int n, int k) { // up to rotation and reflection
i64 rot = 0;
for (int i = 0; i < n; ++i) rot += ipow(k, std::gcd(i, n));
i64 refl = (n % 2 == 1) ? n * ipow(k, (n + 1) / 2)
: (n / 2) * ipow(k, n / 2 + 1) + (n / 2) * ipow(k, n / 2);
return (rot + refl) / (2LL * n);
}
i64 necklaces_mod(int n, i64 k) {
i64 s = 0;
for (int i = 0; i < n; ++i) s = (s + pow_mod(k, std::gcd(i, n), MOD)) % MOD;
return s * pow_mod(n, MOD - 2, MOD) % MOD;
}
i64 brute_orbits(int n, int k, bool flips) {
std::set<std::vector<int>> seen;
int total = (int)ipow(k, n);
std::vector<int> c(n);
for (int code = 0; code < total; ++code) {
for (int i = 0, x = code; i < n; ++i, x /= k) c[i] = x % k;
std::vector<int> best;
for (int f = 0; f < (flips ? 2 : 1); ++f)
for (int r = 0; r < n; ++r) {
std::vector<int> s(n);
for (int i = 0; i < n; ++i) {
int idx = (r + i) % n;
s[i] = c[f == 0 ? idx : n - 1 - idx];
}
if (best.empty() || s < best) best = s;
}
seen.insert(best);
}
return (i64)seen.size();
}
int main() {
assert(necklaces(6, 2) == 14 && bracelets(6, 2) == 13);
assert(necklaces(4, 2) == 6 && necklaces(5, 3) == 51 && necklaces(6, 3) == 130);
assert(necklaces(8, 2) == 36 && bracelets(5, 3) == 39);
for (int n = 1; n <= 8; ++n)
for (int k = 1; k <= 3; ++k)
if (ipow(k, n) <= 7000) {
assert(necklaces(n, k) == brute_orbits(n, k, false));
assert(bracelets(n, k) == brute_orbits(n, k, true));
}
assert(necklaces_mod(12, 3) == 44368);
assert(necklaces_mod(1000000, 1000000) == 905621449);
std::cout << "Burnside: all checks passed\n";
}
const MOD = 1_000_000_007n;
const gcd = (a: number, b: number): number => (b === 0 ? a : gcd(b, a % b));
/** Up to rotation (exact while k^n < 2^53). */
function necklaces(n: number, k: number): number {
let s = 0;
for (let i = 0; i < n; i++) s += k ** gcd(i, n);
return s / n;
}
/** Up to rotation and reflection. */
function bracelets(n: number, k: number): number {
let rot = 0;
for (let i = 0; i < n; i++) rot += k ** gcd(i, n);
const refl = n % 2 === 1
? n * k ** ((n + 1) / 2)
: (n / 2) * k ** (n / 2 + 1) + (n / 2) * k ** (n / 2);
return (rot + refl) / (2 * n);
}
function powMod(a: bigint, e: bigint, m: bigint): bigint {
let r = 1n;
a %= m;
for (; e > 0n; e >>= 1n, a = (a * a) % m) if (e & 1n) r = (r * a) % m;
return r;
}
function necklacesMod(n: number, k: number): bigint {
// group rotations by g = gcd(i, n): the count of i with gcd g is phi(n / g)
let s = 0n;
for (let g = 1; g <= n; g++) {
if (n % g !== 0) continue;
let m = n / g, phi = m;
for (let p = 2; p * p <= m; p++) {
if (m % p === 0) {
while (m % p === 0) m /= p;
phi -= phi / p;
}
}
if (m > 1) phi -= phi / m;
s = (s + BigInt(phi) * powMod(BigInt(k), BigInt(g), MOD)) % MOD;
}
return (s * powMod(BigInt(n), MOD - 2n, MOD)) % MOD;
}
function bruteOrbits(n: number, k: number, flips: boolean): number {
const seen = new Set<string>();
const total = k ** n;
for (let code = 0; code < total; code++) {
const c: number[] = [];
for (let i = 0, x = code; i < n; i++, x = Math.floor(x / k)) c.push(x % k);
let best = "";
for (let f = 0; f < (flips ? 2 : 1); f++)
for (let r = 0; r < n; r++) {
let s = "";
for (let i = 0; i < n; i++) {
const idx = (r + i) % n;
s += c[f === 0 ? idx : n - 1 - idx];
}
if (best === "" || s < best) best = s;
}
seen.add(best);
}
return seen.size;
}
function assert(cond: boolean, msg: string): void { if (!cond) throw new Error(msg); }
assert(necklaces(6, 2) === 14 && bracelets(6, 2) === 13, "n=6, k=2");
assert(necklaces(4, 2) === 6 && necklaces(5, 3) === 51 && necklaces(6, 3) === 130, "small");
assert(necklaces(8, 2) === 36 && bracelets(5, 3) === 39, "more");
for (let n = 1; n <= 8; n++)
for (let k = 1; k <= 3; k++)
if (k ** n <= 7000) {
assert(necklaces(n, k) === bruteOrbits(n, k, false), `necklace ${n},${k}`);
assert(bracelets(n, k) === bruteOrbits(n, k, true), `bracelet ${n},${k}`);
}
assert(necklacesMod(12, 3) === 44368n, "mod small");
assert(necklacesMod(1_000_000, 1_000_000) === 905_621_449n, "mod big");
console.log("Burnside: all checks passed");
Real-world uses
- Lottery and game odds. The UK National Lotto (6 of 59) has outcomes; US Powerball (5 of 69, then 1 of 26) has ; EuroMillions (5 of 50 and 2 of 12) has . Regulators publish exactly these numbers as the jackpot odds.
- Statistics. The hypergeometric distribution behind Fisher's exact test, used for small-sample A/B tests, is a ratio of binomial coefficients (see Statistics for A/B Testing); the Mann–Whitney U distribution is computed by a counting recurrence.
- Chemistry. Pólya's 1937 paper counted isomers of chemical compounds (for example, the substituted benzenes and alkanes) with exactly the Burnside/Pólya machinery shown above; it remains the textbook method in chemical graph enumeration.
- Machine learning feature sizing. Polynomial feature expansion of degree on inputs produces columns (scikit-learn's
PolynomialFeatureswith bias), a stars-and-bars count; pairwise interaction features are . - Software testing. Exhaustive testing of boolean flags needs runs, while pairwise (all-pairs) covering arrays need only a number that grows logarithmically in ; the counting argument is why pairwise testing tools such as Microsoft's PICT exist.
- Error-correcting codes and hashing. The Hamming bound counts the words within distance of a codeword; birthday-style collision estimates for IDs and hashes come from (see Probability for Engineers and Hash Tables).
- Parsing and compilers. The number of parse trees of an ambiguous expression without parentheses grows like the Catalan numbers, which is why grammars fix precedence and associativity; Interval DP problems such as matrix-chain ordering search a Catalan-sized space in polynomial time.
- Load balancing and scheduling. "Distribute identical jobs to machines with capacity " is stars and bars with inclusion–exclusion; used for counting feasible assignments in capacity planning estimates.
Pitfalls & edge cases
- Using factorial tables with .
fact[n] = 0, answers become 0. Use Lucas or a bigger prime. - Forgetting or . Return 0, not a crash or a garbage index.
- Dividing modulo a composite.
inv_factdoes not exist for numbers sharing a factor with the modulus. Use Pascal or the prime-power method. - Overflow in
fact[n] * inv_fact[k] * inv_fact[n-k]. Reduce after each multiplication; in JavaScript useBigIntor split multiplication. - Multiplying instead of taking the lcm in divisibility inclusion–exclusion ( means 12, not 24). And the lcm itself can overflow: compare before multiplying.
- Duplicates in the divisor list. must count once. Deduplicate first (the code does).
- Off-by-one in stars and bars. Non-negative: ; positive: . Test with and .
- Upper bounds in stars and bars handled by "subtract the bad ones" once. You must alternate signs over all subsets of violated bounds.
- Catalan off-by-one. counts strings with pairs (length ), trees with nodes, polygons with sides. Always check .
- Burnside: dividing before summing. The individual terms are not divisible by ; only the sum is. Modulo , multiply the sum by , which requires .
- Necklace vs bracelet. Does flipping count as the same? Read the statement: CSES "Necklaces" is rotation only.
- Derangement base cases. (the empty permutation has no fixed points), .
Variations
- Multinomial coefficients modulo : from the same tables.
- Lattice paths with obstacles: sort obstacles,
ways[i]= paths to obstacle avoiding earlier ones = (inclusion–exclusion as a DP; Codeforces 559C, discussed in Grid & Path DP). - Inclusion–exclusion on subsets with SOS: when depends on the subset in a structured way, compute all of them with SOS DP ("superset sums" plus Möbius transform on the subset lattice).
- Möbius inversion is inclusion–exclusion on the divisor lattice; see Number Theory II.
- Burnside with colour restrictions or adjacency rules: count fixed colourings per symmetry with a DP or a matrix power (for "no two adjacent beads the same colour", fixed colourings of a rotation are counted with the trace of a transfer matrix; see Matrix Exponentiation).
- Grid colourings up to rotation (CSES "Grid Paintings"): the group is the 4 rotations of the square; fixed colourings are .
- Catalan generalizations: Fuss–Catalan for -ary trees; Schröder and Motzkin numbers for paths with flat steps; the "-th Catalan with a forbidden prefix" problems use the reflection trick with a shifted barrier.
- Generating functions + NTT: products of many small polynomials (divide and conquer), power series inverse, log and exp give partition numbers, Bell numbers and Stirling rows in .
Practice ladder
Each problem is described in my own words; follow the link for the full statement.
1. Pascal's Triangle (LeetCode 118) — Build the first rows of Pascal's triangle. Warm-up for the additive rule.
Hint
Each row is [1] + [a + b for adjacent pairs] + [1].
2. Unique Paths (LeetCode 62) — Right/down routes in a grid. Teaches "choose which moves are downs": .
Hint
Compute with the multiplicative formula, dividing at each step to stay exact: r = r * (n - k + i) // i.
3. Binomial Coefficients (CSES 1079) — Up to queries of with . Teaches the factorial tables.
Solution
The first code block of this lesson: build tables of size once, answer each query in . Read input fast; lines is enough that slow I/O dominates in Python.
4. Creating Strings II (CSES 1715) — Count distinct rearrangements of a string of length up to , modulo . Teaches multinomials.
Hint
using inv_fact.
5. Distributing Apples (CSES 1716) — identical apples to children, any child may get none. Teaches stars and bars.
Solution
Non-negative solutions of : , from tables of size .
MOD = 10**9 + 7
def distributing_apples(n: int, m: int) -> int:
size = n + m
fact = [1] * size
for i in range(1, size):
fact[i] = fact[i - 1] * i % MOD
num = fact[n + m - 1]
den = fact[n - 1] * fact[m] % MOD
return num * pow(den, MOD - 2, MOD) % MOD
assert distributing_apples(3, 2) == 6 # (2,0,0)x3 + (1,1,0)x3
assert distributing_apples(3, 10) == 66
6. Unique Binary Search Trees (LeetCode 96) — Count BST shapes on keys. Teaches recognizing Catalan numbers.
Hint
; for it fits in 32 bits.
7. Bracket Sequences I (CSES 2064) — Count balanced bracket strings of length modulo . Teaches the closed-form Catalan with tables, including the odd-length case.
Solution
If is odd, 0. Otherwise and the answer is , or .
MOD = 10**9 + 7
def bracket_sequences(n: int) -> int:
if n % 2:
return 0
k = n // 2
fact = [1] * (n + 1)
for i in range(1, n + 1):
fact[i] = fact[i - 1] * i % MOD
c = fact[2 * k] * pow(fact[k] * fact[k] % MOD, MOD - 2, MOD) % MOD
return c * pow(k + 1, MOD - 2, MOD) % MOD
assert [bracket_sequences(n) for n in range(0, 11)] == [1, 0, 1, 0, 2, 0, 5, 0, 14, 0, 42]
8. Bracket Sequences II (CSES 2187) — Same, but the string must start with a given prefix. Teaches the reflection argument with a shifted start.
Hint
After the prefix you are at height with steps left, so you need up-steps and down-steps. All completions: . Bad completions (touching ) reflect, after their first touch, to paths ending at , which have up-steps: . Answer , or 0 if the prefix itself dips below 0, is odd, or .
9. Christmas Party (CSES 1717) — Gift exchange where nobody gets their own gift. Teaches derangements modulo a prime.
Hint
, or .
10. Ugly Number III (LeetCode 1201) — The -th positive integer divisible by , or . Teaches inclusion–exclusion inside a binary search.
Solution
count(x) = numbers divisible by , or , by inclusion–exclusion with lcms. It is monotone, so binary search for the smallest with count(x) >= n.
from math import lcm
def nth_ugly_number(n: int, a: int, b: int, c: int) -> int:
ab, ac, bc, abc = lcm(a, b), lcm(a, c), lcm(b, c), lcm(a, b, c)
def count(x: int) -> int:
return x // a + x // b + x // c - x // ab - x // ac - x // bc + x // abc
lo, hi = 1, 2 * 10**9
while lo < hi:
mid = (lo + hi) // 2
if count(mid) >= n:
hi = mid
else:
lo = mid + 1
return lo
assert nth_ugly_number(3, 2, 3, 5) == 4
assert nth_ugly_number(4, 2, 3, 4) == 6
assert nth_ugly_number(5, 2, 11, 13) == 10
11. NEQ (AtCoder ABC 172 E) — Count pairs of sequences of distinct values from with at every position. Teaches inclusion–exclusion over "positions where they agree", a generalized derangement.
Hint
Fix : ways. For , force a set of positions equal to : . Answer .
12. Placing Rooks (Codeforces 1342E) — Place rooks on an board so every empty cell is attacked and exactly pairs attack each other. Teaches surjections via inclusion–exclusion.
Hint
Every row (or every column) must hold a rook. If every row does, the rooks occupy columns: choose them () and count surjections from rows onto columns (). Double for the column case when .
13. Necklaces (CSES 2209) — Count necklaces of pearls with colours up to rotation, modulo . Teaches Burnside.
Solution
The third code block's necklaces_mod: , with the division done by a modular inverse of (fine because ).
14. Grid Paintings (CSES 2210) — Colour an grid with colours, up to rotations of the square. Teaches Burnside with a non-cyclic action.
Hint
Four rotations: identity fixes ; 180° fixes ; 90° and 270° fix each. Average them.
15. Binomial Coefficient (Library Checker) — modulo an arbitrary for up to . Teaches the prime-power Lucas generalization and CRT.
Hint
Factor ; for each use Granville's theorem (factorials with multiples of removed, periodic modulo , plus the carry count from Kummer); glue with CRT.
Common mistakes & interview follow-ups
"Why is zero for my ?" Because fact[n] contains . Explain Lucas and give .
"Compute exactly without overflow for ." Use the multiplicative form for ; each intermediate is an integer (it equals ), and with the largest intermediate stays below .
"Prove the Catalan closed form." Reflection: bad paths ↔ paths ending at , so .
"How many numbers up to are coprime to ?" Factor (Pollard's rho if needed, see Number Theory II), then inclusion–exclusion over its at most 15 distinct primes.
"Count necklaces; what changes if flips are allowed?" Burnside over the dihedral group; give the reflection fixed counts for odd and even .
"Why is inclusion–exclusion exponential, and when is it fine?" terms; fine for ish, or when pruning (lcm > N) kills most branches, or when symmetry makes depend only on (then it is terms, as in derangements and surjections).
Mistakes interviewers watch for: confusing permutations and combinations; forgetting to divide by for unordered selections; stars-and-bars off by one; using product instead of lcm; modular division without an inverse; not handling .
Quick quiz
1. How many solutions does have with ?
Answer
. (Brute force agrees: 10.)
2. Compute with Lucas.
Answer
Base-13 digits and : .
3. Why are there 14 necklaces of 6 two-coloured beads, not ?
Answer
Some colourings are fixed by non-trivial rotations, so orbits have different sizes. Burnside averages the fixed counts: .
4. In the reflection proof for Catalan numbers, why does every path from to touch height ?
Answer
Heights change by exactly 1 per step, start at 0 and end at , so the path must pass through .
5. How many integers in are divisible by 4, 6 or 10?
Answer
, using lcms 12, 20, 30 and 60.
6. How many surjections are there from a 6-element set onto a 3-element set?
Answer
.
Further reading / sources
- Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, 2nd ed. (1994) — Ch. 5 (binomial coefficients and identities), Ch. 6 (Stirling and Catalan numbers), Ch. 7 (generating functions).
- Richard P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd ed. (2011) — §1.9 (the twelvefold way), Ch. 2 (inclusion–exclusion); Catalan Numbers (2015).
- Herbert S. Wilf, generatingfunctionology, 3rd ed. (2006), freely available from the author's site.
- Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics (2009) — symbolic method and generating functions.
- Kenneth H. Rosen, Discrete Mathematics and Its Applications — counting, inclusion–exclusion, derangements (introductory).
- George Pólya, "Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen", Acta Mathematica 68, 1937.
- Édouard Lucas, "Théorie des fonctions numériques simplement périodiques", American Journal of Mathematics 1, 1878 (Lucas' theorem); Ernst Kummer, Journal für die reine und angewandte Mathematik 44, 1852 (carries).
- Andrew Granville, "Arithmetic properties of binomial coefficients I: Binomial coefficients modulo prime powers", CMS Conference Proceedings 20, 1997.
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, Appendix C (counting and probability).
- cp-algorithms: Binomial coefficients, Catalan numbers, Inclusion–exclusion, Burnside's lemma / Pólya enumeration, Stars and bars.
- OEIS: A000108 Catalan, A000166 derangements, A000031 binary necklaces, A000029 binary bracelets, A008277 Stirling 2nd kind.
Lessons: previous — Number Theory II · next — Probability & Expected Value · module — Mathematics for Algorithms · course — DSA: Zero to Mastery.
Related Archon pages: Counting & Combinatorial DP · Modular Arithmetic · Number Theory Basics · Grid & Path DP · Bit Manipulation · Backtracking & Recursion · Probability for Engineers · Statistics for A/B Testing · Matrix Exponentiation · FFT & NTT.