组合数学中的一些基本的套路，感觉还是不会做题目啊QAQ
感觉高中的组合数学被翔碾压，大学被各位巨巨智商碾压emmmmmm
还有群论的大坑没有开， polya还不会
圈排列问题
n位同学，围成一圈玩狼人杀，问分配座位的方案。
公式
\((n-1)!\)
链排列
翻转后可以等价的
公式
\(frac{1}{2}(n-1)!\)
隔板法
第一类斯特林数
把一个包含n个元素的集合分成k个环排列的方法数。
第二类斯特林数
把一个包含n个元素的集合分成k个非空子集的个数
Bell数（排名问题）
分拆数（计数dp）
错排公式
问题引入
1~n这n个数构成一个排列，第1项不是1，第2项不是2,……,第n项不是n的方案数
分析
我们考虑1的位置，1的位置有n-1个，在每一个位置都是等价的，因此我们不妨设1在第2项，那么再考虑2的位置，2的位置有两种：
如果2在第1项，那么剩余3~n这n-2个数，需要放在第3~n项中，方案数是f(n-2)。
如果2不再第1项，那么2~n这n-1个数，需要放在第1,3~n项，且因为假设了2不能放在第1项，因此这是n-1个数构成错位排列的情况，方案数是f(n-1)
公式以及相应的化简
卡特兰数–计数映射的伟大胜利
暑假的时候积累了很多的卡特兰数的模型，然而还是不会用，先祭上我收集的博客的知识的链接。其实这一类的找规律的问题都可以使用OEIS大法。然而比赛的时候根本不能用。
卡特兰数的讲解
问题的引入
那么一个足够大的栈的进栈序列为:\(1, 2, 3, 4, …n, \)时有多少个不同的出栈序列？
分析
假设现在入栈为+1, 出栈为-1.若现在要出站，那么之前的和必须要大于等于1.
先在假设有这样的序列：1，-1， 1， 1， -1， -1， -1，1
上面的序列明显是不符合要求的，我们从一开始不符合要求的数字开始：
1，-1， 1， 1， -1， -1， -1，1
更改为下面的序列：\(-1, 1, -1, -1, 1, 1, 1, 1\)的序列，有n+1个+1，n-1个-1.
构成了一一映射的关系。
所以：
$$ h(n) = C_{2n}^{n}-C_{2n}^{n-1} = \frac{C_{2n}^{n}}{n+1} $$
问题2
一个n边形，现在要分割成若干个三角形，那么有多少种分割的方法？（LRJ上面的题目）
分析
具体的分析看一下书，最后的通过两种不同的方向，化简了推导式