2
$\begingroup$

I have this confusion regarding ordered and oriented trees. I know they are both rooted and in ordered trees, the order is important. So lets say I have four nodes

1,2,3,4 then it is given that the number of ordered trees is 5. How come this is true. I can create the following trees. Lets suppose the root is 1

  1            1          1          1 | | |        | | |      | | |      | | | 2 3 4        3 2 4      4 2 3      2 4 3   1   1  |   |   2   3   |   |  3   2  |   |  4   4 

and the list goes on. I didn't understand this part. For oriented trees, I can say that the first four trees are equivalent and same and the bottom two trees are equali

  • 0
    According to Cayley's formula, the number of oriented trees on $n$ vertices is $n^{n-1}$ (this is $n$ times the number given by the formula, since there are $n$ choices for the root). The number of ordered trees is surely larger.2012-08-28

1 Answers 1