number of ordered trees

Question

The number of possible ordered trees with 3 nodes A, B, C is:

(a) 16       (b) 12            (c) 6           (d) 10

 

what is ordered tree alignment?

Comments

In case there are n nodes in a tree, then number of ordered trees(binary trees in which nodes are labelled) possible is (2nCn/(n+1))*n!
so according to the problem the answer should be 60

---

(2nCn/(n+1))*n!=30 not 60 for n=3.

---

yes 30 is right.none of the  above is right

Answer 1

possible ordered tree are 30(which all will be binary) as there will be 5 possible structure and each such structure can be filled in 3!=6 ways

Answer 2

A tree where the children of each node have a designated order (not necessarily based on their value) and can be referred to specifically.

The tree may be of depth 1 or 2. If depth is 2, we have 6 possibilities( 3! ). If the depth is 1, the root maybe one of the three nodes and for each root, 2 trees are possible.

Therefore, 6(depth = 1) + 6(depth = 2)  = 12.

Comments

The formula is a little different from the one used for calculating number of unlabeled binary trees. Here the size of tree is (n+1) whereas in that formula the size is n. This formula tells the number of structures that are possible for making ordered trees.

---

I just read it somewhere, ordered trees are binary search trees(bst). The definition above mentioned also satisfies for bst. So, if we consider ordered trees as bsts, the answer must be 5 and not 12.

---

Just to support possible number of ordered trees, posting below image

Answer 3

I read all the answers and none projects the crux the of the problem. 

Only number of ordered trees has been asked and no where is it mentioned whether it's binary or ternary etc.

The formula n!*(2nCn)/(n+1) is for number of ordered binary trees. According to this the no. of trees should be 5 and ordering each tree

gives us 5*3!=30 trees. as shown below:-

BUT that's not the question !!! 

The only trees possible are trees with height 1 and trees with height 2. 

 THEREFORE THE ANSWER IS 12 TREES.

Comments

Can someone explain how does the formula

n!*(2nCn)/(n+1)

Obtain.... practically?

---

@Patty6397 sir,

Nice explanation.

answer will be 30 in case they ask ordered binary tree.

Answer 4

b)12

The tree maybe of depth 2 or 1. If depth is 2, we have 6 possible trees. This is because one of the 3 nodes A, B, C may be the root and the next level may be one of the remaining 2 nodes. If the depth is 1, the root maybe one of the 3 nodes A, B, C. Corresponding to a root, say A, 2 trees are possible as this.

                                        A                 and                  A

                              B                  C                      C                B

This gives us 6 more possibilities.

Total = $12$