[Enumerating] possible expressions
LeafCount[expr] gives the number of symbols that appear anywhere in an expression, while Depth[expr] gives the number of closing brackets at the end of its functional representation—equal to the number of levels in the rightmost branch of the tree representation. (The maximum number of levels in the tree can be computed from expr /. _Symbol 1 //. x_[y_] 1 + Max[x, y].)
With a list s of possible symbols, c[s, n] gives all possible expressions with LeafCount[expr] n:
c[s_, 1] = s; c[s_, n_] := Flatten[Table[Outer[#1[#2] &, c[s, n - m], c[s, m]], {m, n - 1}]]
There are a total of Binomial[2n - 2, n - 1] Length[s]n/n such expressions. When Length[s] 1 the expressions correspond to possible balanced sequences of opening and closing brackets (see page 989).
