# reflection principle and binary operator

• Jul 30th 2010, 04:05 AM
aman_cc
reflection principle and binary operator
Consider a computation like

a1 + a2 + a3 + ...... + an

Now to perform this you need to fully paranthesize the sum. Question is - how many ways can you fully paranthesize this. Let this be called Pn (let me call this problem 1)

For e.g. for n = 3 we can do it in 2 ways
((a1 + a2) + a3)
(a1 + (a2 + a3))

Now, I have been able to derive the following recurrence

$\displaystyle P_n = \sum_{k=1}^{n-1} P_k.P_{n-k}$

I read that this problem can be solved using reflection principle. I have used reflection princile to solve the problems like - how many ways you can permute a sequence of n '(' and n ')' so that it forms a valid matched pattern. (Which is nothing but catalan number) (let me call this problem 2)

I know how to solve problem 2 using reflection principle.

For problem 2 also I have been able to derive a recurrence relation which is similar to the one delrived for Problem 1 above (with an adjustment to sub-script).

So yes - I can interpret the recurrence relation for the problem 1 - convert it into a problem of problem type 2 and then solve this using reflection principle. And hence I have solved problem 1 using reflection principle.

But apart from the similarity of the recurrence relations of the two problems is there any other combinatorial argument as to why these problem are similar? More specifically can problem 1 be solved without deriving its recurrence relation and rather using reflection principle directly.

Hope I was clear in my explanation !
• Jul 30th 2010, 10:04 AM
emakarov
If one takes a fully parenthesized sum of $\displaystyle n$ terms and removes actual terms and plus signs, then one gets a well-matched string of $\displaystyle n-1$ pairs of ('s and )'s. Moreover, different parethetizations yield different strings and all strings can be obtained in this way. Thus, $\displaystyle P_n=C_{n-1}$ ($\displaystyle C_n$ is the $\displaystyle n$th Catalan number).

To show the first fact, assume that $\displaystyle S_n$ is a fully parenthesized sum of $\displaystyle n$ terms and proceed by (strong) induction on $\displaystyle n$ starting with $\displaystyle n=1$.
• Aug 3rd 2010, 01:27 AM
aman_cc
Thanks for your induction idea !