Combination & Sequence
组合数性质
n 个球 m 个盒子
1.球同，盒同，可空
2. 球同，盒同，不可空
先在每个箱子里面放 $1$ 个球, 然后还剩下 $n-m$ 个球了, 就转化成了上一种情况, $dp_1[n-m][m]$
3.球同，盒不同，不可空
一共有 $n-1$ 个空隙, 要插 $m-1$ 个板, $C_{n-1}^{m-1}$
4.球同，盒不同，可空
先给每个盒子一个球, 把问题转化为不能空的情况, 相当于 $n+m$ 个小球放入 $m$ 个盒子且不能空, $C_{n+m-1}^{m-1}$
应用
从 $n$ 个不同的物品中选取 $m$ 个，每种物品可以取多次，问方案数。
设从每种物品中取 $a_i$ 个，显然 $\sum a_i=m$ ，所以就相当于将 $m$ 个相同的球放入 $n$ 个不同的箱子里。
5.球不同，盒同，不可空
第二类斯特林数
$dp_2[n][m]$ 代表 $n$ 个小球放入 $m$ 个不同的盒子且不能空的方法
6.球不同，盒同，可空
7.球不同，盒不同，不可空
8.球不同，盒不同，可空
Burnside引理
对于一个置换 $f$, 若一个染色方案 $s$ 经过置换后不变，称 $s$ 为 $f$ 的不动点。将 $f$ 的不动点数目记为 $c(f)$，则可以证明等价类数目为所有的 $c(f)$ 平均值。
例子: 一正方形分成 $4$ 格，$2$ 着色，有多少种方案？
对于这 $16$ 种方案可以归一下类：
不动：
转 $90$ 度 ：$a2=(1)(2)(6 ,5, 4, 3)(10, 9 ,8 ,7)(11, 12)(16 ,15 ,14 ,13) $
转 $180$ 度：$a3=(1)(2)(3 ,5)(4, 6)(7, 9)(8, 10)(11)(12) (13, 15)(14, 16) $
- 转 $270$ 度：$a4=(1)(2)(3, 4, 5 ,6)(7 ,8, 9, 10) (11, 12)(13, 14 ,15 ,16)$
$(a,b,c)$ 表示可以通过 $a,b,c$ 旋转得到
所以共有 $\frac {16+2+4+2}4=6$ 种方案.
Polya定理
假设一个置换有 $k$ 个循环，易知每个循环对应的所有位置颜色需一致，而任意两个循环之间选什么颜色互不影响。因此，如果有 $m$ 种可选颜色，则该置换对应的不动点个数为 $m^k$。用其替换 $burnside$ 引理中的 $c(f)$，即 $c(f)=m^k$ 得到等价类数目为：
不动：$a1=(1)(2)(3)(4) $
旋转 $90$ 度：$a2=(1, 2, 3, 4)$
旋转 $180$ 度 ：$a3=(1 ,3)(2 ,4)$
旋转 $270$ 度：$a4=(1, 4, 3, 2)$
由$Polya$ 定理得，共有 $\large\frac {2^4+2^1+2^2+2^1}4=6$ 种方案。
容斥原理
鸽巢原理
定义
如果要把 $n$ 个物品放入 $m$ 个容器中，至少有一个容器中的物品的数量 $\large\ge\lceil\frac n m\rceil$
例子
给 $n$ 个数，找出一些数，其和为 $n$ 的倍数
有 $n$ 个前缀和，如果没有等于 $0$ 的，那么剩余的数的取值为 $1\sim {n-1}$ ，必定有一个数使用了两次
Ramsey定理(广义鸽巢定理)
定义
通俗解释
在 $6$ 个或更多人中，或者有 $3$ 个人，他们中的每两个人都互相认识；或者有 $3$ 个人，他们中的每两个人都彼此不认识。记为 $K_6\to K_3,K_3$
一般解释
对于一个给定的两个整数 $n,m\ge2$，则一定存在一个最小整数 $r$，使得用两种颜色（红色或蓝色）无论给 $K_r$ 的每条边如何染色，总能找到一个红色的 $K_m$ 或者蓝色的 $K_n$ 。显然，当 $p\ge r$ 的时候，$K_p$ 亦满足这个性质。
性质
- $r(m,n)=r(n,m)$
- $r(2,n)=n$
- $r(m,2)=m$
斐波那契数列
$f(i)=f(i-1)+f(i-2),f(1)=f(2)=1$
与集合子集
斐波那契数列的第 $n+2$ 项同时也代表了集合 {1,2,…,n} 中所有不包含相邻正整数的子集个数。
如果 $f(k)$ 能被 $x$ 整除，则 $f(k*i)$ 都可以被 $x$ 整除。
求递推公式 $a(1)=1,a(n+1)=1+\frac 1 {a(n)}$ 的通项公式 $a(n)= \frac {fib(n+1)}{fib(n)}$
矩阵快速幂
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27struct matrix {
ll a[2][2];
matrix(){
mem0(a);
}
};
matrix mat_mul(matrix x, matrix y) {
matrix res;
int (int i = 0; i < 2; i++)
int (int j = 0; j < 2; j++)
int (int k = 0; k < 2; k++)
res.a[i][j] = (res.a[i][j] + x.a[i][k] * y.a[k][j]) % mod;
return res;
}
int mat_pow(ll n) {
if (n <= 2) return 1;
n -= 2;
matrix c, res;
c.a[0][0] = c.a[0][1] = c.a[1][0] = 1;
int (int i = 0; i < 2; i++) res.a[i][i] = 1;
while (n) {
if (n % 2) res = mat_mul(res, c);
c = mat_mul(c, c);
n /= 2;
}
return (res.a[0][0] + res.a[0][1]) % mod;
}
卢卡斯数列
$F_0=2,F_1=1,F_n=F_{n-1}+F_{n-2}$
通项为
法里数列
定义
$n$ 阶的法里数列是 $0$ 和 $1$ 之间最简分数(分母不大于 n )的数列，由小至大排列，每个分数的分母不大于 $n$。
构造
已知两个法里数 $\frac ab$和 $\frac c d$，那么两者之间的法里数就是$\frac {a+c} {b+d}$
性质
$F_n$ 包含了 $F_{n-1}$ 的全部项
$|F_n|=|F_{n-1}+\phi(n)|$
$|F_n|\sim \frac {3n^2} {\pi^2}$
若 $\frac a b,\frac c d(\frac a b<\frac c d)$ 是法里数列的邻项，则它们之差为 $\frac 1 {bd}$
F1 = {0⁄1, 1⁄1}
F2 = {0⁄1, 1⁄2, 1⁄1}
F3 = {0⁄1, 1⁄3, 1⁄2, 2⁄3, 1⁄1}
F4 = {0⁄1, 1⁄4, 1⁄3, 1⁄2, 2⁄3, 3⁄4, 1⁄1}
F5 = {0⁄1, 1⁄5, 1⁄4, 1⁄3, 2⁄5, 1⁄2, 3⁄5, 2⁄3, 3⁄4, 4⁄5, 1⁄1}
F6 = {0⁄1, 1⁄6, 1⁄5, 1⁄4, 1⁄3, 2⁄5, 1⁄2, 3⁄5, 2⁄3, 3⁄4, 4⁄5, 5⁄6, 1⁄1}
F7 = {0⁄1, 1⁄7, 1⁄6, 1⁄5, 1⁄4, 2⁄7, 1⁄3, 2⁄5, 3⁄7, 1⁄2, 4⁄7, 3⁄5, 2⁄3, 5⁄7, 3⁄4, 4⁄5, 5⁄6, 6⁄7, 1⁄1}
F8 = {0⁄1, 1⁄8, 1⁄7, 1⁄6, 1⁄5, 1⁄4, 2⁄7, 1⁄3, 3⁄8, 2⁄5, 3⁄7, 1⁄2, 4⁄7, 3⁄5, 5⁄8, 2⁄3, 5⁄7, 3⁄4, 4⁄5, 5⁄6, 6⁄7, 7⁄8, 1⁄1}
卡特兰数
例子
进出栈问题
一个足够大的栈的进栈序列为 $1,2,3,⋯,n$ 时有多少个不同的出栈序列？
我们可以这样想，假设 $k$ 是最后一个出栈的数。比 $k$ 早进栈且早出栈的有 $k-1$ 个数，一共有 $h(k-1)$ 种方案。比$k$ 晚进栈且早出栈的有 $n-k$ 个数，一共有 $h(n-k)$ 种方案。所以一共有 $h(k-1)\times h(n-k)$ 种方案。显而易见，$k$ 取不同值时，产生的出栈序列是相互独立的，所以结果可以累加。$k$ 的取值范围为 $1$ 至 $n$，所以结果就为$h(n)= h(0)h(n-1)+h(1)h(n-2) + … + h(n-1)h(0)$
有n个结点，问总共能构成几种不同的二叉树。
我们可以假设，如果采用中序遍历的话，根结点第k个被访问到，则根结点的左子树有k-1个点、根结点的右指数有n-k个点。k的取值范围为1到n。讲到这里就很明显看得出是卡特兰数了。
凸多边形的三角形划分
一个凸的n边形，用直线连接他的两个顶点使之分成多个三角形，每条直线不能相交，问一共有多少种划分方案。
选择一个基边，显然这是多边形划分完之后某个三角形的一条边。图中我们假设基边是p1pn，我们就可以用p1、pn和另外一个点假设为pi做一个三角形，并将多边形分成三部分，除了中间的三角形之外，一边是i边形，另一边是n-i+1边形。i的取值范围是2到n-1。所以本题的解$c(n)=c(2)c(n-1)+c(3)c(n-2)+…c(n-1)c(2)$。令t(i)=c(i+2)。则$t(i)=t(0)t(i-1)+t(1)t(i-2)…+t(i-1)t(0)$。很明显，这就是一个卡特兰数了。
$n$ 个 $1$ ， $n$ 个 $-1$ ，构成的排列中，满足任意一段前缀和都 $\ge0$ 或 $\le0$ 的数量为 $h(n)$，可以将 $1$ 看作入栈，将 $-1$ 看作出栈
$x$ 个 $1$ ， $y(x\ge y)$ 个 $-1$ ，构成的排列中，满足任意一段前缀和都 $\ge0$ 的数量为 $C(x+y,x)-C(x+y,x+1)$，可以将 $1$ 看作入栈，将 $-1$ 看作出栈
贝尔数
n个元素的集合的划分方案数
贝尔三角形
第一行第一项是1, $a(1,1)= 1$
对于$n>1$，第 $n$ 行第一项等同第 $n-1$ 行最后一项, $ a(n,1)=a(n-1,n-1)$
对于$m,n>1$，第 $n$ 行第 $m$ 项等于它左边和左上方的两个数之和, $a(n,m)=a(n,m-1)+a(n-1,m-1)$
同余性质 (p是不大于100的素数)
$Stirling$ 数
第一类 $Stirling$ 数
其绝对值是包含 $n$ 个元素的集合分作 $k$ 个环排列的方案数
无符号 $Stirling$ 数
有符号 $Stirling$ 数
第二类Stirling数
将 $n$ 个不同的元素拆分成 $m$ 个集合的方案数
两类Stirling数之间的关系
施罗德数
从 $(0,0)$ 到 $(n,n)$ 的格路中，只能使用 $(1,0),(0,1),(1,1)$ 三种移动方式，始终位于对角线下方且不越过对角线的路径数, $1, 2, 6, 22, 90, 394, 1806, 8558, 41586, 206098,… (OEIS A006318)$
多边形数
五边形数
$\large p(n)=\frac {(3*n^2-n)}2$
前几个五边形数：1, 5, 12, 22, 35, 51, 70, 92, 117, 145, 176, 210, 247, 287, 330, 376, 425, 477, 532, 590, 651, 715, 782, 852, 925, 1001 ………
广义五边形数：
n的取值0,1,-1,2,-2,3,-3…….
前几个广义五边形数：0, 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, 57, 70, 77, 92, 100, 117, 126, 145, 155, 176, 187, 210, 222, 247, 260, 287, 301, 330…..
五边形数测试
中心五边形数
中心六边形数(相邻两个广义五边形数之和)
费马多边形数定理: 每一个正整数最多可以表示为 n 个 n-边形数 的和
求 $1^k+2^k+3^k+….+n^k=?$
$(n-1)^k=n^k+C(k,1)n^(k-1)(-1)+C(k,2)n^(k-2)(-1)^2+…+C(k,k)*(-1)^k$
$(n-2)^k=[(n-1)-1]^k=(n-1)^k+C(k,1)(n-1)^(k-1)(-1)+C(k,2)(n-1)^(k-2)(-1)^2+…+C(k,k)*(-1)^k$
$(n-3)^k=[(n-2)-1]^k=(n-2)^k+C(k,1)(n-2)^(k-1)(-1)+C(k,2)(n-2)^(k-2)(-1)^2+…+C(k,k)*(-1)^k$
…
$2^k=(3-1)^k=3^k+C(k,1)3^(k-1)(-1)+C(k,2)3^(k-2)(-1)^2+…+C(k,k)*(-1)^k$
$1^k=(2-1)^k=2^k+C(k,1)2^(k-1)(-1)+C(k,2)2^(k-2)(-1)^2+…+C(k,k)*(-1)^k$
这n-1个式子相加,得：
$1^k=n^k+C(k,1)(-1)[2^{k-1}+3^{k-1}+…+n^{k-1}]+C(k,2)(-1)^2[2^{k-2}+3^{k-2}+…+n^{k-1}]+…+(n-1)C(k,k)(-1)^k$
如果令关于k的函数$S(k)=1^k+2^k+…+n^k$
则$1=n^k+C(k,1)(-1)[S(k-1)-1]+C(k,2)(-1)^2[S(k-2)-1]+…+(n-1)*(-1)^k$
由此可以得出S(k-1)关于S(k-2)、S(k-3)、…、S(2)和S(1)的地推公式
已知
$S(1)=1+2+…+n=\frac {n(n+1)} 2 $
$S(2)=1^2+2^2+…+n^2=\frac {n(n+1)(2n+1)}2$
$S(3)=1^3+2^3+…+n^3=S(1)^2$
广义斐波那契数列取模循环节
若递推式为 $f(n)=a\times f(n-1)+b\times f(n-2)$ ，其矩阵关系为
寻找最小的 $n$ 使得
令 $c=a^2+4b$ ，分类讨论
- 若 $c$ 是 $p$ 的二次剩余， $n$ 为 $p-1$ 的因子
- 若 $c$ 是 $p$ 的二次非剩余， $n$ 为 $(p-1)(p+1)$ 的因子
斐波那契数列取模循环节
把n素因子分解，即 $n=p_1^{a_1} p_2^{a_2} · · · *p_k^{a_k}$
分别计算Fib数模每个$p^m$的循环节长度，假设长度分别是$x_1,x_2,x_3, · · · ,x_k$
那么Fib模n的循环节长度$L=lcm(x_1,x_2,x_3, · · · ,x_k)$
- Fib数模$p^m$的最小循环节长度等于$G(p)*p^{m-1}$，其中$G(p)$表示Fib数模素数p的最小循环节长度
1 | //简单算法 |