1.斐波那契数列
P.S.:这里首项下标为 1
递推式:$$F_i=F_{i-1}+F_{i-2},F_1=F_2=1$$
性质:
(1.sum^{n}_{i=1}F_{i}=F_{n+2}-1)
(2.sum^{n}_{i=1}F_i^2=F_n F_{n+1})
(3.sum_{i=1}^{n}i F_i=n F_{n+2}-F_{n+3}+2)
(4.F_{n+m}=F_n F_{m-1}+F_{m} F_{n+1})
(5.F_{2n}/F_{n}=F_{n-1}+F_{n+1})
(6.gcd(F_i,F_{i+1})=1)
(7.gcd(F_n,F_m)=F_{gcd(n,m)})
(8.)斐波那契数列的第n+2项代表了集合({1,2,...n})中所有不包含相邻正整数的子集的个数.
2.卡特兰数
P.S. 这里首项下标为0
递推关系:
常用递推关系:
另类递推式:
应用:
- n 个元素的不同的出栈序列个数
- n 个元素的排列中最长下降子序列不超过 2 的排列个数
- 凸 n+2 边形的三角形划分数
- 球迷购票问题
- n 对括号正确匹配的排列方案数
- 链乘的括号化方案数
3.斯特林数
1.第一类斯特林数
含义: n 个人坐 m 张圆桌的方案数
递推式:
理解:新来一个人的时候,要么坐在前面 n-1 个人的某一边(坐在一个地方必定同时是一个人的左边和一个人的右边) , 要么自己新坐一桌
有符号与无符号第一类斯特林数的关系:
1.无符号第一类斯特林数与上升幂/下降幂的关系
考虑:
从生成函数方面考虑其含义,是从 ([0,n-1]) 中选出任意多个数乘起来的和,其中第 (m) 次方项系数表示选了 (n-m) 个数(剩下 m 个数)时的和 , 特别的 , 一个数也不选乘积为 1
设(f(n,m))表示从 ([1,n]) 里面选数 , 剩下 (m) 个数时的和,容易得到递推式:
看 (n-1) 选不选就能够得出来 , 边界: (f(0,0)=1)
这个递推式和第一类斯特林数的式子长的一模一样,所以: (f(n,m)=left [ egin{matrix}n \ mend{matrix}
ight ]_u)(无符号)
那么展开上升幂得到:
是不是和二项式定理很像
对于下降幂:
似乎可以理解为通过上升幂容斥得来:
其实也可以直接写成有符号第一类斯特林数:
2.第二类斯特林数
含义: 把 n 个有标号的球放入 m 个无标号的盒子里 , 不允许空盒的方案数
递推式:
理解: 新来一个球 , 要么放入原有的盒子,要么放入一个新的盒子
常用公式(推导略):
1.通项公式:
拆开组合数可以发现是卷积的形式,可以用 (NTT) 预处理 (n)个球的时候的第二类斯特林数
2.斯特林展开
把第二类斯特林数通项公式用二项式反演定理反演回去即可
由于当(j>n)时,原式子的贡献为0,所以其实只用枚举 (j) 到 (min(n,x))
可以写成下降幂的形式:
当 (j>x) 时 下降幂变为 0 ,所以可直接写成:
这就很优美了
4.贝尔数
含义: 把 1 (sim) n 拆分成若干无序集合的方案数
bell数其实是第二类斯特林数的前缀和 , 可以理解为把 n 个有标号的球放入 n 个无标号的盒子里 , 允许空盒的方案数
递推式:
性质:
- 若 (p) 是任意质数: (B_{n+p}equiv B_n+B_{n+1} (mod p))
5.伯努利数
满足:
化简移项
其生成函数为:
(e^x)泰勒展开后多项式求逆在(O(nlogn))的复杂度内求出前(n)项
可以用来求自然幂数和:
(不定期更新...)