什么是可能的有序树有N个节点的总数是多少？ [英] What are the total number of possible ordered trees with N nodes?

问题描述

例如对于N = 3，我们可以列出这些都容易找到，但要求任意N值我现在面临的问题。

For example for N=3, we can find easily by listing them all, but when asked for any arbitrary N value I am facing problem.

推荐答案

如果你正在寻找二叉树那么，作为mcdowella表示，选择（2N，N）/（N + 1）（加泰罗尼亚号）就是答案。

If you are looking at binary trees then, as mcdowella said, Choose(2n,n)/(n+1) (Catalan number) is the answer.

如果您正在寻找在任意树那么它可能是ñ。 ñ^（N-2）= N ^（N-1），但我不能完全确定。 Prufer的算法中告诉我们，有n ^（N-2）标记的树任何一个节点可以由根，因此，我们得到的数量n ^（N-1）。

If you are looking at arbitrary trees then it is probably n. n^(n-2) = n^(n-1), but I am not totally sure. Prufer's algo tells us that there are n^(n-2) labeled trees and any of the nodes can be made a root, thus we get the number n^(n-1).

这篇关于什么是可能的有序树有N个节点的总数是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！