Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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. – Yuval Filmus Aug 28 '12 at 22:13

Ordered Tree

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

Oriented Tree

A tree used to represent hierarchical data. All edges are directed outward from a distinguished root node. also we can say,that oriented tree may contains at most undirected path between vertex,as in the following statment

A polytree or oriented tree is a directed graph with at most one undirected path between any two vertices. In other words, a polytree is a directed acyclic graph for which there are no undirected cycles either.

share|cite|improve this answer
It might be more helpful to explain more details instead of only the definitions. – Gigili May 5 '12 at 14:08
ok i see thanks for advice – dato datuashvili May 5 '12 at 14:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.