什么时卡特兰数，它为什么可以应用在二叉树结构、曼德勃罗集、分形里？
视频简介：
有一天我在研究一个像"√(1-x²)"这样的函数时，发现它的导数变化特别有意思。这让我想到一个有趣的排列组合问题：
假设你有一堆"上楼梯"和"下楼梯"的卡片，各n张。怎么排列这些卡片，才能保证在任何时候"下楼梯"的次数都不超过"上楼梯"，而且最后刚好回到原点？
比如：
当n=1时：只有"上下"这一种排法
n=2时：有"上上下下"和"上下上下"两种
n=3时：有5种排法
后来我发现，这就像在画一个"山峰"形状的路径：每次向右上方或右下方走一步，不能掉到起点以下，最后要回到起点高度。这种路径的数量就是著名的"卡特兰数"。
更神奇的是，这个数列居然和杨辉三角（帕斯卡三角形）有关系！只要用杨辉三角中间的数字减去它旁边的数字，就能直接算出卡特兰数。比如：
C₃ = 20(中间数) - 15(旁边数) = 5
这个数列在计算机科学（比如二叉树）、几何（多边形分割）甚至分形图形中都会出现，是个超级实用的数学工具！
本视频翻译自：
https://www.youtube.com/watch?v=X6NQMB6JaF0
立即观看
0