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 in some communities. They should not be confused with cardinal trees, also called $k$-ary trees.

  • 1
    $\begingroup$ What is an ordinal tree? $\endgroup$
    – Kaveh
    May 24, 2016 at 14:57
  • 2
    $\begingroup$ "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] $\endgroup$
    – J..y B..y
    May 24, 2016 at 22:40
  • 2
    $\begingroup$ What’s the difference between a “list” and an “array” here? As far as I can see, both are just (ordered) sequences. $\endgroup$ May 25, 2016 at 12:34
  • 1
    $\begingroup$ In data structure terms, your ordinal trees are sometimes called Rose Trees, 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). $\endgroup$
    – Joseph
    May 26, 2016 at 23:47
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 4, 2016 at 17:25


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.