Why does the number of balanced delimiter sequences with n pairs follow a convolution recurrence rather than a linear one?

seniorshould knowfreq 36%

answer

the split point is not fixed
match the first opener's closer
inside times the rest, summed
1, 2, 5, 14, 42
Catalan, not Fibonacci

basics

~20 s

Because the split point varies. The closer matching the first opener can fall anywhere, cutting the sequence into an inside part and a remainder, so C(n) is a sum of products C(i)*C(n-1-i) — products of unknowns, not a fixed-length weighted sum.

solid answer

~40 s

Decompose on the closer that matches the first opener. Inside that pair sits a balanced sequence of i pairs; after it sits a balanced sequence of the remaining n-1-i pairs, and i can be anything from 0 to n-1. Every balanced sequence decomposes this way exactly once, giving C(n) = sum over i of C(i)*C(n-1-i) with C(0) = 1 — the Catalan numbers 1, 1, 2, 5, 14, 42. This is not a linear recurrence: the number of terms grows with n, and each term multiplies two unknown earlier values instead of scaling one. So characteristic roots do not apply. A closed form still exists, C(n) = C(2n,n)/(n+1), and the same numbers count binary tree shapes with n nodes.

Decompose on the closer that matches the **first** opener. Inside that pair sits a balanced sequence of `i` pairs; after it sits a balanced sequence of the remaining `n-1-i` pairs, and `i` can be anything from 0 to `n-1`. Every balanced sequence decomposes this way exactly once, giving `C(n) = sum over i of C(i)*C(n-1-i)` with `C(0) = 1` — the Catalan numbers 1, 1, 2, 5, 14, 42. This is not a linear recurrence: the number of terms grows with `n`, and each term multiplies two unknown earlier values instead of scaling one. So characteristic roots do not apply. A closed form still exists, `C(n) = C(2n,n)/(n+1)`, and the same numbers count binary tree shapes with `n` nodes.

code

pseudocode · 10 lines

pseudocode

C[0] = 1

for n from 1 to N:
    C[n] = 0
    for i from 0 to n-1:
        // i pairs inside the first matched pair,
        // n-1-i pairs after its closer
        C[n] = C[n] + C[i] * C[n-1-i]

return C[N]

go deeper

for a junior

Recognise that nested structures are counted by a recurrence rather than a simple product, and that the counts 1, 2, 5, 14, 42 signal that family.

for a middle

Explain the decomposition at the matching closer, why the split index is summed over, and why the result is a product of two unknown counts rather than a scaled one.

for a senior

Show the diagnosis: name why characteristic roots do not apply here, quote the closed form, and turn the roughly 4-to-the-n growth into a statement about what can still be enumerated.

for a principal

Use it as a feasibility gate. A space of nested structures whose count follows this family leaves the enumerable range in the teens, which rules out designs that assume every structure can be listed.

The decomposition that produces the recurrence

Call a sequence of n opening and n closing delimiters balanced when every prefix has at least as many openers as closers and the totals match. Write C(n) for how many there are, with C(0) = 1 for the empty sequence.

For n >= 1, every balanced sequence starts with an opener. Find the closer that matches it — the one where the running balance first returns to zero. That single position cuts the sequence into two pieces:

the part strictly inside the matched pair, which is itself balanced, say with i pairs;
the part after the matching closer, also balanced, with the remaining n - 1 - i pairs.

The cut is unique, so nothing is double counted, and i ranges over 0 .. n-1, so nothing is missed:

C(n) = C(0)*C(n-1) + C(1)*C(n-2) + ... + C(n-1)*C(0)

Running it out: C(1) = 1, C(2) = 1 + 1 = 2, C(3) = 2 + 1 + 2 = 5, C(4) = 5 + 2 + 2 + 5 = 14, then 42, 132, 429. These are the Catalan numbers.

Why this is not a linear recurrence

The characteristic-root method requires three things at once, and this recurrence fails all three.

requirement	a linear homogeneous recurrence	the convolution above
fixed order	looks back a constant number of positions	the number of terms grows with n
linear in the sequence	each term is a constant times one earlier value	each term multiplies two unknown earlier values
constant coefficients	coefficients do not depend on n	there are no fixed coefficients at all

So there is no characteristic polynomial to solve. Be precise about the claim, though: the Catalan numbers do satisfy a first-order recurrence with non-constant coefficients, C(n) = C(n-1) * 2(2n-1)/(n+1), which is easy to verify — from C(3) = 5, that gives 5 * 14/5 = 14. What they satisfy is no fixed-order, constant-coefficient linear recurrence. There is a clean reason: every solution of such a recurrence is a sum of terms p(n)*r^n with polynomial p, whereas the Catalan numbers grow like 4^n / n^(3/2) up to a constant, and a factor of n to the power -3/2 is not a polynomial.

The same count in three costumes

Balanced delimiter sequences of n pairs — split at the matching closer.
Binary tree shapes with n nodes — put i nodes in the left subtree and n-1-i in the right, and sum the products. There are 5 shapes for 3 nodes.
Monotone lattice paths from corner to corner of an n-by-n grid that never cross the diagonal — cut at the first return to the diagonal.

All three are the same recurrence with the same base case, so they are the same numbers. Recognising the shape is the point of the question: a candidate who sees the varying split point reaches for this family instead of trying to force a Fibonacci-style solution.

The closed form and what it says

C(n) = C(2n,n) / (n+1), where C(2n,n) counts all arrangements of n openers and n closers, balanced or not. So exactly 1/(n+1) of all arrangements are balanced — at n = 4, that is 70/5 = 14. The intuitive guess that "about half" are balanced is badly wrong, and gets worse as n grows.

Growth is roughly 4^n divided by n^(3/2), so the sequence is exponential with base 4 and a mild polynomial damping.

The sizing consequence

C(10) = 16,796 — enumerable without thinking.
C(15) = 9,694,845 — already at the edge of what is worth materialising.
C(20) = 6,564,120,420 — out of reach.

That progression is the reason the count is asked for at all: it tells a design review whether a space of nested structures can be walked exhaustively, and the answer stops being yes somewhere in the teens.

What is actually being checked

You decompose at a structural point (the matching closer), not at the midpoint.
You notice the split point is free and therefore summed over.
You do not reach for characteristic roots on a recurrence that is not linear.
You can say what the numbers mean for feasibility rather than only reciting them.

## The decomposition that produces the recurrence Call a sequence of `n` opening and `n` closing delimiters **balanced** when every prefix has at least as many openers as closers and the totals match. Write `C(n)` for how many there are, with `C(0) = 1` for the empty sequence. For `n >= 1`, every balanced sequence starts with an opener. Find the closer that **matches** it — the one where the running balance first returns to zero. That single position cuts the sequence into two pieces: - the part strictly **inside** the matched pair, which is itself balanced, say with `i` pairs; - the part **after** the matching closer, also balanced, with the remaining `n - 1 - i` pairs. The cut is unique, so nothing is double counted, and `i` ranges over `0 .. n-1`, so nothing is missed: `C(n) = C(0)*C(n-1) + C(1)*C(n-2) + ... + C(n-1)*C(0)` Running it out: `C(1) = 1`, `C(2) = 1 + 1 = 2`, `C(3) = 2 + 1 + 2 = 5`, `C(4) = 5 + 2 + 2 + 5 = 14`, then 42, 132, 429. These are the **Catalan numbers**. ## Why this is not a linear recurrence The characteristic-root method requires three things at once, and this recurrence fails all three. | requirement | a linear homogeneous recurrence | the convolution above | |---|---|---| | fixed order | looks back a constant number of positions | the number of terms grows with n | | linear in the sequence | each term is a constant times one earlier value | each term multiplies two unknown earlier values | | constant coefficients | coefficients do not depend on n | there are no fixed coefficients at all | So there is no characteristic polynomial to solve. Be precise about the claim, though: the Catalan numbers **do** satisfy a first-order recurrence with **non-constant** coefficients, `C(n) = C(n-1) * 2(2n-1)/(n+1)`, which is easy to verify — from `C(3) = 5`, that gives `5 * 14/5 = 14`. What they satisfy is no **fixed-order, constant-coefficient** linear recurrence. There is a clean reason: every solution of such a recurrence is a sum of terms `p(n)*r^n` with polynomial `p`, whereas the Catalan numbers grow like `4^n / n^(3/2)` up to a constant, and a factor of `n` to the power `-3/2` is not a polynomial. ## The same count in three costumes - **Balanced delimiter sequences** of `n` pairs — split at the matching closer. - **Binary tree shapes** with `n` nodes — put `i` nodes in the left subtree and `n-1-i` in the right, and sum the products. There are 5 shapes for 3 nodes. - **Monotone lattice paths** from corner to corner of an `n`-by-`n` grid that never cross the diagonal — cut at the first return to the diagonal. All three are the same recurrence with the same base case, so they are the same numbers. Recognising the shape is the point of the question: a candidate who sees the varying split point reaches for this family instead of trying to force a Fibonacci-style solution. ## The closed form and what it says `C(n) = C(2n,n) / (n+1)`, where `C(2n,n)` counts **all** arrangements of `n` openers and `n` closers, balanced or not. So exactly `1/(n+1)` of all arrangements are balanced — at `n = 4`, that is `70/5 = 14`. The intuitive guess that "about half" are balanced is badly wrong, and gets worse as `n` grows. Growth is roughly `4^n` divided by `n^(3/2)`, so the sequence is exponential with base 4 and a mild polynomial damping. ## The sizing consequence - `C(10) = 16,796` — enumerable without thinking. - `C(15) = 9,694,845` — already at the edge of what is worth materialising. - `C(20) = 6,564,120,420` — out of reach. That progression is the reason the count is asked for at all: it tells a design review whether a space of nested structures can be walked exhaustively, and the answer stops being yes somewhere in the teens. ## What is actually being checked - You decompose at a **structural** point (the matching closer), not at the midpoint. - You notice the split point is free and therefore summed over. - You do not reach for characteristic roots on a recurrence that is not linear. - You can say what the numbers mean for feasibility rather than only reciting them.

What fraction of all arrangements of n openers and n closers is balanced?
Exactly `1/(n+1)`. The total number of arrangements is `C(2n,n)` and the balanced count is `C(2n,n)/(n+1)`. At `n = 4` that is 14 balanced out of 70, one in five — so the common guess of one half is wrong immediately and grows worse with `n`.
How many distinct shapes can a binary tree with n nodes take?
The same Catalan count. Fix the root, place `i` nodes in the left subtree and `n-1-i` in the right, and sum the products over all `i` — the identical convolution. Three nodes give 5 shapes, four give 14, and ten give 16,796.
Does the convolution shape mean no closed form exists?
No. A closed form exists, `C(n) = C(2n,n)/(n+1)`; it simply is not reached by characteristic roots. It comes from a counting argument that pairs each unbalanced arrangement with a balanced one, which is why the answer carries a binomial coefficient rather than a power of some root.

saying these in an interview costs you the question

Reaches for characteristic roots on a recurrence whose term count grows with n
Says exactly half of all opener-closer arrangements are balanced
Splits the sequence at the midpoint instead of the matching closer
Claims the count is 2^n because each position is a binary choice
Treats any recurrence that looks backwards as linear

Why does the number of balanced delimiter sequences with n pairs follow a convolution recurrence rather than a linear one?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The decomposition that produces the recurrence

Why this is not a linear recurrence

The same count in three costumes

The closed form and what it says

The sizing consequence

What is actually being checked

▾common follow-ups3 questions

▾red flags5 flags

The decomposition that produces the recurrence

Why this is not a linear recurrence

The same count in three costumes

The closed form and what it says

The sizing consequence

What is actually being checked

answer

go deeper