可以使用N个密钥创建的二叉搜索树的可能数量由第N个加泰罗尼亚数给出.为什么？

Question

这困扰了我一段时间.我知道,如果N键以二叉搜索树的形式排列,可以创建的树的可能数量对应于加泰罗尼亚序列中的第N个数字.

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

提前致谢!

Answer 1

由于您引用的维基百科文章中有四个证据,因此您似乎并未寻找加泰罗尼亚数字与二叉树的排列之间的对应关系的数学解释.

相反,这里有两种方法可以直观地想象加泰罗尼亚序列(1,2,5,14,42 ......)在组合系统中是如何产生的.

将多边形切割成三角形

对于N面的多边形,有多少种方法可以在将多边形完全切割成三角形的顶点之间绘制切口？

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

通过网格绘制路径而不穿过对角线

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

2x2网格=> 2路径

  _|       |
_|       __|

3x3网格=> 5路径

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

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

等等.

如果您尝试为给定的N绘制可能的二叉树,您将看到树置换的方式是相同的.

你不希望盲目地接受树和序列之间的对应关系的愿望是令人钦佩的.不幸的是,在没有调用二项式数学的情况下,很难进一步讨论这个问题(并解释为什么加泰罗尼亚公式恰好是'它的').如果你想更深入地理解组合学(包括排列计数)本身,维基百科对二项式系数的讨论是一个很好的起点.

Answer 2

加泰罗尼亚语http://www.nohre.se/publicImages/catalan.png

任何二进制搜索树都可以通过预先访问所有节点进行编码,并为每个父节点编码1,为每个叶子编码0.如果树有n个父项,它将有n + 1个叶子,因此二进制代码将具有n 1:s和(n + 1)0:s.而且,代码的任何前缀至少与0:s一样多1:s.因此,可能的树的数量等于对角线下方的路径的数量.