<p><strong>What is the number of ordinal trees (aka rose trees) with $n$ nodes, of depth $d$, with $l$ leaves?</strong></p>

<p>I thought that it was a known results but I could not find it, and neither did the various combinatorics whom I asked. It seems that it should be computed using generating functions, but beside the fact that such a generating function would have two variables, there is also the fact that the number of nodes and of leaves are additive between the various children of a tree, whereas the depth of a tree is one plus the max of the depth of each of its children: I don't know how to express those in a generating functions. </p>

<p>The reason I ask is that, when considering (some variant of) the cartesian tree of a multiset in order to support Range Minimum Queries on it, the number of runs in the multisets corresponds exactly to the number of leaves, and the number of distinct elements in the multiset gives a bound on the depth of the ordinal tree: the logarithm of the number of such trees will give a lower bound on the space usage of any compressed index supporting Range Minimum Queries, in the worst case over multisets of size $n$ with $l$ runs and $d$ distinct values. (And, with only a bit more work I believe, an asymptotically tight upper bound.) </p>

<p>Demaine et al define an ordinal tree as "a rooted tree of arbitrary degree in which the children are ordered" <a href="http://erikdemaine.org/papers/MaryTrees_Algorithmica/paper.ps" rel="nofollow">http://erikdemaine.org/papers/MaryTrees_Algorithmica/paper.ps</a>. It seems that they are also called <a href="https://en.wikipedia.org/wiki/Rose_tree" rel="nofollow">Rose trees</a> in some communities. They should not be confused with cardinal trees, also called $k$-ary trees.</p>

CC BY-SA 3.0
2016-05-24T14:57:40.380Z
What is an ordinal tree?
Kaveh
CC BY-SA 3.0
2016-05-24T22:40:16.597Z
"An ordinal tree (see, e.g., [Geary et al. 2004; Benoit et al. 2005]) is an arbitrary rooted tree where the children of each node are ordered." [www.csie.ntu.edu.tw/~hil/paper/talg07.pdf]
J.y B.y
CC BY-SA 3.0
2016-05-25T12:34:56.483Z
What’s the difference between a “list” and an “array” here? As far as I can see, both are just (ordered) sequences.
Emil Jeřábek
CC BY-SA 3.0
2016-05-26T12:06:47.540Z
An array can be accessed by position, and some positions can be empty. For instance, a node in a binary tree can have a right child without having a left child.

A list (in general) does not have "empty elements". An ordinal tree has only a list of children, none of them empty (but the list itself can be empty).
J.y B.y
CC BY-SA 3.0
2016-05-26T23:47:02.083Z
In data structure terms, your ordinal trees are sometimes called [Rose Trees](https://en.wikipedia.org/wiki/Rose_tree), which algebraicly are labeled ordered unranked trees. I would call a cardinal tree a k-ary tree. I too found your array/list distinction a bit confusing at first; the point is that an array here is fixed size (doesn't grow, same size at all nodes) while a list is unbounded (no upper limit on number of children).
Joseph
CC BY-SA 3.0
2016-05-28T14:50:38.387Z
@Joseph : thanks, I updated the description accordingly: I was not aware of this alternate name. I learned the terms of "ordinal trees" and "cardinal trees" from Ian Munro's data structure class at the university of Waterloo from 10 years ago: I thought it was the well-accepted name for both.
J.y B.y
CC BY-SA 3.0
2016-06-04T17:25:00.610Z
Since you're only interested in a lower bound for the log of this number, you could try the crude approximation of just counting the number of ordered binary trees with the given $n,l,d$ settings. Restricting to $n = 2l-1$ (so every internal node has two children) seems like it might be helpful in that direction.
Andrew Morgan
CC BY-SA 3.0
2016-06-07T16:39:28.843Z
Thanks @AndrewMorgan: I will look into it when I will be back from my conference(s).
J.y B.y
<tree>
Number of ordinal trees with n nodes, of depth d, with l leaves
J.y B.y
# Number of ordinal trees with n nodes, of depth d, with l leaves

(Asked by: username_0 on 2016-05-24)

**What is the number of ordinal trees (aka rose trees) with $n$ nodes, of depth $d$, with $l$ leaves?**

I thought that it was a known results but I could not find it, and neither did the various combinatorics whom I asked. It seems that it should be computed using generating functions, but beside the fact that such a generating function would have two variables, there is also the fact that the number of nodes and of leaves are additive between the various children of a tree, whereas the depth of a tree is one plus the max of the depth of each of its children: I don't know how to express those in a generating functions.

The reason I ask is that, when considering (some variant of) the cartesian tree of a multiset in order to support Range Minimum Queries on it, the number of runs in the multisets corresponds exactly to the number of leaves, and the number of distinct elements in the multiset gives a bound on the depth of the ordinal tree: the logarithm of the number of such trees will give a lower bound on the space usage of any compressed index supporting Range Minimum Queries, in the worst case over multisets of size $n$ with $l$ runs and $d$ distinct values. (And, with only a bit more work I believe, an asymptotically tight upper bound.)

Demaine et al define an ordinal tree as "a rooted tree of arbitrary degree in which the children are ordered" <http://erikdemaine.org/papers/MaryTrees_Algorithmica/paper.ps>. It seems that they are also called [Rose trees](https://en.wikipedia.org/wiki/Rose_tree) in some communities. They should not be confused with cardinal trees, also called $k$-ary trees.

**Tags:** tree
> **Comments:**
> **username_1**: What is an ordinal tree?  
> **username_0**: "An ordinal tree (see, e.g., [Geary et al. 2004; Benoit et al. 2005]) is an arbitrary rooted tree where the children of each node are ordered." [www.csie.ntu.edu.tw/~hil/paper/talg07.pdf]  
> **username_2**: What’s the difference between a “list” and an “array” here? As far as I can see, both are just (ordered) sequences.  
> **username_0**: An array can be accessed by position, and some positions can be empty. For instance, a node in a binary tree can have a right child without having a left child.  A list (in general) does not have "empty elements". An ordinal tree has only a list of children, none of them empty (but the list itself can be empty).  
> **username_3**: In data structure terms, your ordinal trees are sometimes called [Rose Trees](https://en.wikipedia.org/wiki/Rose_tree), which algebraicly are labeled ordered unranked trees. I would call a cardinal tree a k-ary tree. I too found your array/list distinction a bit confusing at first; the point is that an array here is fixed size (doesn't grow, same size at all nodes) while a list is unbounded (no upper limit on number of children).  
> **username_0**: @Joseph : thanks, I updated the description accordingly: I was not aware of this alternate name. I learned the terms of "ordinal trees" and "cardinal trees" from Ian Munro's data structure class at the university of Waterloo from 10 years ago: I thought it was the well-accepted name for both.  
> **username_4**: Since you're only interested in a lower bound for the log of this number, you could try the crude approximation of just counting the number of ordered binary trees with the given $n,l,d$ settings. Restricting to $n = 2l-1$ (so every internal node has two children) seems like it might be helpful in that direction.  
> **username_0**: Thanks @AndrewMorgan: I will look into it when I will be back from my conference(s).  

---

## 0 answers

