数学之美已经超越算法本身，卷积部分待更新
大佬1 “学习”)
大佬2 “学习”)
大佬3 “学习”)
卡特兰数
定义
$C(n)$表示从原点出发，每次向$x$或$y$轴正方向移动$1$单位，到达点$(n,n)$，且在移动过程中不越过第一象限平分线的移动方案数。
推导
生成函数推导
$n$对括号的合法配对方案书，$1..n$,最后一个出栈是$)$,假设匹配的是第$i$个括号，括号里面需要$f[n-i]$，括号外面需要$f[i-1]$
$H(x)=f[0]+f[1]x…f[k]x^k$
组合数推导
总的方案数：$C(2n,n)$
第一次超越对角线的点$P$,到终点$（n,n）$的路径沿（$y=x+1$）对称
不合理的方案数：第一象限$(0,0)\rightarrow(n-1,n+1)$
,$C(2n,n+1)$
或者对于$0011010101$,任意位置$\sum1 \geq \sum0$,不合理的方案必定存在有个位置$\sum1 +1 = \sum0$ 我们这个位置及之前$1,0变换$，就是$n+1$个$1$,$n-1$个$0$，保证了有位置$\sum0<\sum1$，反向变换之后又保证$0,1$个数相同。
1, 1, 2, 5, 14, 42, 132, 429,
- $n$对括号的合法配对方案数
- $n$个节点的二叉树的形态数
- $n+1$个叶子($n$个非叶节点)的满二叉树的形态数, 走到左儿子$+1$,走到 右儿子$-1$,类似于括号匹配(大致同2)
- $n$个数入栈后出栈的排列总数
- 对凸$n+2$边形进行不同的三角形分割的方案数(分割线断点仅为顶点，且分割线仅在顶点上相交)
- $n$层的阶梯切割为$n$个矩形的切法数
第一类斯特林数
定义
$s(n,m)$将 $n$ 个元素划分为 $m$ 个圆排列的方案数。
第二类斯特林数
定义
第二类斯特林数$S(n,m)$表示的是把$n$个不同的小球放在$m$个相同的盒子里方案数，或是把$n$个元素分$m$堆集合。(盒子集合不能为空,$m>=n$)
我们也用$\begin {Bmatrix} n \\ m\end {Bmatrix}$来表示$S(n,m)$
考虑第$n$个元素,可以单独在一个盒子$S(n-1,m-1)\rightarrow S(n,m)$,或者加入原有集合中$S(n-1,m)\rightarrow S(n,m)$有$m$种加法。
考虑$n$个不同球，放到$m$个不同盒子可以空盒子$=m^n$
$n$个不同球，放到$m$个不同盒子不能有空盒子$=m^n-$(一定有空盒子的)
$n$个不同球，放到$m$个不同盒子至少有一个空盒子$C(m,1)*(m-1)^n$,这样计算是有重复(比如选1后2也是空，选2后1也是空)，就需要用到容斥原理。
$k$个为空盒子。
那么选择$k$个元素的方案数为 $C(m,k)$
无空盒子$=m^n-\sum_{i=1}^m (-1)^{i+1} C(m,k)*(m-i)^n$
不同盒子$\rightarrow$相同盒子$*\frac{1}{m!}$
通项公式
$x^{\underline k}$是$x$的$k$次下降幂
$k$个不同求放在$x$个不同盒子里，每个球有$x$种选择，即$x^k$。
或是枚举有多少非空盒子$C(n,i)$,对于那么些盒子方案数为$i!*S(k,i)$。