2
$\begingroup$

An ordered tree (also known as ordinal tree and plane tree) is a rooted tree in which the children of each node are ordered. It is known that the number of the ordered tree with $n$ edges is the $n$'the Catalan number $C_n$.

I am interested in the number of ordered trees in which the number of children of each node is at most $k$ (possibly less than $k$) for some small parameter $k$ (I am particularly interested in the case of $k=4$).

The special case of ordered trees with $k=2$ is called 0-1-2 trees (each node has 0, 1, or 2 children). It is known that the number of such trees with $n$ edges is the $n$'th Motzkin number $M_n$. For $k>2$, the number of ordered trees should lie between $M_n$ and $C_n$. We know $\log_2(M_n) = 1.585 n - o(n)$ and $\log_2(C_n) = 2n - o(n)$. I am interested in the constant behind $n$ for $k=4$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.