Results 1 to 4 of 4

Math Help - Equation Evaluator

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    1

    Equation Evaluator

    Given a number of terms, n in an equation containing only addition as the only possible operator, find the different number of valid ways in which they can be evaluated. Order of evaluation is controlled by grouping the terms in brackets

    e.g. if n = 4
    it means that there are 4 terms in the equation i.e. something like
    a+b+c+d

    Now the valid ways in which it can be evaluated :
    (a + (b + (c+d)))
    (a + ((b+c) + d))
    ((a+b) + (c+d))
    (((a+b) + c) + d)
    ((a + (b+c)) + d)

    So the answer in this case is 5


    whats the logic for this problem?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by suditi View Post
    Given a number of terms, n in an equation containing only addition as the only possible operator, find the different number of valid ways in which they can be evaluated. Order of evaluation is controlled by grouping the terms in brackets

    e.g. if n = 4
    it means that there are 4 terms in the equation i.e. something like
    a+b+c+d

    Now the valid ways in which it can be evaluated :
    (a + (b + (c+d)))
    (a + ((b+c) + d))
    ((a+b) + (c+d))
    (((a+b) + c) + d)
    ((a + (b+c)) + d)

    So the answer in this case is 5


    whats the logic for this problem?
    I'm not sure. But I think all you are trying to construct structurally different binary trees with 4 (or more generally n end nodes)

    So is there a formula for that? Does it match to the answer you are expecting?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by aman_cc View Post
    I'm not sure. But I think all you are trying to construct structurally different binary trees with 4 (or more generally n end nodes)

    So is there a formula for that? Does it match to the answer you are expecting?

    Yes - It works. (atleast for some initial cases)

    I have the recursive formula

    A_n = \sum_{i=1}^{n-1} A_iA_{n-i} ; A_1=1


    So using this we get A2=1, A3=2, A4=5
    (Not sure how to put this as a function of 'n' though)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2009
    Posts
    10
    If you have n terms there are C_n ways of parenthesizing them, where C_n is the n-th Catalan number. Catalan number - Wikipedia, the free encyclopedia
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: April 11th 2011, 01:17 AM
  2. Partial differential equation-wave equation - dimensional analysis
    Posted in the Differential Equations Forum
    Replies: 3
    Last Post: August 28th 2009, 11:39 AM
  3. Replies: 2
    Last Post: May 18th 2009, 12:51 PM
  4. Replies: 2
    Last Post: April 28th 2009, 06:42 AM
  5. Replies: 1
    Last Post: October 23rd 2008, 03:39 AM

Search Tags


/mathhelpforum @mathhelpforum