作者:没有水的鱼0713 | 来源:互联网 | 2023-06-14 19:39
本文由编程笔记#小编为大家整理,主要介绍了施罗德数相关的知识,希望对你有一定的参考价值。 某次考试考到 超级卡特兰数(又称大施罗德数)意义:F[n]:从(0,0)开始,只能往上往右或者往右上
本文由编程笔记#小编为大家整理,主要介绍了施罗德数相关的知识,希望对你有一定的参考价值。
某次考试考到
超级卡特兰数(又称大施罗德数)
意义:F[n]:从(0,0)开始,只能往上往右或者往右上,不能跨过y=x,到达(n,n)的路径方案数
递推式的证明:
类比卡特兰数,后面的是枚举第一次碰到y=x在哪里
还要加上一个F(n-1)的原因是,并没有统计第一次斜着走到(1,1)的情况,之前统计的都是第一次横着走的。