Results 1 to 3 of 3

Math Help - reflection principle and binary operator

  1. #1
    Super Member
    Joined
    Apr 2009
    Posts
    677

    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


    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 by aman_cc; July 30th 2010 at 05:01 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,506
    Thanks
    765
    If one takes a fully parenthesized sum of n terms and removes actual terms and plus signs, then one gets a well-matched string of n-1 pairs of ('s and )'s. Moreover, different parethetizations yield different strings and all strings can be obtained in this way. Thus, P_n=C_{n-1} ( C_n is the nth Catalan number).

    To show the first fact, assume that S_n is a fully parenthesized sum of n terms and proceed by (strong) induction on n starting with n=1.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Thanks for your induction idea !
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. linear operator and reflection
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: October 15th 2011, 03:46 PM
  2. Schwarz reflection principle
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: May 26th 2010, 11:06 AM
  3. Random walks and the reflection principle.. HELP!
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: May 19th 2010, 03:09 PM
  4. Momentum Principle and Energy Principle Problem
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: October 4th 2009, 01:42 AM
  5. Schwarz reflection principle
    Posted in the Calculus Forum
    Replies: 2
    Last Post: February 21st 2009, 09:07 PM

Search Tags


/mathhelpforum @mathhelpforum