A Twenty-Step Tree Has 231 Nodes, or 2,097,151

Whether an up move followed by a down move lands where a down move followed by an up move lands decides between a quadratic node count and an exponential one, and at twenty steps the gap is a factor of 9,078.6. Both sums carry N+1 terms rather than N, because a twenty-step tree has twenty-one dates on it, and the off-by-one costs the entire final row. The article also states the recombination hypothesis exactly, which is weaker than the usual ud = 1.

Twenty steps of a price that can only go up or down. How many nodes does the resulting tree carry? The question has two answers, 231 and 2,097,151, and which one applies depends on a single multiplication. Getting the difference wrong is the difference between a calculation that finishes before you look up and one that does not finish at all.

No option is priced anywhere below. This is pure counting, and it is worth doing carefully because the count is what decides whether a lattice method is usable.

Two trees, one depth

Fix what is being counted first, since two reasonable readings of “node” give completely different comparisons.

Node, and recombination

A node is a distinct pair (date, price). The starting point counts as one, and the tree is counted through step $N$ inclusive. The tree recombines when an up move followed by a down move lands on the same price as a down move followed by an up move, so that two histories can share a node.

Counting only the last row instead would give $N+1$ against $2^N$ , which is 21 against 1,048,576, a different comparison with a different moral. Everything here counts the whole tree, which is the number that matters because a backward induction visits every node once.

Fig. 1 — Four steps is already enough to see the shape of the difference. The left tree adds one node per row; the right one doubles.

Twenty steps, twenty-one dates

Here is the slip that costs most people the question, and it happens before any formula is written. A tree with $N$ steps has $N+1$ dates on it, because time zero is a date. So both sums below run over $N+1$ terms rather than $N$ , and dropping the extra term is not a rounding error.

On the recombining side, counting twenty rows instead of twenty-one gives $20 \cdot 21/2 = 210$ , which is short by 21. Those 21 missing nodes are the entire final row, the one every terminal payoff lives on. On the other side the same slip gives $2^{20} - 1 = 1{,}048{,}575$ , and since $2{,}097{,}151 = 2 \times 1{,}048{,}575 + 1$ , the answer is out by a factor of two.

The cheapest protection is to test any candidate formula at $N = 1$ . One step of a recombining tree has a root and two children, so three nodes. The correct formula gives $2 \cdot 3/2 = 3$ , and the off-by-one version gives $1 \cdot 2/2 = 1$ . A hand check that takes four seconds separates them.

Why each new row adds a single node

In a recombining tree the price after $k$ steps depends only on how many of those steps were up moves, so row $k$ holds the values $j = 0, 1, \dots, k$ and has exactly $k+1$ nodes. Adding a step adds one node, never two, because every interior price on the new row was already reachable. Summing the rows is the oldest sum there is:

\sum_{k=0}^{N} (k+1) \;=\; \sum_{k=1}^{N+1} k \;=\; \frac{(N+1)(N+2)}{2}

(1)

At $N = 20$ that is $21 \cdot 22/2 = 231$ . The count is a triangular number, which is exactly what the picture looks like.

The tree that never folds

Suppose instead that every history is its own state, which is what happens when the move sizes depend on the path taken to get there. Then row $k$ holds one node per history of length $k$ , which is $2^k$ , and the total is a geometric sum:

\sum_{k=0}^{N} 2^{k} \;=\; 2^{N+1} - 1

(2)

At twenty steps that is $2^{21} - 1 = 2{,}097{,}151$ . Comparing the two at the same depth:

\frac{2^{N+1}-1}{(N+1)(N+2)/2} \;\Big|_{N=20} \;=\; \frac{2{,}097{,}151}{231} \;=\; 9078.6

(3)

Fig. 2 — A straight line on a logarithmic axis is exponential growth. The gap at twenty steps is a factor of 9,078.6, and at thirty steps it is over four million.

What the gap buys you

The ratio in (3) is not fixed. It grows without bound, because a quadratic is being divided into an exponential. At thirty steps the counts are 496 and 2,147,483,647, a factor of over four million. A thousand-step lattice, which is an ordinary thing to want, holds 501,501 nodes; the same depth without recombination would hold a number with 302 digits.

Practically this is the difference between a method and a wish. Recombination is also what makes refinement cheap: doubling the number of steps multiplies the work by roughly four rather than squaring it, so accuracy is bought at a predictable price.

A trinomial lattice, where the price can also stay put, keeps the same character. Its rows hold $1, 3, 5, \dots, 2N+1$ nodes, which sums to $(N+1)^2$ , so 441 at twenty steps. Still quadratic, and still nothing like the fan.

When a lattice refuses to recombine

It is worth being exact about the hypothesis, because it is weaker than the usual statement of it. If the up and down factors are the same at every node, the price after $k$ steps is $S_0 u^{j} d^{\,k-j}$ , which depends only on the number of up moves and not on their order. The tree recombines whatever $u$ and $d$ are. The familiar condition $ud = 1$ does something narrower and useful: it puts the recombined middle of the lattice exactly back on the starting price, so the levels stay centred as the tree deepens.

What genuinely breaks recombination is a move size that depends on where you are or how you got there. Two cases matter. A payoff that depends on the path, such as an average or a running maximum, forces the state to carry more than the current price, and the extra coordinate multiplies the node count. And a model whose step depends on the realised history, rather than on the current level alone, gives two different prices to up-then-down and down-then-up. In both cases the fan in equation (2) is what you are actually paying for, and recovering a workable count means enlarging the state deliberately rather than hoping the branches meet.

Sources and further reading

Wikipedia: Binomial options pricing model, for the lattice this counting describes.
Wikipedia: Triangular number for equation (1), and Geometric series for equation (2).
John Cox, Stephen Ross and Mark Rubinstein, “Option Pricing: A Simplified Approach”, Journal of Financial Economics7 (1979), 229–263, where the centred convention $ud = 1$ was introduced.

Both counts were verified by construction rather than by formula before publication. The recombining lattice was built as a set of exact rational prices with $u = 2$ and $d = 1/2$ , so that up-then-down and down-then-up collide exactly rather than within a floating-point tolerance, and its size matched equation (1) at every depth from 0 to 20 with the rows checked one at a time. The other tree was built by enumerating every history to depth 16, which is 131,071 nodes, and matched equation (2) at every depth.