Bracketing Problem, and a useful summation identity.

January 29th, 2004 ~ Posted in: General

I discovered this summation identity naturally– meaning, motivated by my own investigation, and without anticipation of the final result, even though I am sure I’ve seen it before:

\sum_{n=0}^k \binom{k}{n} x^n (1-x)^{k-n} = 1

It seems to work for any complex number, including zero. I have a proof for real x in [0,1], but that is based on probability theory, so I don’t have a handle yet on the general case. I’ve submitted it to the UHME mailing list, but I don’t think anyone will really work at it.

Update: I just realized where I’ve seen that identity before– it’s just an expansion of 1^n using the binomial theorem. Silly me…

The Bracketing Problem (cf. MathWorld) can be stated as such:

Let \star be a non-associative, non-commutative binary operation. Given an ordered n-tuple of operands, (x_1, x_2, \ldots, x_n), indicate using parentheses all possible \star-products that can be found by varying the sequence in which the operands are combined.

For example, a 4-tuple yields five unique bracketings:

(x(x(xx))), (x((xx)x)), ((xx)(xx)), (((xx)x)x), ((x(xx))x)

It can be shown (not yet by me :) ) that there are C_{n-1} bracketings for an n-tuple, where C_n is the n-th Catalan number: \frac{1}{(n+1)!} \binom{2n}{n}.

The question of how to write a ‘Catalan generator’– a program that generates all bracketings for a given number– came up on sci.math. Here’s an algorithm that is straightforward to implement:

To find the bracketings for n, form all pairs (i,j) where 0<i ,j and i+j=n. For each of these pairs, find B_i = the set of i bracketings and B_j = the set of j bracketings, then find B_{(i,j)} = the cartesian product of B_i and B_j. The base case is B_1=\{x\}, where x is just a generic variable as above. Then B_n, the set of bracketings for n, is the union of B_{(i,j)} over all the (i,j) pairs.

General ~

One Response to “Bracketing Problem, and a useful summation identity.”

This entry was posted on Thursday, January 29th, 2004 at 1:38 pm and is filed under General. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply