Nested lists

One can think of structures that annihilate in pairs as being like parentheses or other delimiters that come in pairs, as in the picture below.

A string of balanced parentheses is analogous to a nested Mathematica list such as {{{}, {{}}}, {}}. The Mathematica expression tree for this list then has a structure analogous to the nested pattern in the picture.

The set of possible strings of balanced parentheses forms a context-free language, as discussed on page 939. The number of such strings containing 2n characters is the n^th Catalan number Binomial[2n, n]/(n + 1) (as obtained from the generating function (1 - Sqrt[1 - 4x])/(2x)). The number of strings of depth d (and thus taking d steps to annihilate completely) is given by c[{n, n}, d] - c[{n, n}, d - 1] where

c[{_, _}, -1] = 0; c[{0, 0}, _] = 1; c[{m_, n_}, _] := 0 /; n > m;

c[{m_, n_}, d_] := Sum[c[{i, j}, d], {i, 0, m - 1}, {j, m - d, n - 1}]

Several types of structures are equivalent to strings of balanced parentheses, as illustrated below.