reflection principle and binary operator

Apr 2009
678
140
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 !
 
Last edited:

emakarov

MHF Hall of Honor
Oct 2009
5,577
2,017
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\).
 
  • Like
Reactions: aman_cc