Results 1 to 3 of 3

Math Help - The number of possible binary trees with n nodes

  1. #1
    Newbie
    Joined
    Sep 2010
    Posts
    12

    The number of possible binary trees with n nodes

    If T(n) is the total number of binary tree configurations with n nodes (so T(0) = 1, T(1) = 1, T(2) = 2, T(3) = 5, T(4) = 14. This is pretty easy to conceptualize, if you imagine that for a binary tree with n nodes, the root has two subtrees which can have 0 to n-1 nodes. So the total number of possible trees is:

    T(n) = \sum_{i=0}^{n-1} T(i)T(n-1-i)

    That much I've figured out. The problem now is how to find a closed-form solution for T(n). After calculating some numbers I've found that the sequence matches the "catalan sequence":

    \frac{(2n)!}{n!(n+1)!}

    But how? I just have no idea. Not even sure where to start. Any suggestions?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Sep 2010
    Posts
    12
    Guess I spoke too soon. The recurrence relation I derived turns out to be an alternate definition of the catalan numbers, which I think should be sufficient. I still would be curious to see a derivation from the recursive definition to the closed form (factorial) equation, though. If anyone knows how to do that please let me know.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    You can find a derivation here:

    Catalan number - Wikipedia, the free encyclopedia

    (Five derivations, actually.)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Binary trees
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 4th 2011, 07:43 AM
  2. Binary Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 6th 2009, 12:05 PM
  3. Binary Trees
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 28th 2009, 02:38 AM
  4. Number of nodes in a tree
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 10th 2009, 06:02 AM
  5. binary trees
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 18th 2006, 07:31 PM

Search Tags


/mathhelpforum @mathhelpforum