On this page

Counting & Combinatorial DP

How many ways can you roll a die until the total is exactly 8? How many ways can you pay 5 cents with 1-, 2- and 5-cent coins? How many correctly nested strings of 6 brackets are there? In how many ways can you split 10 into a sum of positive integers? How many ways can 8 people swap gifts so that nobody gets their own?

Every one of these asks for a number of objects, not for one best object. Counting DP answers them with the same machinery you already know from optimisation DP (state, transition, base case, fill order), but with one change in the arithmetic: where an optimisation DP takes min or max over the choices, a counting DP takes the sum. That small change brings two new dangers. The numbers get astronomically large, so we work modulo a prime (almost always ). And a sum is only correct if every object is counted exactly once, so we must design the state so that the cases never overlap.

This lesson builds the toolkit: the rule of sum and the rule of product, loop order and "canonical construction" to kill double counting, and then the classic families every competitive programmer and interviewer expects you to know: Pascal's triangle for , Catalan numbers, integer partitions, Stirling numbers of the second kind and Bell numbers, derangements, tilings and dice sums. It assumes DP Foundations and benefits from Knapsack, because several counting problems are knapsacks that count instead of maximise. You already met one counting DP in Grid & Path DP (unique paths).

Why this exists

Counting is the oldest part of combinatorics. Pascal's triangle was known in India, Persia and China centuries before Pascal's 1654 treatise. Montmort posed the "hat-check" derangement problem in 1708. Euler studied integer partitions in the 1740s. Catalan's numbers appear in Euler's 1751 count of polygon triangulations. Most of these come with clever closed formulas. So why would anyone need a DP?

Three reasons.

  1. The formula does not survive a small change. has a formula; "paths through a grid that avoid these three rocks" does not. "Partitions of " has deep formulas; "partitions of into parts from this list, each used at most twice" does not. A recurrence adapts to new rules; a formula usually breaks.
  2. The formula needs division, and modular division is awkward. requires dividing modulo , which needs modular inverses and fails when is small or not prime. The additive recurrence uses only +.
  3. Brute-force enumeration is hopeless. There are 190,569,292 partitions of 100 and about ways to split 20 items into groups. A counting DP finds these numbers in microseconds without listing a single object.

In software engineering, counting DPs show up whenever you need "how many": how many acyclic paths exist through a program's control-flow graph (for path profiling), how many outcomes of a test statistic are at least this extreme (for exact p-values), how many query plans an optimiser would have to consider. See Real-world uses.

Pattern triggers

If the problem says or has…Think of…
"number of ways", "how many", "count", "modulo "Counting DP: sum over disjoint cases
"order matters" / "sequences" / "compositions"Outer loop over the total, inner over the pieces
"order does not matter" / "combinations" / "multisets"Outer loop over the pieces, inner over the total (unbounded knapsack counting)
"each item at most once", "distinct parts", "subsets summing to"0/1 knapsack counting: inner loop downwards
"choose of ", "binomial", "Pascal"Pascal's rule , or factorials + inverses
"balanced parentheses", "binary trees with nodes", "BST shapes", "triangulations", "non-crossing"Catalan: split at the first return / at the root
"write as a sum of positive integers", "partitions"Partition DP: largest part
"put labelled items into unlabelled non-empty groups"Stirling numbers of the second kind
"all ways to group / cluster / partition a set"Bell numbers
"nobody gets their own", "no fixed point", "Secret Santa"Derangements
"tile a / board"Tiling DP by the last column; profile DP for wider boards
" dice with faces sum to target"Layered DP: dice × sum
"at least one of", "none of", "exactly" with overlapping conditionsInclusion–exclusion (often combined with a DP)
up to with a fixed-size recurrenceMatrix Exponentiation
Count numbers in with a digit propertyDigit DP

The meta-trigger: you are asked for a number, and listing the objects would take forever. Then find a way to split the set of objects into disjoint groups, each of which is "a smaller instance plus one decision".

Intuition & first principles

Two rules you already use every day

Rule of sum. If a set of objects splits into groups that do not overlap, the total is the sum of the group sizes. A menu with 3 soups and 4 salads offers 3 + 4 = 7 starters, provided no dish is both a soup and a salad.

Rule of product. If an object is built by making choice A and then choice B, and the number of options for B does not depend on which A you picked, the count is the product. 3 starters × 5 mains = 15 two-course meals.

Every counting DP is these two rules applied recursively. The DP state names a set of objects ("all ways to reach total 8"), the transition splits that set into disjoint groups by one decision ("by the value of the last die"), and each group is in one-to-one correspondence with a smaller set ("ways to reach 8 − 3, followed by a 3").

The word that matters is disjoint. In an optimisation DP, overlapping cases are harmless: min(a, a) is still a. In a counting DP, an object that sits in two groups is counted twice and the answer is silently wrong. Almost every bug in this lesson is a disjointness bug.

The "last decision" question

Pick a decision that every object makes exactly once and that has a small number of options: the last die rolled, the largest part used, the bracket that matches the first one, the position that person ends up in, the tile covering the last column. Group objects by that decision. Because each object made the decision exactly once, with exactly one value, the groups are disjoint and cover everything. That is the whole design method.

graph TD
    ALL["All objects of size n"] -->|"last decision = option 1"| G1["Group 1 ≅ objects of size n-1"]
    ALL -->|"last decision = option 2"| G2["Group 2 ≅ objects of size n-2"]
    ALL -->|"last decision = option 3"| G3["Group 3 ≅ objects of size n-3"]
    G1 --> SUM["count(n) = sum of group sizes"]
    G2 --> SUM
    G3 --> SUM

The symbol ≅ means "in one-to-one correspondence with": remove the last decision from an object in Group 1 and you get exactly one object of size , and every object of size comes from exactly one object in Group 1. A one-to-one correspondence is called a bijection.

A tiny example you can hold in your head

How many ways can you roll a six-sided die repeatedly so that the running total becomes exactly 4? Order matters: (1, 3) and (3, 1) are different.

Group by the last roll. If the last roll was 1, what came before was some way to reach 3. If it was 2, a way to reach 2. If 3, a way to reach 1. If 4, a way to reach 0 (the empty sequence: exactly 1 way). Rolls of 5 or 6 overshoot.

So ways(4) = ways(3) + ways(2) + ways(1) + ways(0). With ways(0) = 1, ways(1) = 1 (just "1"), ways(2) = 2 ("1 1", "2"), ways(3) = 4 ("1 1 1", "1 2", "2 1", "3"), we get ways(4) = 4 + 2 + 1 + 1 = 8. List them to check: 1111, 112, 121, 211, 22, 13, 31, 4. Eight.

Notice ways(0) = 1. The empty sequence is a real, single object. Getting the "size zero" base case right is the most common small mistake in counting DPs: it is almost always 1, not 0.

Why everything is "modulo "

Counts explode. The number of die sequences summing to 100 has 30 digits. Problems therefore ask for the answer modulo a large prime , almost always (or in problems that need FFT-friendly primes). The rules of modular arithmetic make this safe:

So you can reduce after every addition and multiplication and the final residue is the same as if you had used big integers. Why ? It is prime (so every non-zero number has a modular inverse, needed for division), it fits in a signed 32-bit integer, the sum of two residues fits in 32 bits unsigned and 64 bits signed, and the product of two residues () fits in a signed 64-bit integer (). Modular Arithmetic covers the theory.

Subtraction under a modulus

(a - b) % p can be negative in Java, C++ and JavaScript when a < b (their % keeps the sign of the left operand). Write ((a - b) % p + p) % p. Python's % is always non-negative, which hides this bug until you port the code.

Mechanics

1. Counting sequences: dice combinations

Problem. Count ordered sequences of die rolls (faces 1–6) with total exactly , modulo . (This is CSES "Dice Combinations".)

State: ways[s] = number of sequences with total . Transition: ways[s] = ways[s-1] + ways[s-2] + … + ways[s-6] (terms with negative index are 0). Base: ways[0] = 1 (the empty sequence). Order: increasing . Answer: ways[n].

Dry run up to :

ReadsComputationways[s]
0—base: the empty sequence1
1ways[0]11
2ways[0..1]1 + 12
3ways[0..2]1 + 1 + 24
4ways[0..3]1 + 1 + 2 + 48
5ways[0..4]1 + 1 + 2 + 4 + 816
6ways[0..5]1 + 1 + 2 + 4 + 8 + 1632
7ways[1..6]1 + 2 + 4 + 8 + 16 + 3263
8ways[2..7]2 + 4 + 8 + 16 + 32 + 63125

Up to 6 the counts double (every total up to 6 can end with any die face that does not overshoot). At 7 the pattern breaks: a roll of 7 would be needed to reach 7 from 0, so ways[0] drops out of the window. A brute-force enumeration of all die sequences confirms 125 for total 8.

The window is a fixed size (6), so you can keep a running sum and make each step , giving total. For around , a fixed-size linear recurrence like this one is a job for Matrix Exponentiation.

2. Avoiding double counting: the order of the loops

Problem. Coins of value 1, 2 and 5 cents. In how many ways can you pay 5 cents?

The answer depends on what "a way" means.

  • Combinations (a multiset of coins; "2 + 2 + 1" is the same as "1 + 2 + 2"): 4 ways — {5}, {2, 2, 1}, {2, 1, 1, 1}, {1, 1, 1, 1, 1}.
  • Sequences (order matters): 9 ways — "5"; the 3 orderings of {2, 2, 1}; the 4 orderings of {2, 1, 1, 1}; and "1 1 1 1 1".

Both are computed by a one-dimensional array dp[a] with dp[0] = 1. The only difference is which loop is outside.

def count_sequences(coins, amount):       # order matters: 1+2 and 2+1 differ
    dp = [1] + [0] * amount
    for a in range(1, amount + 1):        # outer: the total
        for c in coins:                   # inner: which coin comes LAST
            if c <= a:
                dp[a] += dp[a - c]
    return dp[amount]


def count_combinations(coins, amount):    # order does not matter
    dp = [1] + [0] * amount
    for c in coins:                       # outer: the coin type
        for a in range(c, amount + 1):    # inner: the total
            dp[a] += dp[a - c]
    return dp[amount]


assert count_sequences([1, 2, 5], 5) == 9
assert count_combinations([1, 2, 5], 5) == 4

Trace of the combinations version (dp after each coin type is fully processed):

After coindp[0]dp[1]dp[2]dp[3]dp[4]dp[5]Meaning
(start)100000only the empty multiset
1111111only 1-cent coins: one way each
2112233e.g. 4 = 1111, 211, 22
51122345 gains {5}

And the sequences version (dp after each amount):

Last coin 1Last coin 2Last coin 5dp[a]
0———1
1dp[0] = 1——1
2dp[1] = 1dp[0] = 1—2
3dp[2] = 2dp[1] = 1—3
4dp[3] = 3dp[2] = 2—5
5dp[4] = 5dp[3] = 3dp[0] = 19

Why the loop order decides it. In the sequences version, dp[a] groups sequences by their last coin — any coin may come last, so every ordering appears. In the combinations version, after processing coin type , dp[a] counts multisets that use only the first coin types. Adding coin to a multiset of the first types (including itself, which is why the inner loop goes upward and may reuse it) produces each multiset in exactly one way: as "its coins in sorted order". The coin-outer loop enforces a canonical order on the coins, so each multiset has exactly one representation.

That is the general cure for double counting:

Canonical construction

If several construction sequences produce the same object, pick one of them as the canonical one (smallest-first, largest-first, by position of the first element, …) and design the DP so it only ever builds canonical sequences. Then objects and construction sequences are in bijection, and the sum counts each object once.

Three more examples of the same idea:

  • Subsets with a given sum. Build a subset by deciding about item 1, then item 2, … — the canonical order is the item order. This is 0/1 knapsack counting; the inner loop runs downwards so each item is used at most once.
  • Partitions of (below). A partition is a multiset of positive integers; the canonical order is "parts in non-increasing order", enforced by the state "largest part allowed".
  • Set partitions (Stirling numbers, below). Canonical order: groups are created in the order of their smallest element.

The three loop patterns side by side:

WantOuter loopInner loopDirection of inner loop
Sequences (order matters, unlimited reuse)total itemany
Multisets (order ignored, unlimited reuse)itemtotal upward
Subsets (order ignored, each item at most once)itemtotal downward

3. Pascal's triangle: by addition

(" choose ") counts the -element subsets of an -element set.

Last-decision split. Look at element . Either it is in the subset — then the other elements are a subset of the first — or it is not — then all elements come from the first . These groups are disjoint, so

graph TD
    A["C(4,2) = 6: 2-subsets of 1..4"] -->|"contains 4"| B["C(3,1) = 3: pick 1 more from 1..3"]
    A -->|"does not contain 4"| C["C(3,2) = 3: pick 2 from 1..3"]

Rows 0–6, each entry the sum of the two above it:

\ 0123456
01
111
2121
31331
414641
515101051
61615201561

Building rows costs additions and memory (or with one row updated right-to-left). It needs no division, so it works modulo any number, prime or not. Exact 64-bit integers hold every entry up to row 66 (); row 67 overflows ().

When is large (say ) and you need many queries, Pascal's table is too big. Precompute factorials and inverse factorials modulo a prime in , then answer each query in :

The inverse of comes from Fermat's little theorem, , and then inv_fact[i-1] = inv_fact[i] * i. Both methods are in the Implementation; they agree on every , and give and .

MethodPrecomputePer queryWorks mod non-prime?Max in practice
Pascal tableyesa few thousand
Factorials + inversesno (needs prime, )
Multiplicative formula with big integers— big-number ops— (exact value)when you need the exact number
Lucas's theorem prime, may be small up to , small

4. Catalan numbers: brackets and tree shapes

How many strings of pairs of brackets are balanced (every prefix has at least as many ( as ), and the totals are equal)? For : ((())), (()()), (())(), ()(()), ()()() — five.

Last-decision split: the first return. Every non-empty balanced string starts with (. Find the ) that matches it. Everything between them is a balanced string with some pairs; everything after is a balanced string with pairs. So every balanced string of pairs is uniquely ( ) , with pairs and pairs, and every such pair gives a different string. By the rules of product and sum:

graph LR
    S["balanced string, n pairs"] --> F["#quot;(#quot; + A + #quot;)#quot; + B"]
    F --> A1["A: balanced, i pairs (C_i ways)"]
    F --> B1["B: balanced, n-1-i pairs (C_(n-1-i) ways)"]

Uniqueness is the key: the matching bracket of the first ( is a single, well-defined position, so the split point is determined by the string. That is the canonical construction that prevents double counting.

The same numbers count binary tree shapes and BSTs. A binary search tree on keys is determined by its root , a BST on (left subtree, keys) and a BST on ( keys). With this is exactly the same recurrence. LeetCode 96 ("Unique Binary Search Trees") asks for this number.

Dry run of the convolution:

Terms for
0base1
11
22
35
414
542
6132
7429

A brute-force check over all bracket strings, and over all generated BSTs, gives 1, 1, 2, 5, 14, 42, 132, 429 for .

The DP is . The closed form gives precomputation with factorials; modulo , both give .

Other things counted by Catalan numbers (each via the same "split at a canonical point" argument): full parenthesisations of a product of factors (split at the last multiplication), triangulations of a convex polygon with sides (split at the triangle on a fixed edge), monotone lattice paths that never cross the diagonal, and stack-sortable permutations. Richard Stanley's book Catalan Numbers (2015) lists 214 such families.

5. Integer partitions

A partition of is a way to write as a sum of positive integers where order does not matter. The 7 partitions of 5 are:

5 · 4+1 · 3+2 · 3+1+1 · 2+2+1 · 2+1+1+1 · 1+1+1+1+1

Write each in non-increasing order (the canonical form) and count those. Let be the number of partitions of with every part at most . Last-decision split on "is there a part equal to ?":

  • No part equals : all parts are at most : .
  • At least one part equals : remove one copy of ; what is left is a partition of with parts at most : .
graph TD
    R["p(5,3): parts at most 3"] -->|"no part equals 3"| A["p(5,2) = 3"]
    R -->|"remove one 3"| B["p(2,3) = p(2,2) = 2"]
    A --> T["p(5,3) = 3 + 2 = 5"]
    B --> T

Check: the partitions of 5 with parts at most 3 are 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1 — five.

The table for (diagonal in bold):

\ 01234567
011111111
101111111
201222222
301233333
401345555
501356777
601479101111
7014811131415

The sequence for is 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, and (a number MacMahon computed by hand for Hardy and Ramanujan in 1918).

One-dimensional version. The table recurrence is exactly "multisets of coins, coin types ". So the combinations loop from section 2 computes with an array:

def partitions(n):
    dp = [1] + [0] * n
    for part in range(1, n + 1):          # outer: the part size (canonical order)
        for a in range(part, n + 1):      # inner: total, upward (a part may repeat)
            dp[a] += dp[a - part]
    return dp[n]


assert partitions(5) == 7 and partitions(100) == 190569292

Variants, one line each.

  • Distinct parts (each part used at most once, e.g. 10 = 7+2+1): the subsets loop — inner loop downward. for : 1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27. So 10 has 10 partitions into distinct parts.
  • Odd parts only: run the multisets loop over parts 1, 3, 5, …. Surprise: the counts are identical to distinct parts (Euler's theorem, 1748). Our script checks it for .
  • At most parts. Draw a partition as rows of dots (the Ferrers diagram) and flip it along its diagonal (the conjugate). Rows become columns, so "at most parts" becomes "largest part at most ". Hence the count is again . For example, 7 has partitions with at most 3 parts.
  • Exactly parts: , or directly (either some part is 1 — remove it — or all parts are at least 2 — subtract 1 from each of the parts). For , : 1, 3, 4, 3, 2, 1, 1.
  • Parts from a given set, with multiplicity limits: bounded knapsack counting.
graph LR
    P["4 + 2 + 1 (3 parts, largest 4)"] -->|"conjugate: flip rows and columns"| Q["3 + 2 + 1 + 1 (4 parts, largest 3)"]

Rows of 4, 2 and 1 dots, read column by column, give columns of height 3, 2, 1, 1 — so the conjugate of 4+2+1 is 3+2+1+1. Parts and largest part swap roles.

6. Stirling numbers of the second kind and Bell numbers

(also written ) counts the ways to split labelled items into non-empty, unlabelled groups. For items {1, 2, 3}: one way into 1 group, three ways into 2 groups ({1}{2,3}, {2}{1,3}, {3}{1,2}), one way into 3 groups. So , , .

Last-decision split: where does item go?

  • Item is alone in its group: the other items form groups: .
  • Item joins an existing group: first split items into groups ( ways), then pick which group item joins ( choices — the groups are distinguishable now, by their contents).
graph TD
    S["S(n,k): where does item n go?"] -->|"alone"| A["S(n-1,k-1)"]
    S -->|"joins one of k existing groups"| B["k × S(n-1,k)"]
\ 01234567Bell (row sum)
011
1011
20112
301315
40176115
501152510152
601319065151203
70163301350140211877

Example step: .

The Bell number counts all ways to split labelled items into groups, any number of groups: 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147 for . A brute-force generator of all set partitions confirms the table for . , which is why no clustering algorithm tries every possible grouping of even 20 points.

def stirling2_table(n_max, mod=10**9 + 7):
    S = [[0] * (n_max + 1) for _ in range(n_max + 1)]
    S[0][0] = 1
    for n in range(1, n_max + 1):
        for k in range(1, n + 1):
            S[n][k] = (k * S[n - 1][k] + S[n - 1][k - 1]) % mod
    return S


S = stirling2_table(9)
assert S[5][3] == 25 and S[7][4] == 350
assert [sum(row) for row in S] == [1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147]

Why "unlabelled groups" matters. If the groups are labelled (boxes A, B, C), each set partition into groups can be labelled in ways, so the number of onto (surjective) functions from items to labelled boxes is . For , : . Inclusion–exclusion gives the same number directly: .

7. Derangements

A derangement is a permutation where no element stays in its own position: nobody draws their own name in a Secret Santa. counts them. (the two 3-cycles: 231 and 312).

Last-decision split: where does element go, and what happens to the element it displaces? Element goes to some position : choices, and by symmetry each choice gives the same count. Fix one. Now look at element :

  • Element goes to position (they swap). The remaining elements must form a derangement among themselves: .
  • Element does not go to position . Then the elements other than must fill the positions other than , with each element avoiding position and element avoiding position . Rename position as "position " and this is exactly a derangement of elements: .
graph TD
    A["element n goes to position i: n-1 choices"] --> B{"does element i go to position n?"}
    B -->|"yes: a swap"| C["D(n-2)"]
    B -->|"no"| D["D(n-1) after renaming position n as i"]
0base11
1base00
210.5
320.333…
490.375
5440.3667
62650.3681
718540.36786
8148330.367882

A brute-force count over all permutations agrees for . The ratio races to : about 37% of random Secret Santa draws need a redraw no matter how many people take part.

The inclusion–exclusion view. Let be the set of permutations that fix element . Derangements are the permutations in none of the . Inclusion–exclusion (Combinatorics) gives

which is why , and why is the integer nearest to for . The DP is still the practical way to get : one multiplication and one addition per step, no inverses, and it gives every for at once. Modulo , .

Inclusion–exclusion inside a DP

Many counting problems with "at least one bad thing" are solved as: count everything with a DP, then add and subtract the counts that force subsets of bad events. When the bad events are ordered (obstacles on a grid sorted by position, as in Codeforces 559C from Grid & Path DP), the alternating sum itself becomes a DP: f[i] = ways to reach obstacle without touching an earlier one. The theory lives in Combinatorics.

8. Tilings

board with dominoes. Look at the left end. Either a vertical domino covers column 1 (the rest is a board), or two horizontal dominoes stacked on top of each other cover columns 1–2 (the rest is ). A horizontal domino in the top row forces one directly below it, so these are the only options and they are disjoint:

That is Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 for .

with dominoes and L-shaped trominoes (LeetCode 790). Enumerating the ways the left edge can be finished, including "two trominoes with dominoes in between", leads to the compact recurrence with , , : 1, 1, 2, 5, 11, 24, 53, 117, …. The clean derivation uses two states: = full boards and = boards with one cell sticking out, which is the idea that generalises.

with dominoes. Odd gives 0 (the area is odd). For even , : 1, 3, 11, 41, 153, 571, 2131 for .

in general. Track which cells of the next column are already covered by tiles sticking out of the current column: a bitmask "profile" of bits, states. This is Broken-Profile DP. When is huge and is small, the column-to-column transition is a matrix and Matrix Exponentiation finishes the job in .

9. Dice-roll sums with a fixed number of dice

Problem (LeetCode 1155). dice, each with faces . How many of the outcomes have total exactly target?

State: dp[i][s] = number of outcomes of the first dice with total . Transition: dp[i][s] = sum over f = 1..k of dp[i-1][s-f]. Base: dp[0][0] = 1. Answer: dp[n][target].

The layer index is what makes this different from section 1: there, the number of rolls was free; here it is fixed. Dice are distinguishable (die 1 shows 3 and die 2 shows 4 is a different outcome from the reverse), so this is a sequence count, layered by die. For two six-sided dice, dp[2][7] = 6; for 30 dice with 30 faces, dp[30][500] .

Naively each layer costs . A sliding-window sum (as in section 1) makes it per layer: total. Dividing by turns these counts into the exact probability distribution of the sum — the entry point to Probability DP.

10. Pointer: counting distinct subsequences

"How many times does rabbit appear as a subsequence of rabbbit?" and "How many distinct subsequences does a string have?" are counting DPs over prefixes of strings. The double-counting trap is sharp there: two different index sets can spell the same subsequence, and the fix subtracts the count from the previous occurrence of the same character. Both are worked in String DP.

The ladder: brute force → better → optimal

Problem: compute , the number of partitions of (exact, or modulo ).

Rung 1: generate every partition

Generate partitions in canonical (non-increasing) order: choose the first part the bound, recurse with the remainder and the new bound.

def partitions_brute(n, max_part=None):
    if max_part is None:
        max_part = n
    if n == 0:
        return 1                                      # the empty partition
    return sum(partitions_brute(n - first, first)    # next parts may not exceed `first`
               for first in range(min(n, max_part), 0, -1))

Correct, but it takes time proportional to the answer: (Hardy–Ramanujan), so already leaves.

Rung 2: memoise the same recursion

The recursion only ever asks about pairs , and there are of them. Cache them. Each pair loops over up to first parts, so this is time, memory — and a recursion depth of .

Rung 3: the two-term recurrence

Replace "loop over the first part" by the binary split from section 5: . Each state is now , so time, memory, filled in a table without recursion.

Rung 4: one array

Process in the outer loop and overwrite a single array (the combinations loop). time, memory. This is what you write in an interview.

Rung 5: Euler's pentagonal number theorem

Euler proved that over all integers . Inverting the generating function gives a recurrence with only terms:

(terms with negative argument are 0). Total .

def partitions_pentagonal(N):
    p = [1] + [0] * N
    for n in range(1, N + 1):
        total, j = 0, 1
        while j * (3 * j - 1) // 2 <= n:
            sign = 1 if j % 2 else -1
            total += sign * p[n - j * (3 * j - 1) // 2]
            if j * (3 * j + 1) // 2 <= n:
                total += sign * p[n - j * (3 * j + 1) // 2]
            j += 1
        p[n] = total
    return p


assert partitions_pentagonal(100)[100] == 190569292
RungMethodTimeExtra spaceWhy it is better than the rung above
1Generate all partitions, exponential in stackBaseline; obviously correct, a test oracle
2Memoised recursion over (n, max part) + stackEach sub-question answered once
3Two-term table work per state, no recursion
4Rolling 1-D arraySame time, linear memory
5Pentagonal recurrenceUses a theorem; fastest simple method

All five agree for every in this lesson's test script. Beyond rung 5, Johansson (2012) evaluated the Hardy–Ramanujan–Rademacher formula to compute exactly; that is number theory, not DP.

Correctness

Every counting DP has the same proof shape, and it has two halves:

  1. Partition. The set counted by the state is split into groups by one decision, and the groups are pairwise disjoint and together cover the set.
  2. Bijection. Each group is in one-to-one correspondence with a set counted by an earlier state (or a product of such sets).

Then the transition is the rule of sum over groups (and product within a group), and induction over the fill order finishes the proof. Below, each recurrence gets its two halves.

Dice combinations. Every non-empty sequence has exactly one last roll (disjoint, covering). Removing it maps sequences with last roll and total bijectively to sequences with total (inverse: append ). Base: one empty sequence with total 0.

Coin combinations (loop order). Invariant: after processing coin types , dp[a] equals the number of multisets of those types with total . Induction on : a multiset of types either contains no (counted before the pass) or contains at least one ; removing one maps the second kind bijectively to multisets of types with total , and because the inner loop runs upward, dp[a - c_j] has already been updated in this pass and counts exactly those. In the amount-outer loop, the invariant is instead "sequences with total ", split by the last coin. The two invariants count different sets, which is why the answers differ.

Pascal. Disjoint split by "contains element or not"; bijections: remove / do nothing.

Catalan. Each non-empty balanced string has a unique first ( and a unique matching ), so its decomposition (A)B is unique (disjoint by the length of ); conversely (A)B is balanced for any balanced and and its first bracket is matched exactly by the ) after , so the map is a bijection onto pairs . For BSTs, the root is unique and the BST property forces the left subtree to hold exactly the keys below the root.

Partitions. In canonical (non-increasing) form, "contains a part equal to " vs "does not" is disjoint and covering for partitions with parts . Removing one copy of is a bijection onto partitions of with parts (inverse: add a in front, which keeps the order non-increasing). Conjugation is an involution on Ferrers diagrams, which proves "at most parts" ↔ "largest part at most ".

Stirling. Item is either a singleton or not (disjoint, covering). Singletons: removing is a bijection onto partitions of into groups. Non-singletons: removing from its group leaves a partition of into groups (still all non-empty, since 's group had another member), and the map "partition, chosen group" ↔ "partition with inserted into that group" is a bijection with choices.

Derangements. The choices of give disjoint groups of equal size (swap the labels and to map one group onto another). Within a group, "" vs "" is disjoint and covering. In the first case, deleting elements and (and positions and ) leaves a derangement of the other elements, and every such derangement extends uniquely by the swap. In the second case, delete element and position , then rename position as position . The remaining constraints were " avoids position " for and "element avoids position "; after the renaming the last one reads "element avoids position ". So these permutations are in bijection with derangements of elements, and the map is reversible (rename back, put in position ).

Tilings. The cell in the top-left corner is covered by exactly one tile (disjoint, covering by its type and orientation); removing the tiles forced by that choice is a bijection onto tilings of the shorter board.

Complexity

ProblemTimeSpaceNotes
Dice combinations up to , or with a window sum, or rolling with matrix power
Coin sequences / combinations, coins, amount loop order chooses the meaning
Pascal table to row , or per rowno division needed
Factorials + inverses precompute, per query prime,
Catalan by DP with the closed form
Partitions pentagonal
Partitions into parts / at most parts
Stirling table, or rolling
Bell via Stirling rows or the Bell triangle
Derangements rolling
/ tilings with matrix power
dice, faces, target with window sums naive

Number sizes. With , residues fit in 32 bits, sums of two residues fit in a signed 64-bit integer, and products of two residues fit in a signed 64-bit integer (but not in a 32-bit one, and not exactly in a JavaScript number, whose integers are exact only up to ). Without a modulus: Catalan numbers overflow signed 64-bit after ; derangements after ; after ; Pascal entries after row 66. (All four limits were checked by script with exact integers.)

Implementation

Each block is complete and runs its own assertions on the numbers from this lesson. All four languages were run.

two ways: Pascal table and factorials

MOD = 10**9 + 7


def pascal_table(n_max: int, mod: int = MOD) -> list[list[int]]:
    """C[n][k] for 0 <= k <= n <= n_max, using only additions (works for any mod)."""
    C = [[0] * (n_max + 1) for _ in range(n_max + 1)]
    for n in range(n_max + 1):
        C[n][0] = 1
        for k in range(1, n + 1):
            C[n][k] = (C[n - 1][k - 1] + C[n - 1][k]) % mod
    return C


class Binomial:
    """O(n_max) precomputation, O(1) per query. Needs a prime mod > n_max."""

    def __init__(self, n_max: int, mod: int = MOD) -> None:
        self.mod = mod
        self.fact = [1] * (n_max + 1)
        for i in range(1, n_max + 1):
            self.fact[i] = self.fact[i - 1] * i % mod
        self.inv_fact = [1] * (n_max + 1)
        self.inv_fact[n_max] = pow(self.fact[n_max], mod - 2, mod)  # Fermat inverse
        for i in range(n_max, 0, -1):
            self.inv_fact[i - 1] = self.inv_fact[i] * i % mod

    def comb(self, n: int, k: int) -> int:
        if k < 0 or k > n:
            return 0
        return self.fact[n] * self.inv_fact[k] % self.mod * self.inv_fact[n - k] % self.mod


if __name__ == "__main__":
    C = pascal_table(1000)
    assert C[4][:5] == [1, 4, 6, 4, 1]
    assert C[6][:7] == [1, 6, 15, 20, 15, 6, 1]
    assert C[1000][500] == 159835829
    small = Binomial(300)
    assert all(C[n][k] == small.comb(n, k) for n in range(301) for k in range(n + 1))
    assert small.comb(5, 7) == 0
    assert Binomial(100000).comb(100000, 50000) == 149033233
    print("binomial tests passed")
public class Binomials {
    static final long MOD = 1_000_000_007L;

    static int[][] pascalTable(int nMax) {
        int[][] c = new int[nMax + 1][nMax + 1];
        for (int n = 0; n <= nMax; n++) {
            c[n][0] = 1;
            for (int k = 1; k <= n; k++)
                c[n][k] = (int) ((c[n - 1][k - 1] + (long) c[n - 1][k]) % MOD);
        }
        return c;
    }

    static long power(long base, long exp) {
        long result = 1;
        base %= MOD;
        while (exp > 0) {
            if ((exp & 1) == 1) result = result * base % MOD;
            base = base * base % MOD;
            exp >>= 1;
        }
        return result;
    }

    static final class Binomial {
        final long[] fact, invFact;

        Binomial(int nMax) {
            fact = new long[nMax + 1];
            invFact = new long[nMax + 1];
            fact[0] = 1;
            for (int i = 1; i <= nMax; i++) fact[i] = fact[i - 1] * i % MOD;
            invFact[nMax] = power(fact[nMax], MOD - 2);        // Fermat inverse
            for (int i = nMax; i > 0; i--) invFact[i - 1] = invFact[i] * i % MOD;
        }

        long comb(int n, int k) {
            if (k < 0 || k > n) return 0;
            return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
        }
    }

    public static void main(String[] args) {
        int[][] c = pascalTable(1000);
        int[] row6 = {1, 6, 15, 20, 15, 6, 1};
        for (int k = 0; k <= 6; k++) check(c[6][k] == row6[k]);
        check(c[4][2] == 6);
        check(c[1000][500] == 159835829);
        Binomial small = new Binomial(300);
        for (int n = 0; n <= 300; n++)
            for (int k = 0; k <= n; k++) check(c[n][k] == small.comb(n, k));
        check(small.comb(5, 7) == 0);
        check(new Binomial(100000).comb(100000, 50000) == 149033233L);
        System.out.println("binomial tests passed");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError("test failed");
    }
}
#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

const int64_t MOD = 1'000'000'007LL;

vector<vector<int64_t>> pascalTable(int nMax) {
    vector<vector<int64_t>> c(nMax + 1, vector<int64_t>(nMax + 1, 0));
    for (int n = 0; n <= nMax; n++) {
        c[n][0] = 1;
        for (int k = 1; k <= n; k++) c[n][k] = (c[n - 1][k - 1] + c[n - 1][k]) % MOD;
    }
    return c;
}

int64_t power(int64_t base, int64_t exp) {
    int64_t result = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) result = result * base % MOD;   // both < 2^30, product < 2^60
        base = base * base % MOD;
        exp >>= 1;
    }
    return result;
}

struct Binomial {
    vector<int64_t> fact, invFact;
    explicit Binomial(int nMax) : fact(nMax + 1), invFact(nMax + 1) {
        fact[0] = 1;
        for (int i = 1; i <= nMax; i++) fact[i] = fact[i - 1] * i % MOD;
        invFact[nMax] = power(fact[nMax], MOD - 2);   // Fermat inverse
        for (int i = nMax; i > 0; i--) invFact[i - 1] = invFact[i] * i % MOD;
    }
    int64_t comb(int n, int k) const {
        if (k < 0 || k > n) return 0;
        return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
    }
};

int main() {
    auto c = pascalTable(1000);
    vector<int64_t> row6 = {1, 6, 15, 20, 15, 6, 1};
    for (int k = 0; k <= 6; k++) assert(c[6][k] == row6[k]);
    assert(c[4][2] == 6);
    assert(c[1000][500] == 159835829);
    Binomial small(300);
    for (int n = 0; n <= 300; n++)
        for (int k = 0; k <= n; k++) assert(c[n][k] == small.comb(n, k));
    assert(small.comb(5, 7) == 0);
    assert(Binomial(100000).comb(100000, 50000) == 149033233);
    cout << "binomial tests passed\n";
    return 0;
}
const MOD = 1_000_000_007;

// a * b mod MOD without losing precision: a, b < 2^30, so split b into 16-bit halves.
function mulmod(a: number, b: number): number {
  const hi = (a * (b >>> 16)) % MOD; // < 2^30 * 2^14 = 2^44, exact
  return (hi * 65536 + a * (b & 0xffff)) % MOD; // each term < 2^46, sum exact
}

function power(base: number, exp: number): number {
  let result = 1;
  base %= MOD;
  while (exp > 0) {
    if (exp & 1) result = mulmod(result, base);
    base = mulmod(base, base);
    exp = Math.floor(exp / 2);
  }
  return result;
}

function pascalTable(nMax: number): number[][] {
  const c: number[][] = [];
  for (let n = 0; n <= nMax; n++) {
    const row = new Array<number>(n + 1).fill(0);
    row[0] = 1;
    for (let k = 1; k <= n; k++) row[k] = (c[n - 1][k - 1] + (k < n ? c[n - 1][k] : 0)) % MOD;
    c.push(row);
  }
  return c;
}

class Binomial {
  fact: number[];
  invFact: number[];
  constructor(nMax: number) {
    this.fact = new Array<number>(nMax + 1).fill(1);
    for (let i = 1; i <= nMax; i++) this.fact[i] = mulmod(this.fact[i - 1], i);
    this.invFact = new Array<number>(nMax + 1).fill(1);
    this.invFact[nMax] = power(this.fact[nMax], MOD - 2); // Fermat inverse
    for (let i = nMax; i > 0; i--) this.invFact[i - 1] = mulmod(this.invFact[i], i);
  }
  comb(n: number, k: number): number {
    if (k < 0 || k > n) return 0;
    return mulmod(mulmod(this.fact[n], this.invFact[k]), this.invFact[n - k]);
  }
}

function assert(ok: boolean, msg = "test failed"): void {
  if (!ok) throw new Error(msg);
}

const table = pascalTable(1000);
assert(JSON.stringify(table[6]) === JSON.stringify([1, 6, 15, 20, 15, 6, 1]));
assert(table[4][2] === 6);
assert(table[1000][500] === 159835829);
const small = new Binomial(300);
for (let n = 0; n <= 300; n++)
  for (let k = 0; k <= n; k++) assert(table[n][k] === small.comb(n, k));
assert(small.comb(5, 7) === 0);
assert(new Binomial(100000).comb(100000, 50000) === 149033233);
console.log("binomial tests passed");

The TypeScript mulmod is the important line: a * b for two residues near is about , far past , so plain (a * b) % MOD returns a wrong answer without any error. Splitting one factor into 16-bit halves keeps every intermediate product below . (BigInt also works but is several times slower.)

Integer partitions: all parts, at most parts, distinct parts

MOD = 10**9 + 7


def partitions(n: int, mod: int = MOD) -> int:
    """p(n): multisets of positive integers summing to n."""
    dp = [1] + [0] * n
    for part in range(1, n + 1):                 # canonical order: by part size
        for total in range(part, n + 1):         # upward: a part may repeat
            dp[total] = (dp[total] + dp[total - part]) % mod
    return dp[n]


def partitions_at_most_k_parts(n: int, k: int, mod: int = MOD) -> int:
    """Partitions of n into at most k parts = partitions with largest part <= k (conjugation)."""
    dp = [1] + [0] * n
    for part in range(1, min(k, n) + 1):
        for total in range(part, n + 1):
            dp[total] = (dp[total] + dp[total - part]) % mod
    return dp[n]


def partitions_distinct(n: int, mod: int = MOD) -> int:
    """Partitions of n into distinct parts: each part used at most once."""
    dp = [1] + [0] * n
    for part in range(1, n + 1):
        for total in range(n, part - 1, -1):     # downward: each part at most once
            dp[total] = (dp[total] + dp[total - part]) % mod
    return dp[n]


if __name__ == "__main__":
    assert [partitions(n) for n in range(11)] == [1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42]
    assert partitions(100) == 190569292
    assert partitions(1000) == 709496666                       # p(1000) mod 1e9+7
    assert [partitions_at_most_k_parts(7, k) for k in range(8)] == [0, 1, 4, 8, 11, 13, 14, 15]
    exactly = [partitions_at_most_k_parts(7, k) - partitions_at_most_k_parts(7, k - 1)
               for k in range(1, 8)]
    assert exactly == [1, 3, 4, 3, 2, 1, 1]
    assert partitions_distinct(10) == 10
    assert [partitions_distinct(n) for n in range(16)] == \
        [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27]
    print("partition tests passed")
public class Partitions {
    static final long MOD = 1_000_000_007L;

    static long partitions(int n) {
        return partitionsAtMostKParts(n, n);
    }

    /** Partitions of n into at most k parts = partitions with largest part at most k. */
    static long partitionsAtMostKParts(int n, int k) {
        long[] dp = new long[n + 1];
        dp[0] = 1;
        for (int part = 1; part <= Math.min(k, n); part++)
            for (int total = part; total <= n; total++)       // upward: parts may repeat
                dp[total] = (dp[total] + dp[total - part]) % MOD;
        return dp[n];
    }

    static long partitionsDistinct(int n) {
        long[] dp = new long[n + 1];
        dp[0] = 1;
        for (int part = 1; part <= n; part++)
            for (int total = n; total >= part; total--)       // downward: each part once
                dp[total] = (dp[total] + dp[total - part]) % MOD;
        return dp[n];
    }

    public static void main(String[] args) {
        long[] first = {1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42};
        for (int n = 0; n <= 10; n++) check(partitions(n) == first[n]);
        check(partitions(100) == 190569292L);
        check(partitions(1000) == 709496666L);
        long[] atMost = {0, 1, 4, 8, 11, 13, 14, 15};
        for (int k = 0; k <= 7; k++) check(partitionsAtMostKParts(7, k) == atMost[k]);
        long[] exactly = {1, 3, 4, 3, 2, 1, 1};
        for (int k = 1; k <= 7; k++)
            check(partitionsAtMostKParts(7, k) - partitionsAtMostKParts(7, k - 1) == exactly[k - 1]);
        long[] distinct = {1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27};
        for (int n = 0; n <= 15; n++) check(partitionsDistinct(n) == distinct[n]);
        System.out.println("partition tests passed");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError("test failed");
    }
}
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

const int64_t MOD = 1'000'000'007LL;

// Partitions of n into at most k parts = partitions with largest part at most k.
int64_t partitionsAtMostKParts(int n, int k) {
    vector<int64_t> dp(n + 1, 0);
    dp[0] = 1;
    for (int part = 1; part <= min(k, n); part++)
        for (int total = part; total <= n; total++)      // upward: parts may repeat
            dp[total] = (dp[total] + dp[total - part]) % MOD;
    return dp[n];
}

int64_t partitions(int n) { return partitionsAtMostKParts(n, n); }

int64_t partitionsDistinct(int n) {
    vector<int64_t> dp(n + 1, 0);
    dp[0] = 1;
    for (int part = 1; part <= n; part++)
        for (int total = n; total >= part; total--)      // downward: each part once
            dp[total] = (dp[total] + dp[total - part]) % MOD;
    return dp[n];
}

int main() {
    vector<int64_t> first = {1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42};
    for (int n = 0; n <= 10; n++) assert(partitions(n) == first[n]);
    assert(partitions(100) == 190569292);
    assert(partitions(1000) == 709496666);
    vector<int64_t> atMost = {0, 1, 4, 8, 11, 13, 14, 15};
    for (int k = 0; k <= 7; k++) assert(partitionsAtMostKParts(7, k) == atMost[k]);
    vector<int64_t> exactly = {1, 3, 4, 3, 2, 1, 1};
    for (int k = 1; k <= 7; k++)
        assert(partitionsAtMostKParts(7, k) - partitionsAtMostKParts(7, k - 1) == exactly[k - 1]);
    vector<int64_t> distinct = {1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27};
    for (int n = 0; n <= 15; n++) assert(partitionsDistinct(n) == distinct[n]);
    cout << "partition tests passed\n";
    return 0;
}
const MOD = 1_000_000_007;

// Partitions of n into at most k parts = partitions with largest part at most k.
function partitionsAtMostKParts(n: number, k: number): number {
  const dp = new Array<number>(n + 1).fill(0);
  dp[0] = 1;
  for (let part = 1; part <= Math.min(k, n); part++)
    for (let total = part; total <= n; total++) dp[total] = (dp[total] + dp[total - part]) % MOD; // upward
  return dp[n];
}

function partitions(n: number): number {
  return partitionsAtMostKParts(n, n);
}

function partitionsDistinct(n: number): number {
  const dp = new Array<number>(n + 1).fill(0);
  dp[0] = 1;
  for (let part = 1; part <= n; part++)
    for (let total = n; total >= part; total--) dp[total] = (dp[total] + dp[total - part]) % MOD; // downward
  return dp[n];
}

function assert(ok: boolean, msg = "test failed"): void {
  if (!ok) throw new Error(msg);
}

const first = [1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42];
for (let n = 0; n <= 10; n++) assert(partitions(n) === first[n]);
assert(partitions(100) === 190569292);
assert(partitions(1000) === 709496666);
const atMost = [0, 1, 4, 8, 11, 13, 14, 15];
for (let k = 0; k <= 7; k++) assert(partitionsAtMostKParts(7, k) === atMost[k]);
const exactly = [1, 3, 4, 3, 2, 1, 1];
for (let k = 1; k <= 7; k++)
  assert(partitionsAtMostKParts(7, k) - partitionsAtMostKParts(7, k - 1) === exactly[k - 1]);
const distinct = [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27];
for (let n = 0; n <= 15; n++) assert(partitionsDistinct(n) === distinct[n]);
console.log("partition tests passed");

Only additions appear, so the TypeScript version needs no mulmod (a sum of two residues is below ). Note the "exactly " check subtracts two unreduced-looking residues; it is safe here only because the true values are tiny. With large values, write (a - b + MOD) % MOD.

Catalan numbers and derangements modulo a prime

MOD = 10**9 + 7


def catalan_table(n: int, mod: int = MOD) -> list[int]:
    """C_0..C_n by the first-return recurrence, O(n^2)."""
    c = [0] * (n + 1)
    c[0] = 1
    for m in range(1, n + 1):
        c[m] = sum(c[i] * c[m - 1 - i] for i in range(m)) % mod
    return c


def catalan_formula(n: int, mod: int = MOD) -> int:
    """C_n = binom(2n, n) / (n + 1), with modular inverses (mod must be a prime > 2n)."""
    num = den = 1
    for i in range(1, n + 1):
        num = num * (n + i) % mod
        den = den * i % mod
    den = den * (n + 1) % mod
    return num * pow(den, mod - 2, mod) % mod


def derangements(n: int, mod: int = MOD) -> list[int]:
    """D(0..n): D(m) = (m - 1) * (D(m-1) + D(m-2))."""
    d = [0] * (n + 1)
    d[0] = 1
    for m in range(2, n + 1):
        d[m] = (m - 1) * (d[m - 1] + d[m - 2]) % mod
    return d


if __name__ == "__main__":
    c = catalan_table(1000)
    assert c[:10] == [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]
    assert c[1000] == 110961515 == catalan_formula(1000)
    d = derangements(12)
    assert d == [1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841]
    assert derangements(10**6)[-1] == 102701088
    print("catalan and derangement tests passed")
public class CatalanDerangements {
    static final long MOD = 1_000_000_007L;

    static long[] catalanTable(int n) {
        long[] c = new long[n + 1];
        c[0] = 1;
        for (int m = 1; m <= n; m++) {
            long s = 0;
            for (int i = 0; i < m; i++) s = (s + c[i] * c[m - 1 - i]) % MOD;  // product < 2^60
            c[m] = s;
        }
        return c;
    }

    static long power(long base, long exp) {
        long r = 1;
        base %= MOD;
        for (; exp > 0; exp >>= 1, base = base * base % MOD)
            if ((exp & 1) == 1) r = r * base % MOD;
        return r;
    }

    static long catalanFormula(int n) {
        long num = 1, den = 1;
        for (int i = 1; i <= n; i++) {
            num = num * (n + i) % MOD;
            den = den * i % MOD;
        }
        den = den * (n + 1) % MOD;
        return num * power(den, MOD - 2) % MOD;
    }

    static long[] derangements(int n) {
        long[] d = new long[n + 1];
        d[0] = 1;
        for (int m = 2; m <= n; m++) d[m] = (m - 1) * ((d[m - 1] + d[m - 2]) % MOD) % MOD;
        return d;
    }

    public static void main(String[] args) {
        long[] c = catalanTable(1000);
        long[] want = {1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862};
        for (int i = 0; i < want.length; i++) check(c[i] == want[i]);
        check(c[1000] == 110961515L && catalanFormula(1000) == 110961515L);
        long[] d = derangements(12);
        long[] wantD = {1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841};
        for (int i = 0; i < wantD.length; i++) check(d[i] == wantD[i]);
        check(derangements(1_000_000)[1_000_000] == 102701088L);
        System.out.println("catalan and derangement tests passed");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError("test failed");
    }
}
#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

const int64_t MOD = 1'000'000'007LL;

vector<int64_t> catalanTable(int n) {
    vector<int64_t> c(n + 1, 0);
    c[0] = 1;
    for (int m = 1; m <= n; m++) {
        int64_t s = 0;
        for (int i = 0; i < m; i++) s = (s + c[i] * c[m - 1 - i]) % MOD;   // product < 2^60
        c[m] = s;
    }
    return c;
}

int64_t power(int64_t base, int64_t exp) {
    int64_t r = 1;
    base %= MOD;
    for (; exp > 0; exp >>= 1, base = base * base % MOD)
        if (exp & 1) r = r * base % MOD;
    return r;
}

int64_t catalanFormula(int n) {
    int64_t num = 1, den = 1;
    for (int i = 1; i <= n; i++) {
        num = num * (n + i) % MOD;
        den = den * i % MOD;
    }
    den = den * (n + 1) % MOD;
    return num * power(den, MOD - 2) % MOD;
}

vector<int64_t> derangements(int n) {
    vector<int64_t> d(n + 1, 0);
    d[0] = 1;
    for (int m = 2; m <= n; m++) d[m] = (m - 1) * ((d[m - 1] + d[m - 2]) % MOD) % MOD;
    return d;
}

int main() {
    auto c = catalanTable(1000);
    vector<int64_t> want = {1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862};
    for (size_t i = 0; i < want.size(); i++) assert(c[i] == want[i]);
    assert(c[1000] == 110961515 && catalanFormula(1000) == 110961515);
    auto d = derangements(12);
    vector<int64_t> wantD = {1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841};
    assert(d == wantD);
    assert(derangements(1000000)[1000000] == 102701088);
    cout << "catalan and derangement tests passed\n";
    return 0;
}
const MOD = 1_000_000_007;

function mulmod(a: number, b: number): number {
  const hi = (a * (b >>> 16)) % MOD; // exact: < 2^44
  return (hi * 65536 + a * (b & 0xffff)) % MOD; // exact: < 2^47
}

function power(base: number, exp: number): number {
  let r = 1;
  base %= MOD;
  for (; exp > 0; exp = Math.floor(exp / 2), base = mulmod(base, base)) if (exp & 1) r = mulmod(r, base);
  return r;
}

function catalanTable(n: number): number[] {
  const c = new Array<number>(n + 1).fill(0);
  c[0] = 1;
  for (let m = 1; m <= n; m++) {
    let s = 0;
    for (let i = 0; i < m; i++) s = (s + mulmod(c[i], c[m - 1 - i])) % MOD;
    c[m] = s;
  }
  return c;
}

function catalanFormula(n: number): number {
  let num = 1, den = 1;
  for (let i = 1; i <= n; i++) {
    num = mulmod(num, n + i);
    den = mulmod(den, i);
  }
  den = mulmod(den, n + 1);
  return mulmod(num, power(den, MOD - 2));
}

function derangements(n: number): number[] {
  const d = new Array<number>(n + 1).fill(0);
  d[0] = 1;
  for (let m = 2; m <= n; m++) d[m] = mulmod(m - 1, (d[m - 1] + d[m - 2]) % MOD);
  return d;
}

function assert(ok: boolean, msg = "test failed"): void {
  if (!ok) throw new Error(msg);
}

const c = catalanTable(1000);
assert(JSON.stringify(c.slice(0, 10)) === JSON.stringify([1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]));
assert(c[1000] === 110961515 && catalanFormula(1000) === 110961515);
const d = derangements(12);
assert(JSON.stringify(d) === JSON.stringify([1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841]));
assert(derangements(1_000_000)[1_000_000] === 102701088);
console.log("catalan and derangement tests passed");

Real-world uses

  • Path profiling in compilers and profilers. The Ball–Larus algorithm ("Efficient Path Profiling", MICRO 1996) counts, for every node of a function's acyclic control-flow graph, the number of paths from that node to the exit — a counting DP over a DAG in reverse topological order — and uses those counts to give every path a unique integer ID that can be computed with a few additions at run time. Descendants of this idea are used in profile-guided optimisation research and tools.
  • Exact p-values in statistics. The exact null distribution of the Mann–Whitney U (Wilcoxon rank-sum) statistic counts how many ways to choose which ranks belong to the first sample give each value of — a partition-style counting recurrence (Mann and Whitney, 1947). SciPy's scipy.stats.mannwhitneyu(..., method="exact") computes this distribution for small samples rather than using the normal approximation.
  • Option pricing on binomial trees. The Cox–Ross–Rubinstein model (1979) prices options on a recombining tree where the number of up/down paths reaching a node is a binomial coefficient; the backward-induction pricing pass is a Pascal-shaped DP that adds weighted contributions from two children.
  • Query optimisation. The number of bushy join trees for relations is (orderings of the leaves times Catalan tree shapes), which grows so fast that System R (Selinger et al., 1979) restricted itself to left-deep plans and modern optimisers use DP over subsets instead of enumeration. See Bitmask DP for the subset-DP flavour.
  • Matrix-chain products. The number of ways to parenthesise a product of matrices is (CLRS §14.2 uses this to show brute force is exponential), which is why the optimal order is found by Interval DP.
  • Random Secret Santa and "hat-check" systems. The fraction of derangements tends to , so a "shuffle until nobody has their own name" loop needs about shuffles on average — a quick capacity estimate that follows directly from .
  • Counting clusterings. Bell numbers explain why exhaustive clustering is infeasible: 20 items already admit groupings. Practical clustering algorithms (k-means, hierarchical clustering) are heuristics for exactly this reason.
  • Probability of game outcomes. Dice-sum tables like section 9 are how board-game designers and casino mathematicians compute exact odds: the distribution of the sum of dice is the counting DP divided by .

Pitfalls & edge cases

  • Base case for "size zero". ways[0] = 1, p(0) = 1, , , , . The empty object exists exactly once. Setting it to 0 zeroes the whole table.
  • Wrong loop order. Swapping the two loops of the coin DP silently switches between counting sequences and counting multisets. Decide which one the problem wants before coding, and test on a case where they differ (coins {1, 2}, amount 3: 3 sequences, 2 multisets).
  • Wrong inner-loop direction. Upward lets an item be reused; downward forbids reuse. "Distinct parts" with an upward loop counts ordinary partitions.
  • Forgetting to reduce. Reduce after every addition and every multiplication. In Java and C++, a * b of two residues must be done in 64-bit: (long) a * b % MOD. In TypeScript, use a split multiply or BigInt.
  • Negative results from subtraction. (a - b) % MOD may be negative outside Python. Add MOD before the final %.
  • Division modulo . You cannot divide residues directly; multiply by the modular inverse, and only when is prime and does not divide the divisor. with factorials breaks when (then ); use Lucas's theorem or Pascal's table.
  • Double counting through symmetric choices. In tilings, "two horizontal dominoes" must be one case, not "top domino" plus "bottom domino". In set partitions, groups are unlabelled; multiply by only if the problem labels them.
  • Labelled vs unlabelled. Distinguishable dice and items give sequences and -style counts; identical items give partitions. Read the statement twice.
  • Overflow without a modulus. If a problem wants exact counts, check the sizes in Complexity: 64-bit holds Catalan only up to .
  • Recursion depth. A memoised recursion on overflows the call stack in Python and often in Java. Tabulate.

Variations

  • Lucas's theorem: over the base- digits of and , for huge and a small prime .
  • Stirling numbers of the first kind : permutations of elements with exactly cycles. Recurrence (element is inserted after one of the others in an existing cycle, or forms its own cycle).
  • Eulerian numbers: permutations with exactly ascents; .
  • Narayana and Motzkin numbers: refinements and relatives of Catalan (Catalan paths by number of peaks; paths with flat steps allowed).
  • Compositions with restricted parts: ordered sums with parts from a set — section 1 with a different set of faces.
  • Bell triangle: computes without Stirling numbers: each row starts with the last entry of the previous row, and each next entry is the sum of its left neighbour and the entry above that neighbour.
  • Counting with a modulus that is not prime: use Pascal (no division), or the Chinese Remainder Theorem over prime-power factors.
  • Counting paths in a DAG: the general form of all of the above; see DAG DP and Topological Sort.
  • Counting numbers with digit properties: Digit DP.
  • Very large with a linear recurrence (dice, tilings, Fibonacci): Matrix Exponentiation.

Practice ladder

Problems are ordered from easy to hard. Statements are paraphrased; follow the links for the originals.

1. Climbing Stairs (LeetCode 70) — Count ways to climb steps taking 1 or 2 at a time. Teaches the last-step split and ways[0] = 1.

Hint

ways[n] = ways[n-1] + ways[n-2]. It is the domino tiling in disguise.

2. Dice Combinations (CSES 1633) — Ordered sequences of die rolls with sum , modulo . Teaches section 1 exactly.

Hint

Six-term window: ways[s] = sum(ways[s-1..s-6]). Reduce every step.

3. Pascal's Triangle (LeetCode 118) — Build the first rows. Teaches the additive rule and row-by-row tables.

Hint

Each row starts and ends with 1; the inside entries are sums of adjacent entries of the row above.

4. Coin Combinations I (CSES 1635) and Coin Combinations II (CSES 1636) — The same coins and target; the first counts ordered sequences, the second unordered multisets. Teaches loop order better than any explanation.

Solution
MOD = 10**9 + 7


def ordered(coins, x):
    dp = [1] + [0] * x
    for a in range(1, x + 1):
        for c in coins:
            if c <= a:
                dp[a] = (dp[a] + dp[a - c]) % MOD
    return dp[x]


def unordered(coins, x):
    dp = [1] + [0] * x
    for c in coins:
        for a in range(c, x + 1):
            dp[a] = (dp[a] + dp[a - c]) % MOD
    return dp[x]


assert ordered([2, 3, 5], 9) == 8
assert unordered([2, 3, 5], 9) == 3

5. Coin Change II (LeetCode 518) and Combination Sum IV (LeetCode 377) — The unordered and ordered versions again, on LeetCode. Note that LeetCode 377, despite its name, counts ordered sequences.

Hint

518: coins outside. 377: target outside. Check: coins [1, 2, 5], amount 5 → 4; nums [1, 2, 3], target 4 → 7.

6. Unique Binary Search Trees (LeetCode 96) — Number of BST shapes on keys . Teaches the Catalan recurrence by root choice.

Solution
def num_trees(n):
    c = [1] + [0] * n
    for m in range(1, n + 1):
        c[m] = sum(c[root - 1] * c[m - root] for root in range(1, m + 1))
    return c[n]


assert [num_trees(n) for n in range(1, 6)] == [1, 2, 5, 14, 42]

7. Bracket Sequences I (CSES 2064) — Count balanced bracket strings of length modulo , with up to . Teaches when the Catalan DP is too slow and the closed form with factorials is needed.

Hint

Odd → 0. Otherwise with inverse factorials.

8. Number of Dice Rolls With Target Sum (LeetCode 1155) — dice with faces, count outcomes with a given total. Teaches the layered (dice × sum) DP.

Solution
MOD = 10**9 + 7


def num_rolls_to_target(n, k, target):
    dp = [1] + [0] * target
    for _ in range(n):
        new = [0] * (target + 1)
        window = 0                                 # sum of dp[s-k .. s-1]
        for s in range(1, target + 1):
            window += dp[s - 1]
            if s - k - 1 >= 0:
                window -= dp[s - k - 1]
            new[s] = window % MOD
        dp = new
    return dp[target]


assert num_rolls_to_target(1, 6, 3) == 1
assert num_rolls_to_target(2, 6, 7) == 6
assert num_rolls_to_target(30, 30, 500) == 222616187

9. Domino and Tromino Tiling (LeetCode 790) — Tile with dominoes and L-trominoes. Teaches tiling DPs with an extra "jagged edge" state.

Hint

full[n] = full[n-1] + full[n-2] + 2*half[n-1], half[n] = half[n-1] + full[n-2]; or the compact . Check , , .

10. Two Sets II (CSES 1093) — In how many ways can be split into two sets of equal sum? Teaches subset counting (downward loop) and removing a symmetry factor of 2.

Solution

Put in the "second" set by convention; count subsets of with sum . That fixes the labelling, so no division by 2 is needed.

MOD = 10**9 + 7


def two_sets(n):
    total = n * (n + 1) // 2
    if total % 2:
        return 0
    target = total // 2
    dp = [1] + [0] * target
    for x in range(1, n):                          # n itself goes to the other set
        for s in range(target, x - 1, -1):         # downward: each number once
            dp[s] = (dp[s] + dp[s - x]) % MOD
    return dp[target]


assert two_sets(7) == 4
assert two_sets(6) == 0

11. Christmas Party (CSES 1717) — children exchange gifts so nobody gets their own; count the ways modulo . Teaches the derangement recurrence.

Hint

with , ; reduce after the addition and after the multiplication.

12. Distinct Subsequences (LeetCode 115) — Count occurrences of one string as a subsequence of another. Teaches counting over two prefixes; worked in String DP.

Hint

dp[i][j] = dp[i-1][j] + (s[i-1] == t[j-1] ? dp[i-1][j-1] : 0), dp[i][0] = 1.

13. Number of Music Playlists (LeetCode 920) — Playlists of a given length using every one of songs, where a song may repeat only after others have played. Teaches "new item vs reused item" splits with a count of distinct items in the state.

Solution

dp[i][j] = playlists of length using exactly distinct songs. Last song new: choices from dp[i-1][j-1]. Last song old: only old songs are allowed, from dp[i-1][j].

MOD = 10**9 + 7


def num_music_playlists(n, goal, k):
    dp = [[0] * (n + 1) for _ in range(goal + 1)]
    dp[0][0] = 1
    for i in range(1, goal + 1):
        for j in range(1, n + 1):
            dp[i][j] = (dp[i - 1][j - 1] * (n - j + 1)
                        + dp[i - 1][j] * max(j - k, 0)) % MOD
    return dp[goal][n]


assert num_music_playlists(3, 3, 1) == 6
assert num_music_playlists(2, 3, 0) == 6
assert num_music_playlists(2, 3, 1) == 2

Common mistakes & interview follow-ups

"Does order matter?" Ask it out loud before writing code. Interviewers love Coin Change II vs Combination Sum IV because the code differs by one swapped loop. Show the 2-vs-3 example (coins {1, 2}, amount 3) to prove you know which is which.

"Why does the loop order change the answer?" Explain the invariant: coin-outer means "using only the first coin types", which forces a canonical order; amount-outer means "grouped by the last coin", which allows any order.

"Your answer overflows." Use the modulus the problem gives; in Java/C++ cast to 64-bit before multiplying; in JavaScript, use a split multiply or BigInt. If the problem wants an exact count, use Python integers or a big-number class.

"Can you compute for , many queries?" Factorials and inverse factorials in , then per query; explain Fermat's little theorem for the inverse. If the modulus is not prime: Pascal's table (small ) or CRT.

"Prove the Catalan recurrence." First-return decomposition, with the argument that the matching bracket of the first ( is unique — that uniqueness is what makes the cases disjoint.

"Count derangements without the recurrence." Inclusion–exclusion: . Then mention .

" is ." If the recurrence has a fixed number of terms (dice, tilings, Fibonacci), use matrix exponentiation. If it is a convolution like Catalan, use the closed form (and Lucas's theorem if ).

Mistakes interviewers watch for: base case 0 instead of 1; loops in the wrong order or wrong direction; reducing only at the end (overflow happens in the middle); negative residues after subtraction; dividing residues instead of multiplying by an inverse; counting symmetric configurations twice.

Quick quiz

1. Coins {1, 2}, amount 3. How many sequences, how many multisets?

Answer

Sequences: 1+1+1, 1+2, 2+1 → 3. Multisets: {1, 1, 1}, {1, 2} → 2.

2. Why is ways[0] = 1 and not 0 in the dice DP?

Answer

There is exactly one sequence with total 0: the empty one. The one-roll sequence "1" is built from it by appending a 1; with 0, ways[1] would be 0 and every later entry too.

3. Using , compute from the table.

Answer

. (They are 3+3, 3+2+1, 3+1+1+1, 2+2+2, 2+2+1+1, 2+1+1+1+1, 1+1+1+1+1+1.)

4. Compute from and list the groupings.

Answer

: {1}{234}, {2}{134}, {3}{124}, {4}{123}, {12}{34}, {13}{24}, {14}{23}.

5. In the distinct-parts partition DP, what goes wrong if the inner loop runs upward?

Answer

dp[total - part] may already include this part, so a part can be used twice: you count ordinary partitions instead of . For you would get 5 instead of 2.

6. About what fraction of random permutations of 50 elements are derangements?

Answer

About . The convergence is so fast that already agrees to 5 decimal places.

Further reading / sources

  • Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, 2nd ed. (1994) — Ch. 5 (binomial coefficients), Ch. 6 (Stirling numbers, Catalan numbers, Eulerian numbers).
  • Richard P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd ed. (2011) — partitions, set partitions, the "twelvefold way"; and Catalan Numbers (2015).
  • George E. Andrews, The Theory of Partitions (1976) — Euler's distinct/odd parts theorem and the pentagonal number theorem.
  • Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 4th ed. — §14.2 (the Catalan count of parenthesisations), Appendix C (counting).
  • cp-algorithms: Binomial coefficients, Catalan numbers, Inclusion–exclusion.
  • OEIS: A000108 Catalan, A000041 partitions, A000110 Bell, A000166 derangements, A008277 Stirling 2nd kind.
  • Thomas Ball and James R. Larus, "Efficient Path Profiling", MICRO-29, 1996.
  • H. B. Mann and D. R. Whitney, "On a Test of Whether One of Two Random Variables Is Stochastically Larger than the Other", Annals of Mathematical Statistics 18(1), 1947.
  • John C. Cox, Stephen A. Ross, Mark Rubinstein, "Option Pricing: A Simplified Approach", Journal of Financial Economics 7(3), 1979.
  • Fredrik Johansson, "Efficient implementation of the Hardy–Ramanujan–Rademacher formula", LMS Journal of Computation and Mathematics 15, 2012.
  • CSES Problem Set, Dynamic Programming and Mathematics sections.

Lessons: previous — Broken-Profile DP · next — Probability DP · module — Dynamic Programming · course — DSA: Zero to Mastery.

Related Archon pages: Grid & Path DP · String DP · Topological Sort · Recursion & Induction · Probability for Engineers · Combinatorics · Modular Arithmetic · Knapsack · Digit DP · Matrix Exponentiation.