可以用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).

提前谢谢！

推荐答案

由于存在四个证明在您引用的Wikipedia文章中，您似乎并没有在寻找有关加泰罗尼亚数字与二叉树排列的对应关系的数学解释.

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屋！