常见数列

斐波那契数列

F_i=F_i-1+F_i-2，  F₁=F₂=1 的数列 {Fn} 称为斐波那契数列，为斐波那契数

1.2通项公式：

Catalan 卡特兰数列

应用:

1. 出栈序列数

2. 二叉树构成 n个结点, 问能构成几种不同的二叉树
3. n+2 条边的凸多边形的三角形划分

4. 在n*n的格子中，只在下三角行走，每次横或竖走一格，有多少种走法？

5. 由n对括号形成的合法括号表达式的个数为
6. n+1个数连乘，不同的乘法顺序数为

第二类斯特林数

第二类斯特林数 「S(n,m)」 表示的是把n个不同的小球放在m个相同的盒子里方案数(盒子不为空)。

递推:

S(n,m)=S(n-1,m-1)+m*S(n-1,m)

• 第n个球单独放入一个盒子里, 剩下的n-1个球放入m-1个盒子里S(n-1,m-1)
• 第n个球不单独放入一个盒子里, 剩下的n-1个球放入m个盒子里, 盒子不能空, 那么第n个球可以放在任一盒子里, 所以有m*S(n-1,m)

第一类斯特林数

将n个不同的元素划分为k个圆排列的方案数.

递推式:f(i,j)=f(i-1,j-1)+(i-1)*f(i-1,j)

加入一个新的数有两种情况:

1. 是自己成环, 剩下的 i-1 个数形成 j-1 个环
2. 是加入以前的环，那么这个数可以插到任何一个数的前面 (i−1) f(i−1, j)