Results 1 to 2 of 2

Math Help - Permutation of Tree Construction

  1. #1
    twfx
    Guest

    Permutation of Tree Construction

    Question:
    ------------
    Given N nodes, with one node is fixed as root. How many tree, p, could be built?

    Condition:
    ------------
    a) The trees can be balanced/unbalanced, as long as All nodes MUST in the tree.
    b) Every node (except the root) connected to different set of child node(s) in its child tree is considered unique. However if two or more leaf node(s) connected to the same parent, position is not important.
    Meaning, for N=3, with N1 is root

    N1->N2->N3 and N1->N3->N2 is considered different tree.
    But, the below is considered same tree.

    N1 N1
    | | | |
    v v v v
    N2 N3 N3 N2


    c) To simplify, consider there exist only 1 root node, the rest of nodes are non-root.

    Eg:
    ----
    For N=3, p = 3
    For N=4, p= 16
    For N=5, p=125

    I have manually calculated N={3,4,5}. However,
    1) Is there a maths formula to solve this problem?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    earboth's Avatar
    Joined
    Jan 2006
    From
    Germany
    Posts
    5,812
    Thanks
    116
    Quote Originally Posted by twfx View Post
    Question:
    ...
    Eg:
    ----
    For N=3, p = 3
    For N=4, p= 16
    For N=5, p=125

    I have manually calculated N={3,4,5}. However,
    1) Is there a maths formula to solve this problem?
    Hello,

    you have
    For N=2, p = 1
    For N=3, p = 3
    For N=4, p= 16
    For N=5, p=125

    According to your result you probably get:

    p = N^{N-2}

    I'm only guessing. I didn't find a proof for this formula.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Construction...
    Posted in the Geometry Forum
    Replies: 1
    Last Post: November 2nd 2010, 12:13 AM
  2. Tree/Permutation - Urn problem
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 26th 2009, 02:52 AM
  3. Construction help
    Posted in the Geometry Forum
    Replies: 2
    Last Post: April 27th 2009, 05:21 AM
  4. I need help with a construction.
    Posted in the Geometry Forum
    Replies: 1
    Last Post: April 26th 2009, 12:28 PM
  5. construction
    Posted in the Geometry Forum
    Replies: 1
    Last Post: July 30th 2008, 04:13 AM

Search Tags


/mathhelpforum @mathhelpforum