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 !

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 !

Last edited: