数论+组合

· · 个人记录

LaTeX

注：引理见后面第四部分

1.欧拉函数，欧拉筛及应用

1.欧拉筛：

for(int i = 2;i <= N;i++)
{
    if(!vis[i]) pri[++cnt] = i;
    for(int j = 1;i * pri[j] <= N;j++)
    {
        int u = i * pri[j];
        vis[u] = 1;
        if(i % pri[j] == 0) break;
    }
}

2.欧拉函数：\varphi(n)

计算：\varphi(n) = n \times \prod _ {i = 1} ^ n (1 - \frac{1}{p_i})

用欧拉筛实现： 设 m = pri[j] \times i

1>若i \bmod pri[j] == 0

则

\varphi(m) &= m \times \prod _ {i = 1} ^ k(1 - \frac{1}{p_i}) \\&= pri[j] \times i \times\prod _ {i = 1} ^ k(1 - \frac{1}{p_i})\\& = pri[j] \times \varphi[i] \end{aligned}

2>若i \bmod pri[j] != 0,说明二者互质

则

\begin{aligned} \varphi(m) &= \varphi(pri[j]) \times \varphi(i) \\ & = (pri[j] - 1) \times \varphi(i) \end{aligned}

2.定理

欧拉定理：

若\gcd(a,m) = 1

则

a ^ {\varphi(m)} \equiv 1 \pmod m

裴蜀定理

设a,b \in Z

则存在x,y,使得

ax + by = \gcd(a,b)

推广1：存在x,y,使得

ax + by = \gcd(a,b) \times n

推广2：存在X_1 \cdots X_n,使得

\sum\limits_ {i = 1}^{n}A_iX_i = \gcd(A_1,A_2,\cdots,A_n)

扩展欧几里得

对方程ax + by = \gcd(a,b)（设\gcd(a,b) = d）

可得到

\begin{cases} ax_0 + by_0 = \gcd(a,b)\\ bx_1 + (a \% b)y_1 = \gcd(b,a \% b) \end{cases}

而\gcd(a,b) = \gcd(b,a \% b)

则

ax_0 + by_0 = bx_1 + (a \%b)y_1

又有a \% b = a - (int)a / b \times b

设(int)a /b = k

则

ax_0 + by_0 = bx_1+(a - kb)y_1

整理得

ax_0 + by_0 = ay_1 + b(x_1 - ky_1)

则

\begin{cases} x_0 = y_1\\ y_0 = x_1 - ky_1 \end{cases}

这是相邻两组解的关系，那么这样推下去，则a\%b会变成0(求gcd时的终止条件)

则有

d\times x_n + 0 \times y_n = d

则存在特解

\begin{cases} x_n = 1\\ y_n = 0 \end{cases}

递归反推每一组解即可

ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b == 0)
    {
        x = 1;y = 0;
        return a;
    }
    ll d;
    d = exgcd(b,a % b,x,y);
    ll t = x; 
    x = y;
    y = t - a / b * y;
    return d;
}

通解：

\begin{cases} x = x_0 + \frac{b}{\gcd(a,b)} \times k\\ y = y_0 - \frac{a}{\gcd(a,b)} \times k \end{cases}

扩展欧拉定理

a^b \equiv \begin{cases} a^{b \operatorname{mod} \varphi(p)}&\gcd(a,p) = 1\\ a ^b &\gcd(a,p) \neq 1,b < \varphi(p) \\ a^{b \operatorname{mod} \varphi(p) + \varphi(p)}&\gcd(a,p) \neq 1,b \geqslant \varphi(p) \end{cases} \pmod p

证明：

对于第一个式子，由欧拉定理

\begin{aligned} a^b &\equiv a^{k \times \varphi(p)+r} \\&\equiv (a^{\varphi(p)})^k + a^r \\&\equiv 1^k + a^r \\&\equiv a^{b \operatorname{mod} \varphi(p)} \end{aligned}

第二个式子用于b较小的时候

下证第三个式子

a = \prod\limits_{i = 1}^{s}p_i^{r_i}

(分解质因数)

代入

(\prod\limits_{i = 1}^{s}p_i^{r_i})^b \equiv (\prod\limits_{i = 1}^{s}p_i ^ {r_i})^{b \operatorname{mod} \varphi(p)+\varphi(p)} \pmod p \prod\limits_{i = 1}^{s}(p_i^{r_i})^b \equiv \prod\limits_{i = 1}^{s}(p_i ^ {r_i})^{b \operatorname{mod} \varphi(p)+\varphi(p)} \pmod p \prod\limits_{i = 1}^{s}p_i^b \equiv \prod\limits_{i = 1}^{s}p_i ^{b \operatorname{mod} \varphi(p)+\varphi(p)} \pmod p

即证明对

\forall 1 \leqslant i \leqslant s,p_i^b \equiv p_i ^{b \operatorname{mod} \varphi(p)+\varphi(p)} \pmod p

(在此之后，模数更换为m

即\forall 1 \leqslant i \leqslant s，p_i^b \equiv p_i ^{b \operatorname{mod} \varphi(m)+\varphi(m)} \pmod m,并将p_i写成p,p是质数)

如果\gcd(p,m) = 1,则

\begin{aligned} p^b &\equiv p^b \times 1 \\&\equiv p^{b \operatorname{mod} \varphi(m)} \times p^{\varphi(m)} \\&\equiv p^{b \operatorname{mod} \varphi(m) + \varphi(m)} \end{aligned}

如果不等于1，则m = k \times p(k \geqslant 2)

设m = s \times p^r,\gcd(s,p^r) = 1 = \gcd(s,p)

则

p^{\varphi(s)}\equiv 1 \pmod s

又有\varphi(m) = \varphi(p^r) \times \varphi(s)

那么p^{\varphi(m)} \equiv 1^{\varphi(p^r )}\equiv 1 \pmod s--------------①

又因为

p^b = (p^{\varphi(m)})^{\lfloor \frac{b}{\varphi(m)} \rfloor} \times p^{b \operatorname{mod} \varphi(m)}

并由①：(p^{\varphi(m)})^{\lfloor \frac{b}{\varphi(m)} \rfloor} \equiv 1^{\lfloor \frac{b}{\varphi(m)} \rfloor} \equiv 1 \pmod s

故

p^b \equiv p^{b \operatorname{mod} \varphi(m)} \pmod s p^{b + r} \equiv p^{b \operatorname{mod} \varphi(m)+ r} \pmod {s \times p^r}

(由引理)

则

p^{b + r} \equiv p^{b \operatorname{mod} \varphi(m)+ r} \pmod m 由①： $$p^{\varphi(m)+r} \equiv p^r \pmod {s \times p^r}$$ $$p^{\varphi(m)+r} \equiv p^r \pmod m$$ 所以 $$ \begin{aligned} p^b &\equiv p^{b - r} \times p^r \\&\equiv p^{b - r} \times p^{\varphi(m)+r} \\&\equiv p^{b + \varphi(m)} \\&\equiv p^{b \operatorname{mod} \varphi(m)+ \varphi(m)} \end{aligned} \pmod m $$ 证毕 ### $Lucas$定理 $$C_{n}^{m} \equiv C_{n / p}^{m / p} \times C_{n \%p}^{m\%p} \pmod p$$ （$p$为素数） 证明： 首先： $$ \begin{aligned} C_{p}^{x} &\equiv \frac{p!}{x!(p - x)!} \\&\equiv \frac{p}{x}\times C_{p -1}^{x - 1} \\&\equiv p \times x^{-1}\times C_{p - 1}^{x - 1} \\&\equiv 0 \pmod p \end{aligned} $$ 其中$0 < x < p,gcd(x,p) = 1

所以x的逆元存在

再由上

\begin{aligned} (1 + x)^n &\equiv \sum\limits_{i = 0}^{n} C_{n}^{i}x^i \\&\equiv C_{n}^{0}\times 1 +C_{n}^{n} \times x^n \\&\equiv 1 + x^n \pmod p \end{aligned}

接下来

\begin{aligned} (1 + x)^n &\equiv \sum\limits_{i = 0}^{n} C_{n}^{i}x^i ---- \alpha \\&\equiv (1 + x)^{ap+b} \\&\equiv ((1 + x)^p)^a \times (1 + x)^b \\&\equiv (1 + x^p)^a \times (1 + x)^b \\&\equiv \sum\limits_{i = 0}^{a}C_{a}^{i}x^{ip} \times \sum\limits_{j = 0}^{b}C_{b}^{j}x^j -----\beta \pmod p \end{aligned}

有x^m = x^{cp+d} = x^{cp} \times x^d

由\alpha,\beta式和系数相等：

C_{n}^{m} = C_{a}^{c} \times C_{b}^{d}

再结合n = ap + b,m = cp + d

C_{n}^{m} \equiv C_{n/ p}^{m / p} \times C_{n \%p}^{m\%p} \pmod p

中国剩余定理（CRT）

若

\begin{cases} x \equiv r_1 \pmod {m_1}\\ x \equiv r_2 \pmod {m_2}\\ \cdots\\ x \equiv r_n \pmod {m_n} \end{cases} \forall1 \leqslant i < j \leqslant n,\gcd(m_i,m_j) = 1

那么

x_{min+} = \sum\limits_{i = 1}^{n}r_ic_ic_i^{-1} \operatorname{mod} M

其中

M = \prod\limits_{i =1}^{n}m_i c_i = \frac{M}{mi} 证明： 首先：对$x \equiv r_i \pmod {m_i}$,先不求余 $$ \begin{aligned} x &\equiv \sum\limits_{j = 1 \& j != i}^{n}r_jc_jc_j^{-1} + r_ic_ic_i^{-1} \\&\equiv \sum\limits_{j = 1 \& j != i}^{n}r_j\frac{m_i\times\frac{M}{m_i}(\in Z)}{m_j}c_j^{-1}+r_ic_ic_i^{-1} ---\frac{M}{m_i} \% m_i != 0 \\&\equiv 0+r_ic_ic_i^{-1} \\&\equiv r_i \pmod {m_i} \end{aligned} $$ 再： $$ \begin{aligned} x_{min+} &\equiv x \% M \\&\equiv x +(-k)\times M \\&\equiv x --- m_i|M \pmod {m_i} \end{aligned} $$ ### 扩展中国剩余定理（exCRT） 若$m_i$不一定两两互质 最直观的：不求余中第一个注释处将不成立（$\frac{M}{m_i} \% m_i != 0$互质时必成立，但不互质时不一定），无法进行后续计算 EX: 对于 $$x \equiv r_1 \pmod {m_1}$$ $$x \equiv r_2 \pmod {m_2}$$ 转化为 $$x = m_1p + r_1 = m_2q + r_2$$ 则 $$m_1p - m_2q = r_2 - r_1$$ 由裴蜀定理 $\gcd(m_1,m_2) | (r_2 - r_1)$时有解 特解与通解：（exgcd） $$p = p_0 + \frac{m_2}{\gcd} \times k,q = q_0 - \frac{m_1}{\gcd} \times k$$ 所以 $$x = m_1p + r_1 = m_1p_0 + \frac{m_1m_2}{\gcd}\times k + r_1$$ 那么 $$x \equiv m_1p_0 + r_1 \pmod {m_1m_2}$$ 也就是说，两个方程可以合并成一个方程： $$x \equiv r \pmod m,r = m_1p_0 + r_1,m = \operatorname{lcm}(m_1,m_2)$$ 合并$n - 1$次即可 ### ExLucas(与Lucas无关) 求 $$C_{n}^{m} \operatorname{mod} p$$ 其中$p$不一定是质数 设 $$p = \prod\limits_{i = 1}^{k}p_i^{\alpha_i}$$ 那么只需求 $$ \begin{cases} C_{n}^{m} \operatorname{mod}p_i^{\alpha_i} \end{cases} $$ 再用$CRT$合并即可（得到的是和$C_{n}^{m}$同余的最小正整数） 考虑求 $$C_{n}^{m} \operatorname{mod} p^k,p\in \operatorname{prime}$$ 即 $$\frac{n!}{m!(n - m)!} \operatorname{mod} p^k$$ 考虑到阶乘可能包含$p$因子，所以先除干净 即 $$\frac{\frac{n!}{p^x}}{\frac{m!}{p^y}\times \frac{(n - m)!}{p^z}} \times p^{x - y - z} \operatorname{mod} p^k$$ 其中$x,y,z$均为对应阶乘中含有的$p$因子数量 则再求 $$\frac{n!}{p^x} \operatorname{mod} p^k$$ （分母那俩求逆元就行了） 考虑按是否是$p$的倍数划分阶乘 $$ \begin{aligned} n! &= \prod\limits_{i = 1}^{n}i \\&= \prod\limits_{i = 1}^{\lfloor\frac{n}{p}\rfloor}(i \times p) \times \prod\limits_{j = 1,j \% p != 0}^{n}j \\&= p^{\lfloor\frac{n}{p}\rfloor} \times (\lfloor\frac{n}{p}\rfloor)! \times \prod\limits_{j = 1,j \% p != 0}^{n}j \end{aligned} $$ 对于后面一坨，考虑到$\operatorname{mod}$有循环节，后面循环的部分可以直接“掏”掉若干次方的模数成为第一部分的循环节 比如： $$(1 \times 2 \times 4 \times 5) \times(10 \times 11 \times 13 \times 14) \equiv (1 \times 2 \times 4 \times 5)^2 \pmod 9$$ 其中后半部分循环节可以掏掉一个$9$变成第一部分 那么 $$\prod\limits_{j = 1,j \% p != 0}^{n}j = (\prod\limits_{i = 1,i \% p != 0}^{p^k}i)^{\lfloor\frac{n}{p^k}\rfloor} \times (\prod\limits_{i = p^k\times\lfloor\frac{n}{p^k}\rfloor,i \% p != 0}^{n}i) $$ 前半部分是掏完模数的所有循环节，可以并成乘方，后半部分是剩的 所以 $$n! = p^{\lfloor\frac{n}{p}\rfloor} \times (\lfloor\frac{n}{p}\rfloor)! \times (\prod\limits_{i = 1,i \% p != 0}^{p^k}i)^{\lfloor\frac{n}{p^k}\rfloor} (\prod\limits_{i = p^k\times\lfloor\frac{n}{p^k}\rfloor,i \% p != 0}^{n}i)$$ 第一项要除掉，但第二项中可能还有$p$因子 所以定义 $$f(n) = \frac{n!}{p^x}$$ $$ f(n) = f(\lfloor\frac{n}{p}\rfloor)(\prod\limits_{i = 1,i \% p != 0}^{p^k}i)^{\lfloor\frac{n}{p^k}\rfloor} (\prod\limits_{i = p^k\times\lfloor\frac{n}{p^k}\rfloor,i \% p != 0}^{n}i)$$ 回到原式，即求 $$\frac{f(n)}{f(m)f(n - m)}p^{x - y - z} \operatorname{mod} p^k$$ 接下来求$x,y,z

令g(n) = x（就是n的阶乘中有多少个p因子）

结合n!的展开式，可得

g(n) = \lfloor \frac{n}{p}\rfloor + g(\lfloor \frac{n}{p}\rfloor)

so~

C_{n}^{m} \operatorname{mod} p^k = \frac{f(n)}{f(m)f(n - m)}p^{g(n) - g(m) - g(n - m)} \operatorname{mod} p^k f(n) = \frac{n!}{p^x} g(n) = x

合并即可

容斥原理

|\mathop{\bigcup}\limits_{i = 1}^{n}A_i| = \sum\limits_{i = 1}^{n}|A_i| - \sum\limits_{i < j}|A_i \cap A_j| + \sum\limits_{i < j < k}|A_i \cap A_j \cap A_k| - \cdots + (-1)^{n - 1}|A_1 \cap A_2 \cap \cdots \cap A_n|

奇数个集合交集个数的系数为正，偶数个集合交集个数的系数为负

这实在没法证就那样不断修正后就这样了

3.乘法逆元

定义：若a \times x \equiv 1 \pmod b,则x是a在模b意义下的乘法逆元，记为a^{-1}

使用：(a/b) \% p = a \times b^{-1} \% p

方法 条件 时间复杂度 备注
费马小定理 模数为素数 O(\log n)
欧拉定理 \gcd(a,p) = 1 O(\sqrt{n})
扩展欧几里得 \gcd(a,p) = 1 O(\log n) 可以判断是否互质
线性递推 模数为素数 O(n)

exgcd:求ax+by=1中x的最小正整数解（如果有的话）

Fermat:可知a^{p - 1} \equiv 1 \pmod p

即a \times a^{p - 2}\%p \equiv 1 \pmod p

则a^{p - 2} \% p为逆元，快速幂求解

Euler:类似于Fermat,a^{\varphi(p)-1}为逆元

线性：对于质数p,求1,2,\cdots,p - 1的逆元

设p = k \times i + r(1<i<p,r <i)

则k \times i + r \equiv 0 \pmod p

则

k \times r ^{-1} + i^{-1} \equiv 0 \pmod p i^{-1} \equiv -k \times r ^{-1} \pmod p i ^{-1} \equiv - \lfloor \frac{p}{i} \rfloor \times r ^{-1} \pmod p i ^{-1} \equiv - \lfloor\frac{p}{i}\rfloor \times (p\mod i)^{-1} \pmod p

即inv[i] = - p / i \times inv[p \%i]

inv[1] = 1

保证非负：inv[i] = (p - p / i) \times inv[p \% i] \% p

4.结论/引理

任意互质的a,n,满足a^x \equiv 1 \pmod n的最小x一定是\varphi(n)的约数

证明：若不是，则有

x \times k +r = \varphi(n)(r < x,k \in Z)

由已知：a^x \equiv a^{\varphi(n)} \equiv 1 \pmod n

则有a ^ {x \times k} \equiv 1^ k \equiv 1 \pmod n

进一步的：a^{x \times k + r} \equiv a ^ r \pmod n ------- a

又因为x已经最小，那么a^r 模n一定不为1（r < x）

又由式子a可得：1\equiv a ^{\varphi(n)} \equiv a^r \pmod n

矛盾！

\gcd(a,b) = \gcd(a + k \times b,b)

证明：

设\gcd(a,b) = d

则a = p\times d,b = q \times d(gcd(p,q) = 1)

则

\begin{aligned} \gcd(a+k \times b,b) &= \gcd(pd+kqd,dq) \\&= \gcd(d(p + k \times q),dq) \\&= d \times \gcd(p+k \times q,q) \end{aligned}

设m | p+k \times q,m|q,则m | p

则\gcd(p+k \times q,q) = m = 1

则\gcd(a+k \times b,b) = d

若a \equiv b \pmod m,则a \times k \equiv b \times k \pmod {m \times k}

证明：

a = s \times m + r b = t \times m + r a \times k - b \times k = (s - t)\times m \times k

则a \times k \equiv b \times k \pmod {m \times k}

组合

常见策略

D(n) = (n - 1) \times (D(n - 1) + D(n - 2))

Catalan数

定义

H(0) = 1,H(1) = 1 H(n) = \sum\limits_{i = 0}^{n - 1}H(i)\times H(n - 1 - i) \begin{aligned} H(n) &=C_{2n}^{n} - C_{2n}^{n-1} \\&= \frac{(2n)!}{n!n!} - \frac{(2n)!}{(n - 1)!(n + 1)!} \\&= \frac{(2n)!}{n!(n - 1)!}(\frac{1}{n} - \frac{1}{n+1}) \\&= \frac{(2n)!}{n!(n-1)!} \times \frac{1}{n(n + 1)} \\&= \frac{(2n)!}{n!n! \times (n+1)} \\&= \frac{1}{n+1}C_{2n}^{n} \end{aligned} H(n) = \frac{4n-2}{n + 1}H(n - 1)

应用：

(1).（典例/特征）从(0,0)走到(n,n),且路径不超过对角线的路径总数为H(n)

证明：

路径总数：C_{2n}^{n}（共2n步，其中n步向上/右）

对角线：y = x

非法路径超过对角线，说明与y = x + 1有交点

将该交点以后的路径关于y = x + 1对称，终点变为(n + 1,n - 1)

也就是说，所有非法路径其实就是从(0,0)到(n + 1,n - 1)的所有路径

那么合法路径就是C_{2n}^{n} - C_{2n}^{n-1}

(2).n个元素进栈序列为1,2,\cdots,n，则出栈序列总数 = H(n)

将进栈抽象为走格子中向右走，出栈抽象为走格子中向上走，又因为一个元素进一次出一次，共2n次，那么就相当于：

从(0,0)走到(n,n)，任意时刻向上走的步数不能超过向右走的步数（出>入），也就是不超过对角线

显然的卡特兰数

(3).n对括号，能够匹配的序列总数

一共2n个符号，左括号n个，右括号n个，记答案为f(2n)（显然，括号里为字符数）

很显然，匹配的序列满足：任意一对括号中必有偶数个字符

我们选定一组括号作为分界，命名为括号W，左括号在第0位，那么右括号在

每一个括号$W$的分布，对答案的贡献是 括号$W$内部的括号匹配排列数 $\times$ 括号$W$外的括号匹配序列数 比如：括号$W$的位置为$0,3$,那么内部有$2$个字符，外部有$2n - 2 - 2 = 2n - 4$个字符，那么贡献就是 $$f(2) \times f(2n - 4)$$ 那么 $$ans = \sum\limits_{i = 1}^{n - 1}f(2i) \times f(2n - 2 - 2i)$$ 由于自变量是字符个数 $= 2 \times$括号个数$n$，实际上这个答案改成以个数为自变量就是 $$ \begin{aligned} ans &= \sum\limits_{i = 1}^{n - 1}f(\frac{2i}{2}) \times f(\frac{2n - 2 - 2i}{2}) \\&= \sum\limits_{i = 0}^{n - 1}f(i)\times f(n - 1 - i) \end{aligned} $$ 形式决定本质：鉴定答案为$H(n)

类似的想法还有

n个节点的不同二叉树排列形式

非根结点总数n - 1，分成两部分（左右子树）排，无了，H(n)

一个凸多边形（顶点数为n）划分成三角形区域的方法数

先选定一个三角形把多边形分成两部分，该三角形占用3个顶点，那么左右的多边形节点总数为n +1个（三角形的一个顶点会被算两次）

那么

ans = \sum\limits_{i = 2}^{n - 1}f(i)\times f(n + 1 - i)

总和为n - 1时答案为H(n)，那么此时答案就是H(n - 2)

总结：Catalan数的运用场景

对应一下：

Prufur序列

构造： $Tree -> Prufur

如图

Prufur -> Tree

如图

（还是以上图中的树为例）

性质：

其中，一一对应（双射）是非常有用的一条性质，这个性质可以让我们对数列（而不是树）进行排列组合以获得方案数而且不用担心重复（一个序列只对应一棵树，序列不同，树一定不同）

应用：

很好理解：n - 2个空，每个空上可填1 \sim n

\frac{(n - 2)!}{\prod\limits_{i = 1}^{n}(d_i - 1)!}

这就是一个重排列问题

如果有k个节点能进入序列，那么每个节点的出现次数一定是d_i - 1，由重排列得到\frac{A_{n - 2}^{n - 2}}{\prod\limits_{i = 1}^{k}A_{d_i - 1}^{d_i - 1}}

又因为(1 - 1)! = 0所以叶子节点的度不影响结果，索性从1到n计算（也省去了求k的时间）

实际中，却总有一些逆天情况

设有m个节点没有度数限制，有k个节点有度数限制

设sum = n - 2 - \sum\limits_{i = 1}^{k}(d_i - 1)，表示剩下的节点还能出现几次

把未知度数的节点视为一个整体，运用重排列得到方案数：\frac{A_{n - 2}^{n - 2}}{\prod\limits_{i = 1}^{k}A_{d_i - 1}^{d_i - 1}\times sum!}

再考虑这个整体内部的方案数，由于无度数限制，直接随便排

ans = \frac{A_{n - 2}^{n - 2}}{\prod\limits_{i = 1}^{k}A_{d_i - 1}^{d_i - 1}\times sum!} \times m^{sum},sum = n - 2 - \sum\limits_{i = 1}^{k}(d_i - 1)

BSGS

已知a,b,p,\gcd(a,p) = 1，求

a^x \equiv b \pmod p

的最小非负整数解

由扩展欧拉定理：a^x \equiv a^{x \operatorname{mod} \varphi(p)}\pmod p

因为\varphi(p) \leqslant p - 1 < p，所以[0,p - 1]中一定有解

设x = im - j,m = \lceil \sqrt{p} \rceil,i \in [1,m],j \in [0,m - 1]

则

a^{im-j} \equiv b \pmod p (a^m)^i \equiv ba^j \pmod p

先枚举j，求出ba^j，用unordered_map存储(ba^j,j)，如果关键字重复，用j大的替代旧的

再枚举i,求出(a^m)^i，如果表中有相同的结果，找到第一个（j最大）就结束，ans = im - j

斯特林数

第一类斯特林数： \begin{bmatrix}n\\m\end{bmatrix}

组合意义：让n个人坐m个圆桌（大小足够且不能有空桌）的方案数

递推：

\begin{bmatrix}n\\m\end{bmatrix} = \begin{bmatrix}n-1\\m - 1\end{bmatrix} + (n - 1)\begin{bmatrix}n - 1\\m\end{bmatrix}

解释：对于一个人，可以让他单独占一张桌子，也可以先让剩下n - 1个人坐m张桌子，然后把这个人插入这些人的左边，共n - 1种方案

第二类斯特林数：\begin{Bmatrix}n\\m\end{Bmatrix}

组合意义：将n个球放入m个盒子中（均相同而且要求非空）的方案数

递推：

\begin{Bmatrix}n\\m\end{Bmatrix} = \begin{Bmatrix}n - 1\\m - 1\end{Bmatrix} + m\begin{Bmatrix}n-1\\m\end{Bmatrix}

解释： 对于一个小球，可以让他单独占一个盒子，或者其他小球先放，他随便放入一个盒子