更新时间:2023-11-23 14:21:04
既然有四个证明 在您引用的***文章中,您似乎没有在寻找加泰罗尼亚数字与二叉树排列之间的对应关系的数学解释.
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?
在这种情况下,唯一路径的数量是加泰罗尼亚数字.
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.