1
$\begingroup$

Is computing the number of ordinal trees (also known as "Rose trees") with $n$ nodes, of depth $d$, with $l$ leaves an open problem?

I assumed at first that it was a known results but I could not find it, and neither did the various combinatorics colleagues 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.

(Reposted from https://cstheory.stackexchange.com/questions/34824/number-of-ordinal-trees-with-n-nodes-of-depth-d-with-l-leaves because it seems that theoretical computer science was not the appropriate community for this question.)

$\endgroup$

closed as off-topic by davidlowryduda Jun 2 '16 at 5:39

  • This question does not appear to be about math within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. You might want to let your colleague know that cross-posting on multiple SE sites is against the SE rules. $\endgroup$ – D.W. May 31 '16 at 21:52
  • $\begingroup$ I'm voting to close this question as off-topic because it has been asked and answered on another SE site. $\endgroup$ – davidlowryduda Jun 2 '16 at 5:39
  • $\begingroup$ @D.W. : sorry for that. Shall I close the question myself if it is inapropriate in thie community? Note that it was NOT answered in the Theoretical Computer Science community, and that a colleague suggested that even though it has applications in TCS, the problem itself is in Combinatorics. $\endgroup$ – Jeremy Jun 2 '16 at 9:51

Browse other questions tagged or ask your own question.