Parentheses Combination with addition

Question

I have an interesting combination problem and I'm kinda stuck

Lets define a function p(xn) which returns the number of '()' for the equation x Now x can only be in the form x1 + x2 + x3 ... xn This function is defined for n >=2

Examples:

P(x2) = (x1 + x2) = 1

p(x3) = ((x1 + x2) + x3) and (x1 + (x2 + x3))

p(x4) =

((x1 + x2) + (x3 + x4))

(((x1 + x2) + x3) + x4)

((x1 + (x2 + x3)) + x4)

(x1 + ((x2 + x3) + x4))

(x1 + (x2 + (x3 + x4)))

and so on Notice (x1 + (x2 + x3) + x4) is not a valid example there has to be one ()'s for each +

Now, Im trying to come up with a formula for P that'll determine the number of combinations I'm not sure if there is a fixed formula or a recursive definition that depends on its previous terms. Can you guys help me figure out the formula?

Answer 1

Basically you are looking to count the number of unique binary expression trees where the nodes are summations and the leaves are x₁ to x_n. Let's call this number P(n).

You can choose any of the n-1 summations as the root node. Let's choose the k'th summation. There are k variables to the left of the root, so you can organize the left subtree in P(k) ways. There are n-k variables to the right, so the right subtree can be organized in P(n-k) ways. So, in total you can organize the tree in P(k)P(n-k) different ways.

Since you could choose k freely from 1 to n-1, the total number with which you can organize the expression tree with n leaves is:

P(n) = P(1)P(n-1) + P(2)P(n-2) + ··· + P(n-2)P(2) + P(n-1)P(1)

As noted by @DSM in the comments this recurrence relation generates the Catalan numbers. There is a closed form solution, but it's a little tricky to derive from the recurrence formula. You can find several proofs of the formula in the Wikipedia article for Catalan numbers. The solution is:

P(n) = C(2n,n)/(n+1)                where C(n,k) = n! / (k!(n-k)!)