Counting the number of bracketings

How many ways are there of bracketing together the composite of three, four, five, six etc. functions? It’s possible to do this by brute force for a small number of functions, for instance there are two ways of bracketing together three functions and five ways of bracketing together four functions. This starts to get tedious with five functions, so can we be more systematic. Suppose our five functions are f : A → B, g : B → C, h : C → D, k : D → E, and l : E → F. Then each way of bracketing the composite l ∘ k ∘ h ∘ g ∘ f has one of the following forms:

(i) l ∘ (some bracketing of k ∘ h ∘ g ∘ f),
(ii) (l ∘ k) ∘ (some bracketing of h ∘ g ∘ f),
(iii) (some bracketing of l ∘ k ∘ h) ∘ (g ∘ f),
(iv) (some bracketing of l ∘ k ∘ h ∘ g) ∘ f.

The number of ways in each of these forms are 5, 2, 2 and 5 respectively. Hence there are 14 ways of bracketing five functions.

What about six or more functions? In all cases each way of bracketing n functions has the form B ∘ A where B is a way of bracketing the first j functions say, and A a way of bracketing the remaining n − j functions. Here j can be any number between 1 and n − 1. (If j = 1 then B is just the first function, and if j = n − 1 then A is just the last function.) Let W_{n} be the number of ways of bracketing n functions, so that W_{1} = 1, W_{2} = 1, W_{3} = 2, W_{4} = 5, W_{5} = 14, etc. For a fixed j there are W_{j}W_{n−j} ways of bracketing n functions as B ∘ A where B contains j functions, and A contains n − j functions. Hence there are W_{1}W_{n−1} + W_{2}W_{n−2} + ⋯ + W_{n−1}W_{1} ways of bracketing n functions. Thus

W_{n} = W_{1}W_{n−1} + W_{2}W_{n−2} + ⋯ + W_{n−1}W_{1} = ∑_{j=1}^{n−1} W_{j}W_{n−j}  (1)

at least for n ≥ 2. (Observe that this formula doesn’t work for n = 1. Why?)

The formula (1) is a recurrence which lets us compute W_{n} for as many n as we like. Thus

W_{6} = W_{1}W_{5} + W_{2}W_{4} + W_{3}W_{3} + W_{4}W_{2} + W_{5}W_{1} = 1 · 14 + 1 · 5 + 2 · 2 + 5 · 1 + 14 · 1 = 42.

Similarly W_{7} = 132, W_{8} = 429, etc.

The question remains as to whether one can get a formula for the W_{n}s. Let F (X) denote the series

W_{1}X + W_{2}X^{2} + W_{3}X^{3} + ⋯ = ∑_{n=1}^{∞} W_{n}X^{n}.

This is called the generating function of the sequence (W_{n}). Then

F (X)^{2} = W_{1}W_{1}X^{2} + (W_{1}W_{2} + W_{2}W_{1})X^{3} + (W_{1}W_{3} + W_{2}W_{2} + W_{3}W_{1})X^{4} + ⋯
= ∑_{n=2}^{∞} (∑_{j=1}^{n−1} W_{j}W_{n−j}) X^{n}.

But by the recurrence (1) this means that

F (X)^{2} = W_{2}X^{2} + W_{3}X^{3} + W_{4}X^{4} + ⋯ = ∑_{n=2}^{∞} W_{n}X^{n} = F (X) − W_{1}X = F (X) − X.

Thus

F (X)^{2} − F (X) + X = 0.

Solving this quadratic equation gives

F (X) = \frac{1 ± \sqrt{1 − 4X}}{2} .

However as F (0) = 0 we must take the minus sign in this, so that

F (X) = \frac{1 − \sqrt{1 − 4X}}{2} .  (2)

To find the W_{n}s we apply the binomial theorem to \sqrt{1 − 4X}. This gives

\sqrt{1 − 4X} = 1 + \frac{1}{2}(−4X) + \frac{1}{2} \frac{−1}{2} \frac{(−4X)^{2}}{2} + \frac{1}{2} \frac{−1}{2} \frac{−3}{2} \frac{(−4X)^{3}}{3!} + ⋯

+\frac{1}{2} \frac{−1}{2} \frac{−3}{2} ⋯ \frac{−(2n − 3)}{2} \frac{(−4X)^{n}}{n!} + ⋯

= 1 − 2X − \frac{4X^{2}}{2} − 3\frac{8X^{3}}{3!} − 3 · 5\frac{16X^{4}}{4!} − ⋯

−3 · 5 ⋯ (2n − 3)\frac{2^{n}X^{n}}{n!} − · · · .

Now note that

3 · 5 ⋯ (2n − 3) = \frac{2 · 3 · 4 ⋯ (2n − 2)}{2 · 4 · 6 ⋯ (2n − 2)} = \frac{(2n − 2)!}{2^{n−1}(n − 1)!}.

Thus the coefficient of X^{n} in the binomial series for \sqrt{1 − 4X} is

−2\frac{(2n − 2)!}{(n − 1)!n!}.

Finally from (2) we get

W_{n} = \frac{(2n − 2)!}{(n − 1)!n!} = \frac{1}{n}\binom{2n − 2}{n − 1} = \frac{1}{2n − 1}\binom{2n − 1}{n}.

RJC 12/2/97