组合数学总结
I.组合数
1.定义：用表示
个物品选
个（不排序）的方案数。
2.性质：
1>
2>
3>（证明：利用性质2）
>
（性质3的扩展）
4>
3.求法：
1>递推。使用性质2，。
2>Lucas定理。适用于%一个质数 的情况，
，注意其中
还可以再分。
3>扩展Lucas定理。将模数 分解为
，就只需要求
，然后用CRT合并即可。
II.第一类斯特林（Stirling I）数
1.定义：用表示把
个不同物品分成
个圆排列的方案数，亦写作S1[n,k]。
2.递推式：
.分析：
1>在一个圆圈里只有编号为n的人。排法有个。
2>n至少和另外一个人在一个圆圈里。这些排法可以通过把1，2.....n-1排成k个圆圈，再把n放在1，2，......，n-1任意一个人的左边。因此，第二种类型的排法有种。
III.第二类斯特林（Stirling II）数
1.定义：把 个物品分成
个集合的方案数叫第二类斯特林数，用{
}表示。其中
个物品互不相同，
个集合相同。亦写作S2{n,k}。
2.递推式：{}
{
}
{
}
.分析：略，同第一类斯特林数。
IV.卡特兰（Catalan）数
1.定义：
1>有 对括号的合法括号序列匹配方案数。
2> ，
，...，
顺次入栈，出栈序列方案数。
3>边数为 凸多边形三角划分方案数。
4> 个节点的二叉树种数。
2.求法：
1>递推。，其中
。
2>公式。
3.扩展卡特兰数 BSOJ P2726 【SCOI2010】字符串
要求使组成 01 串中任意前缀中 1 的个数比 0 多，而 0 和 1 的个数不等。
那么我们假设向右上走表示这个字符选择 1 ，向右下走表示这个字符选择 0 ，问题即化为从走到
的总方案数（不考虑不合法时）。
本题即可化为总方案数 - 不合法方案数，不合法方案数即为触碰到 的方案数，即
也可以看Luogu Solution，戳
V.斐波那契（Fibonacci）数列
1.定义：略
2.性质：
1>
2>
3>
4>
此文章采用 语法
