可以用 N 个键创建的二叉搜索树的可能数量由第 N 个加泰罗尼亚数字给出.为什么? [英] The possible number of binary search trees that can be created with N keys is given by the Nth catalan number. Why?

问题描述

这已经困扰了我一段时间了.我知道给定 N 个键以二叉搜索树的形式排列，可以创建的树的可能数量对应于 加泰罗尼亚语序列.

This has been bothering me for a while. I know that given N keys to arrange in the form of a binary search tree, the possible number of trees that can be created correspond to the Nth number from the Catalan sequence.

我一直在试图确定这是为什么；无法找到任何可能甚至试图直观地解释它的东西，我求助于 SO 的集体知识.我找到了其他方法来计算可能的树的数量，但它们似乎不太直观，除了如何使用它之外没有提供任何解释.再加上维基页面(上面的链接)甚至显示了一个可能的树形结构的图像，带有 3 个键，这让我认为有一个很好的和简洁的解释可以听到(不用说，文章中没有包含)).

I have been trying to determine why this is; unable to find anything that might even attempt to explain it intuitively I resort to the collective knowledge of SO. I found other ways to calculate the number of possible trees, but they seemed less intuitive and no explanation was offered beyond how to use it. Plus the wiki page (that link above) even shows an image of the possible tree formations with 3 keys, which would lead me to think there's a nice and neat explanation to be heard (which is, needless to say, not included in the article).

提前致谢！

推荐答案

既然有四个证明 在您引用的维基百科文章中，您似乎没有在寻找加泰罗尼亚数字与二叉树排列之间的对应关系的数学解释.

Since there are four proofs in the wikipedia article you referenced, it seems you aren't looking for a mathematical explanation for the correspondence between the Catalan numbers and the permutations of a binary tree.

因此，这里有两种方法可以尝试直观地可视化加泰罗尼亚序列(1, 2, 5, 14, 42, ...)在组合系统中是如何出现的.

So instead, here are two ways to try and intuitively visualise how the Catalan sequence (1, 2, 5, 14, 42, ...) arises in combinatorial systems.

对于边长为 N 的多边形，在将多边形完全切割成三角形的顶点之间绘制切口有多少种方法?

For a polygon of side N, how many ways can you draw cuts between the vertices that chop the polygon up entirely into triangles?

• 三角形(N=3):1(已经是三角形了)
• 正方形 (N=4):2(可以在任一对角线上切片)
• 五边形 (N=5):5(从一个顶点发出的两条切片线.五个顶点可供选择)
• 六边形 (N=6):14(尝试绘制)
• ...等等.

在这种情况下，唯一路径的数量是加泰罗尼亚数字.

In this case, the number of unique paths is the Catalan number.

2x2 网格 =>2条路径

2x2 grid => 2 paths

  _|       |
_|       __|

3x3 网格 =>5条路径

3x3 grid => 5 paths

    _|       |       _|         |         |
  _|      _ _|      |          _|         |
_|      _|       _ _|      _ _|      _ _ _|

4x4 网格 =>14条路径
5x5 网格 =>42条路径

4x4 grid => 14 paths
5x5 grid => 42 paths

等等.

如果您尝试为给定的 N 绘制可能的二叉树，您会发现树的排列方式完全相同.

If you try drawing the possible binary trees for a given N, you will see that the way the tree permutes is just the same.

你不只是盲目地接受树和序列之间的对应关系的愿望是令人钦佩的.不幸的是，在不调用二项式数学的情况下，很难进一步讨论这个讨论(并解释为什么加泰罗尼亚公式恰好是"它的样子).如果您想了解 组合数学(包括 排列计数) 本身更深入.

Your desire not to just blindly accept the correspondence between the tree and the sequence is admirable. Unfortunately, it's difficult to go much further with this discussion (and explain why the Catalan formula 'happens to be' the way it is) without invoking binomial mathematics. The Wikipedia discussion of binomial coefficients is a good starting point if you want to understand combinatorics (which includes permutation counting) itself in more depth.

这篇关于可以用 N 个键创建的二叉搜索树的可能数量由第 N 个加泰罗尼亚数字给出.为什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！