组合数学初步

· · 算法·理论

组合数学初步

数论初步链接

2026.8.23，已更新完毕！优化了一些格式内容。

本文将围绕数论进阶知识展开，讲解许多有关数论的知识，如果有问题，请指出，作者必将改进（前提你说的是对的）。

一些性质我不给出证明过程，还请谅解！

参考资料：OI-Wiki 数论板块；定理与算法为通用数学知识，证明、例题、行文逻辑为自主整理。

对于一些希腊字母符的读音，参照下图（上大写，下小写）： :::align{center} ::::

加法原理与乘法原理

加法原理

定义：完成一件事有 n 类不同的方案，第一类方案有 m_1 种方法，第 2 类方案有 m_2 种方法，……，第 n 类方案有 m_n 种方法，且这些方案之间互不重叠（即选择了一类就不能选另一类），那么完成这件事共有：

m_1+m_2+\cdots+m_n

种方法。通俗理解就是：“分类相加”。

乘法原理

定义：完成一件事有 n 个独立的步骤，第一步有 m_1 种方法，第 2 步有 m_2 种方法，……，第 n 步有 m_n 种方法，那么完成这件事共有：

m_1\times m_2\times\cdots\times m_n

种方法。通俗理解就是：“分步相乘”。

排列组合

排列

排列研究的是：从 n 个不同的元素中，按顺序选出 k 个元素，有多少种选法？

定义：从 n 个不同元素中取出 k 个（k\le n）排成一列，称为排列，记作 A_n^k 或 P(n,k)，有计算公式：

A_n^k = n \times (n-1) \times \cdots \times (n-k+1) = \dfrac{n!}{(n-k)!}

怎么来的？根据乘法原理，第一个位置有 n 种选择，第二个位置有 n-1 种选择，……，第 k 个位置有 n-k+1 种选择，乘起来即可。

特别的，当 k=n 时，称为全排列，A_n^n=n!。

圆排列

定义：从 n 个不同元素中取出 k 个，排成一个圆环，称为圆排列。

与直线排列不同的是，圆排列没有“起点”，因此旋转后相同的排列被视为同一种。

有计算公式：圆排列数=\dfrac{A_n^k}{k}=\dfrac{n!}{k\cdot(n-k)!}

特别地，n 个元素的全圆排列数为 \dfrac{n!}{n}=(n-1)!。

组合

组合研究的是：从 n 个不同的元素中，无序地选出 k 个元素，有多少种选法？

定义：从 n 个不同元素中，取出 k 个（k\le n）元素并成一组，不考虑顺序，称为从 n 个元素中取 k 个元素的组合，记作 C_n^k 或 \dbinom{n}{k}（注意是反过来的）。

有计算公式：

C_n^k=\dfrac{A_n^k}{k!}=\dfrac{n!}{k!(n-k)!}

怎么来的？由于组合数 C_n^k 表示无序地选出 k 个元素。而排列数 A_n^k 是在组合的基础上，再对选出的 k 个元素进行全排列。

选出的 k 个元素的全排列数为：k!，所以我们得到如下组合与排列的关系：

A_n^k=C_n^k\times k!

将这个关系式简单移项化简就可以得到结论了。

组合数的一些性质

  1. 对称性\binom{n}{k}=\binom{n}{n-k}
  2. 帕斯卡恒等式\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}
  1. 求和公式（n 个元素的所有子集个数）\sum^n_{i=0}\binom{n}{i}=2^n

    多重集组合（隔板法）

    定义：从 n 类元素中（每类元素有无限多个，同类元素完全相同）取出 k 个，叫做多重集组合数，计算公式：

    \binom{n+k-1}{k}=\Large C_{n+k-1}^k

    这就相当于将 k 个相同的球放入 n 个不同的盒子中，允许空盒。等同于在 k+n-1 个位置中选 n-1 个位置放隔板，即

    \binom{n+k-1}{n-1}=\binom{n+k-1}{k}

    多重集和多重集的全排列

    多重集

    由于普通集合（set）中的元素不能重复，所以就有了多重集合（multiset）使得其中的元素可以重复。

    多重集的全排列

    若多重集中有 n 个元素，其中第 i 种元素出现了 k_i 次（\sum k_i=n），则全排列数为：

    \dfrac{n!}{k_1!\cdot k_2!\cdots k_m!}

    推导过程十分简单，先当作所有元素都不同，有 n! 种，再除以同类元素的内部排列数 k_i!。

解析：这个单词里 $\texttt{e}$ 出现了一次，$\texttt{k}$ 出现了两次，$\texttt{i}$ 出现了三次，$\texttt{t}$ 出现了一次，共有七个字符，所以有： $$\dfrac{7!}{1!\cdot2!\cdot3!\cdot1!}=\dfrac{5040}{12}=420$$ 到这里可以发现，当只有两类元素时，全排列数就跟我们的组合数一样了，所以，我们有：**组合数本质上是两类元素的多重集全排列数**。 ### 求组合数的代码实现 #### 预处理阶乘与逆元 当模数 $p$ 为质数且 $n\le 10^6$ 时，可以使用预处理阶乘与逆元（费马小定理），代码如下： ```cpp #include<bits/stdc++.h> #define int long long #define rep(z,x,y) for(int z=x;z<=y;z++) #define drep(z,x,y) for(int z=x;z>=y;z--) using namespace std; const int MAXN=1000005; const int MOD=1e9+7; int fac[MAXN],ifc[MAXN]; int fpw(int a,int b){ int r=1; while(b){ if(b&1) r=r*a%MOD; a=a*a%MOD; b>>=1; } return r; } void init(int n){ fac[0]=1; rep(i,1,n){ fac[i]=fac[i-1]*i%MOD; } ifc[n]=fpw(fac[n],MOD-2); drep(i,n-1,0){ ifc[i]=ifc[i+1]*(i+1)%MOD; } } int C(int n,int k){ if(k<0||k>n) return 0; return fac[n]*ifc[k]%MOD*ifc[n-k]%MOD; } ``` #### 递推法（杨辉三角） 当且仅当 $n\le 2000$ 时，可以递推求解，代码如下： ```cpp #include<bits/stdc++.h> #define int long long #define rep(z,x,y) for(int z=x;z<=y;z++) #define drep(z,x,y) for(int z=x;z>=y;z--) using namespace std; const int MAXN=2005; int C[MAXN][MAXN]; void initC(int n){ rep(i,0,n){ C[i][0]=C[i][i]=1; rep(j,1,i-1){ C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD; } } } ``` #### 多重集全排列 我们知道**组合数本质上是两类元素的多重集全排列数**，所以可以写得如下代码： ```cpp #include<bits/stdc++.h> #define int long long #define rep(z,x,y) for(int z=x;z<=y;z++) #define drep(z,x,y) for(int z=x;z>=y;z--) using namespace std; int fac(int n){ int r=1; rep(i,2,n){ r*=i; } return r; } int msp(vector<int>&cnt,int n){ int ans=fac(n); for(int c:cnt){ ans/=fac(c); } return ans; } ``` 给一道组合数例题：[[GESP202312 八级] 奖品分配](https://www.luogu.com.cn/problem/P10112) ## 等价关系与等价类 ### 等价关系 定义：在一个集合 $S$ 上，如果有一个关系 $\sim$ （等价于），它对任意元素 $a,b,c\in S$ 都满足以下三个性质，则称 $\sim$ 是 $S$ 上的一个等价关系： - 自反性：$a\sim a$（每个元素和自己等价） - 对称性：若 $a\sim b$，则 $b\sim a$（对称） - 传递性：若 $a\sim b$ 且 $b\sim c$，则 $a\sim c$（传递） 最直观的例子就是**模运算同余**。 ### 等价类 定义：把集合里的元素按关系分组。每一组叫做一个等价类。 元素 $a$ 所在的等价类，记作 $[a]$，定义为： $$[a]=\{x\in S\mid x\sim a\}$$ 即所有与 $a$ 等价的元素组成的集合。 以**模 $3$ 同余**为例，整数集 $\mathbb Z$ 被分成了 $3$ 个等价类： - $[0]=\{\dots,-6,-3,0,3,6,\dots\}$（余数为 $0$ 的数） - $[1]=\{\dots,-5,-2,1,4,7,\dots\}$（余数为 $1$ 的数） - $[2]=\{\dots,-4,-1,2,5,8,\dots\}$（余数为 $2$ 的数） 每一个等价类里的数，除以 $3$ 的余数都相同。这些类互不相交，且并起来就是整个 $\mathbb Z$。 等价关系就是“去重”或“去顺序”的数学依据，而我们的**组合数，圆排列数都等于等价类的个数**。 ## 二项式定理 在数学中，我们经常碰到这样一个问题： $$(a+b)^n$$ 想必大家在遇到 $n$ 比较小的时候会暴力拆解吧，但是，有一招很简单的方法，几乎秒出答案。 当展开 $(a+b)^n$ 时，每一项都是从 $n$ 个括号中选若干个取 $b$，其余选 $a$ 的结果。 - 假设 $k$ 个括号取 $b$，剩下 $n-k$ 个取 $a$。 - 那么它的贡献为 $a^{n-k}b^k$。 - 总共有 $\large C_n^k$ 种选法。 所以，我们得出结论： $$(a+b)^n=\sum^n_{k=0}\binom{n}{k}a^{n-k}b^k$$ ### 数学归纳法证明 验证 $n=1$ 的时候原式成立： $$(a+b)^1=\binom{0}{1}a+\binom{1}{0}b=a+b$$ 假设 $n$ 时原式也成立，证明 $n+1$ 时也成立： $$(a+b)^{n+1}=(a+b)(a+b)^n=(a+b)\sum^n_{k=0}\binom{n}{k}a^{n-k}b^k$$ 展开得到： $$=\sum^n_{k=0}\binom{n}{k}a^{n-k+1}b^k+\sum^n_{k=0}\binom{n}{k}a^{n-k}b^{k+1}$$ 我们令 $j=k+1$： $$=\sum^n_{k=0}\binom{n}{k}a^{n-k+1}b^k+\sum^{n+1}_{j=1}\binom{n}{j-1}a^{n-j+1}b^{j}$$ 合并同类项，利用帕斯卡恒等式 $\Large\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ 得到： $$=\sum^{n+1}_{k=0}\binom{n+1}{k}a^{n-k+1}b^k$$ ### 与杨辉三角的关系 我们枚举 $n=0,1,2,3,4,5$ 的情况观察一下： $$(a+b)^0=1$$ $$(a+b)^1=a+b$$ $$(a+b)^2=a^2+2ab+b^2$$ $$(a+b)^3=a^3+3a^2b+3ab^2+b^3$$ $$(a+b)^4=a^4+4a^3b+6a^2b^2+4ab^3+b^4$$ $$(a+b)^5=a^5+5a^4b+10a^3b^2+10a^2b^3+5ab^4+b^5$$ 我们将上述系数排列出来，可以得到**杨辉三角**： ```cpp n=0: 1 n=1: 1 1 n=2: 1 2 1 n=3: 1 3 3 1 n=4: 1 4 6 4 1 n=5: 1 5 10 10 5 1 ``` 且第 $n$ 行的第 $k$ 个数就是 $\Large\binom{n}{k}$。 ## 一些推论 ### 推论1：令 $a=1,b=1 2^n=\sum^n_{k=0}\binom{n}{k}

含义：n 个元素的所有子集个数为 2^n。这也体现了组合数学与二进制的关系。

推论2：令 a=1,b=-1

0=\sum^n_{k=0}(-1)^k\binom{n}{k}\iff\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\dots=\binom{n}{1}+\binom{n}{3}+\binom{n}{5}+\dots=2^{n-1}

含义：偶数大小子集和奇数大小子集各占一半。

推论3：令 b=1

(1+a)^n=\sum^n_{k=0}\binom{n}{k}a^k

这就是生成函数的雏形。

推论4：求导

对 (1+a)^n=\sum^n_{k=0}\binom{n}{k}a^k 求导：

n(1+a)^{n-1}=\sum^n_{k=1}k\binom{n}{k}a^{k-1}

我们令 a=1：

n\cdot2^{n-1}=\sum^n_{k=1}k\binom{n}{k}

推论5：曲棍球棒恒等式

标准的曲棍球棒恒等式是：

\sum^k_{i=0}\binom{r+i}{i}=\binom{r+k+1}{k}

如果我们令 r=n-1，就会得到：

\sum^k_{i=0}\binom{n-1+i}{i}=\binom{n+k}{k}

推论6：范德蒙德卷积

\binom{a+b}{n}=\sum^n_{i=0}\binom{a}{i}\binom{b}{n-i}\iff\binom{a+b}{n}=\sum^n_{i=0}\binom{a}{n-i}\binom{b}{i}

我们令 a=b=n 可以得到：

\binom{2n}{n}=\sum^n_{i=0}\binom{n}{i}^2

再令 b=-b 呢？

\binom{a-b}{n}=\sum^n_{i=0}\binom{a}{i}\binom{-b}{n-i}

上面的公式就是广义的范德蒙德卷积。

负组合数

当上标为负数时，组合数的定义为：

\binom{-n}{m}=\dfrac{(-n)(-n-1)(-n-2)\cdots(-n-m+1)}{m!}

广义二项式定理

当指数 n 不是非负整数时，二项式定理可以推广到实数或复数指数：

(1+x)^{\alpha}=\sum^{\infty}_{k=0}\binom{\alpha}{k}x^k \text{e.g.}\quad\alpha=-1 (1+x)^{-1}=1-x+x^2-x^3+\cdots=\sum^{\infty}_{k=0}(-1)^k x^k

三项展开（多项式定理）

(a+b+c)^n=\sum_{i+j+k=n}\dfrac{n!}{i!j!k!}a^ib^jc^k

证明方式跟二项式定理的证明几乎一模一样，这里不再解释。

对于任意 m 项：

(x_1+x_2+x_3+\cdots+x_m)^n=\sum_{k_1+k_2+k_3+\cdots+k_m=n}\dfrac{n!}{k_1!k_2!k_3!\cdots k_m!}x_1^{k_1}x_2^{k_2}x_3^{k_3}\cdots x_m^{k_m}

这是二项式定理的推广，系数为多项分布系数（多重集全排列数）。

二项式反演

二项式反演是组合数学中最重要的反演公式之一。它描述了两种组合数求和之间的互逆关系：

如果：

f(n)=\sum^n_{i=0}\binom{n}{i}g(i)

那么：

g(n)=\sum^n_{i=0}(-1)^{n-i}\binom{n}{i}f(i)

这两个公式互为反演，即两个可以相互推导出来。

简单证明一下：代入即可，核心是使用恒等式 \large\binom{n}{i}\binom{i}{j} = \binom{n}{j}\binom{n-j}{i-j} 和二项式定理。

错位排列

定义：n 个元素的一个排列，使得没有任何一个元素处于它原来的位置。记作 D_n 或 !n

列举一下前几项：

D_1=0,D_2=1,D_3=2,D_4=9,D_5=44,D_6=265

从而得到递推公式：

D_n=(n-1)(D_{n-1}+D_{n-2})

怎么来的？考虑第 n 个元素放在位置 k(k\ne n)，有 n-1 种选择。而位置 k 上的元素有两种去向：

  1. 放到位置 n，剩下 n-2 个元素错排：D_{n-2}。
  2. 不放到位置 n，剩下 n-1 个元素错排：D_{n-1}。

    近似值

    如果 n 超级大时：

    D_n\approx\dfrac{n!}{e}

    因为 \sum^{\infty}_{j=0}\dfrac{(-1)^j}{j!}=e^{-1}，所以错位排列数约等于全排列数的 \dfrac{1}{e}\approx36.8\%。

    代码实现

    递推法

    #include<bits/stdc++.h>
#define int long long
#define rep(z,x,y) for(int z=x;z<=y;z++)
#define drep(z,x,y) for(int z=x;z>=y;z--)
using namespace std;
const int maxn=25;
int f[maxn],n;
signed main(){
 ios::sync_with_stdio(false);
 cin.tie(nullptr),cout.tie(nullptr);
 cin>>n;
 f[1]=0;
 f[2]=1;
 f[3]=2;
 if(n==1||n==2||n==3){
     cout<<f[n]<<'\n';
     return 0;
 }
 rep(i,4,n){
     f[i]=(i-1)*(f[i-1]+f[i-2]);
 }
 cout<<f[n]<<'\n';
 return 0;
}

    抽屉原理

    抽屉原理（Pigeonhole Principle），也叫鸽巢原理，是组合数学中最简单、最直观，却也最深刻的原理之一。

它的表述极其简单，但应用起来却变化万千，能解决许多看似困难的问题。有人说：“抽屉原理是数学中少数几个既显然又深刻的定理之一。”

基本形式

证明也比较简单，使用反证法。若每个抽屉最多放 \lceil\dfrac{m}{n}\rceil-1 个，则总数最多为：

n\times(\lceil\dfrac{m}{n}\rceil-1)<m

这就矛盾了，所以得证。

一些应用

这个过程形象地称为 “多退少补” 。

基本形式

对于两个有限集合 A 和 B，有：

\lvert A\cup B\rvert=\lvert A\rvert+\lvert B\rvert-\lvert A\cap B\rvert

在小学的时候，我们学过维恩图，他就是两个圆重叠，\lvert A\rvert+\lvert B\rvert 将重叠部分 \lvert A\cap B\rvert 算了两次，所以需要减去一次。

$$\lvert A_2\cup A_3\rvert=\lvert A_2\rvert+\lvert A_3\rvert-\lvert A_2\cap A_3\rvert=50+33-16=67$$ 扩展一下呢？对于三个有限集合 $A,B,C$，有： $$\lvert A\cup B\cup C\rvert=\lvert A\rvert+\lvert B\rvert+\lvert C\rvert-\lvert A\cap B\rvert-\lvert B\cap C\rvert-\lvert A\cap C\rvert+\lvert A\cap B\cap C\rvert$$ 三个圆重叠，先加三个单独区域（多加了两次两两重叠），减掉三个两两重叠（又多减了一次三重重叠），再加回三重重叠。 如果我们扩展到 $n$ 个呢？对于 $n$ 个有限集合 $A_1,A_2,\dots A_n$，有： $$ \left|\bigcup_{i=1}^{n} A_i\right| = \sum_{i=1}^{n}|A_i| - \sum_{1\le i<j\le n}|A_i\cap A_j| + \sum_{1\le i<j<k\le n}|A_i\cap A_j\cap A_k| -\dots + (-1)^{n-1}\left|A_1\cap A_2\cap \dots \cap A_n\right| $$ 用求和符号简写： $$ \left|\bigcup_{i=1}^{n} A_i\right| = \sum_{\varnothing\neq S\subseteq \{1,2,\dots,n\}} (-1)^{|S|+1} \left|\bigcap_{i\in S} A_i\right| $$ ### 证明 方法：数学归纳法 第 $1$ 步：$n=1$ 时显然成立：$|A_1| = |A_1|$。 第 $2$ 步：$n=2$ 时成立，作为归纳基础。 第 $3$ 步：假设 $n-1$ 时成立，证明 $n$ 时也成立。 令 $B = A_1 \cup A_2 \cup \dots \cup A_{n-1}$，则： $$\left|\bigcup_{i=1}^{n} A_i\right|= |B \cup A_n|= |B| + |A_n| -|B\cap A_n|$$ 而： $$ B \cap A_n = (A_1 \cap A_n) \cup (A_2 \cap A_n) \cup \dots \cup (A_{n-1} \cap A_n)$$ 对 $n-1$ 个集合 $A_1\cap A_n,\,A_2\cap A_n,\dots,A_{n-1}\cap A_n$，应用归纳假设： $$|B \cap A_n|=\sum_{\varnothing\neq S\subseteq \{1,\dots,n-1\}}(-1)^{|S|+1}\left|\bigcap_{i\in S}(A_i \cap A_n)\right|$$ 代入整理即可得到 $n$ 时的公式。 ### 应用（欧拉函数） 设 $n = p_1^{\alpha_1} p_2^{\alpha_2}\cdots p_k^{\alpha_k}$，求 $\varphi(n)$。 $\varphi(n)$ 表示 $1$ 到 $n$ 中与 $n$ 互质的数的个数。 设 $A_i$ 表示 $1$ 到 $n$ 中能被 $p_i$ 整除的数的集合。 $$|A_i|=\frac{n}{p_i},\quad |A_i\cap A_j|=\frac{n}{p_ip_j},\ \dots$$ 需要排除所有能被至少一个 $p_i$ 整除的数： $$\begin{aligned}\varphi(n) &= n-\sum_i \frac{n}{p_i}+\sum_{i<j}\frac{n}{p_ip_j}-\cdots \\&= n\left(1-\sum_i \frac{1}{p_i}+\sum_{i<j}\frac{1}{p_ip_j}-\cdots\right) \\&= n\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right)\end{aligned}$$ 而这就是欧拉函数的通项公式，与数论初步中的内容完美呼应。 ### 一个问题的代码实现 给定一个 $n$，让你求 $1\sim n$ 中与 $m$ 互质的个数。 思路就是对 $m$ 进行质因数分解，然后用容斥原理扣除能被某个质因子整除的数。代码如下： ```cpp #include<bits/stdc++.h> #define int long long #define rep(z,x,y) for(int z=x;z<=y;z++) #define drep(z,x,y) for(int z=x;z>=y;z--) using namespace std; int cpc(int n,int m){ vector<int>pr; int tmp=m; for(int i=2;i*i<=tmp;i++){ if(tmp%i==0){ pr.push_back(i); while(tmp%i==0) tmp/=i; } } if(tmp>1) pr.push_back(tmp); int k=pr.size(); int ans=n; for(int ms=1;ms<(1<<k);ms++){ int bt=__builtin_popcount(ms); int prod=1; for(int i=0;i<k;i++){ if(ms&(1<<i)) prod*=pr[i]; } if(bt&1) ans-=n/prod; else ans+=n/prod; } return ans; } ``` ### 对偶形式 对于补集，有对偶形式： $$\left|\bigcap_{i=1}^{n} A_i\right|=\lvert U\rvert-\left|\bigcup_{i=1}^n\overline{A_i}\right|$$ 即：同时满足所有条件的个数 = 总数 - 至少不满足一个条件的个数。 ## 卡特兰数 卡特兰数（Catalan Number）是组合数学中出现频率最高的数列之一。它计数的问题多到令人惊讶——从括号匹配到二叉树，从进出栈到多边形剖分，看似完全不相干的问题，答案竟然都是同一个数列。 列举一下前几项： $$1,1,2,5,14,42,132,429,1430,4862$$ ### 定义 卡特兰数 $C_n$（注意不是组合数），有多种等价的定义方式： **递推定义：** $$C_0=1,\quad C_{n+1}=\sum^n_{i=0}C_iC_{n-i}$$ **通项公式：** $$C_n=\dfrac{1}{n+1}\binom{2n}{n}=\binom{2n}{n}-\binom{2n}{n+1}$$ #### 对于通项公式的推导： ##### 生成函数法 设卡特兰数的生成函数为 $F(x)=\sum^{\infty}_{n=0}C_nx^n$。 由递推式 $C_{n+1}=\sum^n_{i=0}C_iC_{n-i}$ 得到： $$F(x)-1=xF(x)^2$$ 来解这个二次方程： $$F(x)=\dfrac{1-\sqrt{1-4x}}{2x}$$ 展开 $\sqrt{1-4x}$，比较系数可以得到： $$C_n=\dfrac{1}{n+1}\binom{2n}{n}$$ ### 一些运用 - $n$ 对括号的合法匹配。 - $n$ 个元素依次进栈，有多少种不同的出栈序列。 - 具有 $n$ 个节点的不同形态的二叉树有多少种。 - 一个凸 $n+2$ 边形，可以划分成多少个三角形。 ### 代码实现 #### 通项公式法 当 $n$ 在 $10^6$ 的级别时，且模数 $p$ 为质数时： ```cpp #include<bits/stdc++.h> #define int long long #define rep(z,x,y) for(int z=x;z<=y;z++) #define drep(z,x,y) for(int z=x;z>=y;z--) using namespace std; const int MAXN=2000005; const int MOD=1e9+7; int fac[MAXN],ifc[MAXN]; int fpw(int a,int b){ int r=1; while(b){ if(b&1) r=r*a%MOD; a=a*a%MOD; b>>=1; } return r; } void init(int n){ fac[0]=1; rep(i,1,n){ fac[i]=fac[i-1]*i%MOD; } ifc[n]=fpw(fac[n],MOD-2); drep(i,n-1,0){ ifc[i]=ifc[i+1]*(i+1)%MOD; } } int C(int n,int k){ if(k<0||k>n) return 0; return fac[n]*ifc[k]%MOD*ifc[n-k]%MOD; } int cat(int n){ return C(2*n,n)*fpw(n+1,MOD-2)%MOD; } signed main(){ ios::sync_with_stdio(false); cin.tie(nullptr),cout.tie(nullptr); init(2000000); cout<<cat(3)<<'\n'; cout<<cat(4)<<'\n'; cout<<cat(5)<<'\n'; return 0; } ``` #### 递推法 当不需要取模，或 $n$ 较小时： ```cpp int cat(int n){ vector<int>c(n+1); c[0]=1; rep(i,1,n){ c[i]=c[i-1]*2*(2*i-1)/(i+1); } return c[n]; } ``` 递推的公式推导也比较简单： $$C_n = \dfrac{1}{n+1}\binom{2n}{n},\quad C_{n-1} = \dfrac{1}{n}\binom{2n-2}{n-1}$$ $$\dfrac{C_n}{C_{n-1}}=\dfrac{\dfrac{1}{n+1}\binom{2n}{n}}{\dfrac{1}{n}\binom{2n-2}{n-1}}=\dfrac{n}{n+1}\cdot\dfrac{(2n)(2n-1)}{n^2}=\dfrac{2(2n-1)}{n+1}$$ 所以： $$C_n=\dfrac{2(2n-1)}{n+1}C_{n-1}$$ ## 斯特林数 斯特林数（Stirling Number）是组合数学中研究划分结构的核心工具，分为两大类： | 类型 | 研究对象 | 记法 | |:-:|:-:|:-:| | 第一类斯特林数 | 排列成轮换 | $s(n,k)$ 或 $c(n,k)$ | | 第二类斯特林数 | 划分成子集 | $S(n,k)$ 或 $\large\left\{n \atop k\right\}$ | ### 第二类斯特林数 定义：$S(n,k)$ 表示将 $n$ 个不同元素划分成 $k$ 个非空子集的方案数。 #### 递推公式 $$S(n,k)=S(n-1,k-1)+k\cdot S(n-1,k)$$ 对于初始值 $S(0,0)=1,S(n,0)=0,S(n,n)=1$。 推导：考虑第 $n$ 个元素： 1. 自成一组：剩下 $n-1$ 个元素分为 $k-1$ 组，方案数为 $S(n-1,k-1)$。 2. 加入已有组：先给剩下 $n-1$ 个元素分成 $k$ 组，共有 $S(n-1,k)$ 种分法。第 $n$ 个元素可以加入其中任意一组，有 $k$ 中选择。 两种情况相加即得递推式。 #### 通项公式 $$S(n,k)=\dfrac{1}{k!}\sum^k_{i=0}(-1)^{k-i}\binom{k}{i}i^n$$ 推导思路：用容斥原理。先给每个元素分配一个组编号（$k^n$种），减去有空组的方案，最后除以 $k!$ 消去组编号的顺序。 #### 前几项： $$\begin{array}{c|ccccccc}n\backslash k & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\\hline0 & 1 \\1 & 0 & 1 \\2 & 0 & 1 & 1 \\3 & 0 & 1 & 3 & 1 \\4 & 0 & 1 & 7 & 6 & 1 \\5 & 0 & 1 & 15 & 25 & 10 & 1 \\6 & 0 & 1 & 31 & 90 & 65 & 15 & 1\end{array}$$ #### 代码实现 ##### 递推法 ```cpp #include<bits/stdc++.h> #define int long long #define rep(z,x,y) for(int z=x;z<=y;z++) #define drep(z,x,y) for(int z=x;z>=y;z--) using namespace std; const int MOD=1e9+7; int s2(int n,int k){ if(k<0||k>n) return 0; vector<vector<int>>S(n+1,vector<int>(k+1,0)); S[0][0]=1; rep(i,1,n){ rep(j,1,min(i,k)){ S[i][j]=(S[i-1][j-1]+j*S[i-1][j])%MOD; } } return S[n][k]; } ``` ##### 通项公式法 ```cpp int s2f(int n,int k){ int ans=0; rep(i,0,k){ int tm=C(k,i)*fpw(i,n)%MOD; if((k-i)&1) ans=(ans-tm+MOD)%MOD; else ans=(ans+tm)%MOD; } return ans*ifc[k]%MOD; } ``` ### 第一类斯特林数 定义：$s(n,k)$ 表示将 $n$ 个不同元素划分成 $k$ 个非空轮换的方案数。 什么是轮换？轮换（cycle）是一种环形排列。例如，$(1\ 2\ 3)$ 表示 $1 \to 2 \to 3 \to 1$ 的循环。 轮换 $(1\ 2\ 3)$ 和 $(2\ 3\ 1)$ 表示同一个轮换（只是起点不同），但 $(1\ 3\ 2)$ 是另一个轮换。 $\text{e.g.}$ $3$ 个元素排列成 $2$ 个轮换： - $(1)\circ(2\ 3)$：$1$ 不动，$2$ 和 $3$ 互换 - $(2)\circ(1\ 3)

共 3 种，所以 s(3,2)=3。

两种版本

第一类斯特林数有两种版本：

版本 记法 递推公式 关系
无符号 c(n,k) c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k) c(n,k)\ge 0
有符号 s(n,k) s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k) s(n,k)=(-1)^{n-k}c(n,k)

对于初值：c(0,0)=s(0,0)=1,\ c(n,0)=s(n,0)=0\ (n>0)。

关系：

s(n,k)=(-1)^{n-k}c(n,k)

递推公式推导

考虑第 n 个元素：

  1. 自成轮换：剩下 n-1 个元素排成 k-1 个轮换，方案数为 c(n-1,k-1)。
  2. 插入已有轮换：先给剩下 n-1 个元素排成 k 个轮换，共有 c(n-1,k) 种。第 n 个元素可以插入任意一个轮换的任意一个元素后面，有 n-1 种选择。

所以：

c(n,k)=c(n-1,k-1)+(n-1)\cdot c(n-1,k)

有符号版本：

s(n,k)=s(n-1,k-1)-(n-1)\cdot s(n-1,k)

前几项

\begin{array}{c|ccccccc}n\backslash k & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\\hline0 & 1 \\1 & 0 & 1 \\2 & 0 & 1 & 1 \\3 & 0 & 2 & 3 & 1 \\4 & 0 & 6 & 11 & 6 & 1 \\5 & 0 & 24 & 50 & 35 & 10 & 1 \\6 & 0 & 120 & 274 & 225 & 85 & 15 & 1\end{array}

代码实现

int s1(int n,int k){
    if(k<0||k>n)
        return 0;
    vector<vector<int>>s(n+1,vector<int>(k+1,0));
    s[0][0]=1;
    rep(i,1,n){
        rep(j,1,min(i,k)){
            s[i][j]=(s[i-1][j-1]+(i-1)*s[i-1][j])%MOD;
        }
    }
    return s[n][k];
}

两类斯特林数的联系

若将 x^n 和 x^{\underline{n}} 用两类斯特林数联系：

x^n=\sum_{k=0}^{n} S(n,k)\cdot x^{\underline{k}} x^{\underline{n}}=\sum_{k=0}^{n} s(n,k)\cdot x^{k}

其中 x^{\underline{n}}=x(x-1)(x-2)\cdots(x-n+1) 是下降阶乘。

这意味着两类斯特林数的矩阵互为逆矩阵。

贝尔数

定义：贝尔数 B_n 表示将 n 个不同元素划分成若干个非空子集的方案总数。

B_n=\sum_{k=0}^{n} S(n,k)

其中 S(n,k) 是第二类斯特林数。

列举一下前几项：

B_0=1,\,B_1=1,\,B_2=2,\,B_3=5,\,B_4=15,\,B_5=52,\,B_6=203,\dots

递推公式

B_{n+1}=\sum_{k=0}^{n}\binom{n}{k}B_k

推导：先选定包含元素 n+1 的子集，从剩下 n 个元素中选 k 个与它放在一起，剩下 n-k 个元素任意划分。

代码实现

int bel(int n){
    vector<int>b(n+1);
    b[0]=1;
    rep(i,0,n-1){
        b[i+1]=0;
        rep(k,0,i){
            b[i+1]=(b[i+1]+C(i,k)*b[k])%MOD;
        }
    }
    return b[n];
}

给一道例题吧，比较综合：十二重计数法【弱化版】。

本题就是考察十二种盒子与球的计数方法，本人的参考代码： ::::info[十二重计数法【弱化版】代码]

include<bits/stdc++.h>

define int long long

define rep(z,x,y) for(int (z)=(x);(z)<=(y);(z)++)

define drep(z,x,y) for(int (z)=(x);(z)>=(y);(z)--)

using namespace std; const int MOD=998244353; const int MAXN=2005; int f[MAXN],niyuan[MAXN],s[MAXN][MAXN],b[MAXN][MAXN]; int C(int n,int k){ if(k<0||k>n) return 0; return f[n]niyuan[k]%MODniyuan[n-k]%MOD; } int qpow(int a,int b){ int r=1; while(b){ if(b&1) r=ra%MOD; a=aa%MOD; b>>=1; } return r; } signed main(){ // freopen(".in","r",stdin); // freopen(".out","w",stdout); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m; cin>>n>>m; f[0]=1; rep(i,1,MAXN-1){ f[i]=if[i-1]%MOD; } niyuan[MAXN-1]=qpow(f[MAXN-1],MOD-2); drep(i,MAXN-2,0) niyuan[i]=niyuan[i+1](i+1)%MOD; s[0][0]=1; rep(i,1,MAXN-1){ rep(j,1,i){ s[i][j]=(s[i-1][j-1]+js[i-1][j])%MOD; } } rep(i,0,MAXN-1) b[0][i]=1; rep(i,1,MAXN-1){ rep(j,1,MAXN-1){ b[i][j]=b[i][j-1]; if(i>=j) b[i][j]=(b[i][j]+b[i-j][j])%MOD; } } int sum4=0; rep(i,1,m) sum4=(sum4+s[n][i])%MOD; cout<<qpow(m,n)<<endl; if(n>m) cout<<0<<endl; else cout<<f[m]niyuan[m-n]%MOD<<endl; if(n<m) cout<<0<<endl; else cout<<f[m]*s[n][m]%MOD<<endl; cout<<sum4<<endl; if(n<=m) cout<<1<<endl; else cout<<0<<endl; if(n<m) cout<<0<<endl; else cout<<s[n][m]<<endl; cout<<C(n+m-1,m-1)<<endl; cout<<C(m,n)<<endl; if(n<m) cout<<0<<endl; else cout<<C(n-1,m-1)<<endl; cout<<b[n][m]<<endl; if(n<=m) cout<<1<<endl; else cout<<0<<endl; if(n<m) cout<<0<<endl; else cout<<b[n-m][m]<<endl; return 0; } :::: 到这里，组合数学初步知识就到此为止了，希望你能有所收获。

附：涉及到本文的模板如下： ::::info[所有模板代码]

#include<bits/stdc++.h>
#define int long long
#define rep(z,x,y) for(int z=x;z<=y;z++)
#define drep(z,x,y) for(int z=x;z>=y;z--)
using namespace std;

const int MAXN = 2000005;
const int MOD = 1e9 + 7;

int fac[MAXN], ifc[MAXN];

// 快速幂
int fpw(int a, int b){
    int r = 1;
    while(b){
        if(b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

// 预处理阶乘、阶乘逆元，n为最大范围
void init(int n){
    fac[0] = 1;
    rep(i, 1, n){
        fac[i] = fac[i-1] * i % MOD;
    }
    ifc[n] = fpw(fac[n], MOD - 2);
    drep(i, n-1, 0){
        ifc[i] = ifc[i+1] * (i+1) % MOD;
    }
}

// 组合数 C(n,k)
int C(int n, int k){
    if(k < 0 || k > n) return 0;
    return fac[n] * ifc[k] % MOD * ifc[n - k] % MOD;
}

// ========== 杨辉三角递推求组合数，n<=2000 ==========
const int MAXY = 2005;
int cyh[MAXY][MAXY];
void initC(int n){
    rep(i, 0, n){
        cyh[i][0] = cyh[i][i] = 1;
        rep(j, 1, i-1){
            cyh[i][j] = (cyh[i-1][j-1] + cyh[i-1][j]) % MOD;
        }
    }
}

// ========== 多重集全排列 ==========
int fac_big(int n){
    int r = 1;
    rep(i, 2, n) r *= i;
    return r;
}
int msp(vector<int>& cnt, int n){
    int ans = fac_big(n);
    for(int c : cnt){
        ans /= fac_big(c);
    }
    return ans;
}

// ========== 错位排列 D_n ==========
int derange(int n){
    const int maxd = 25;
    vector<int> f(maxd + 1);
    f[1] = 0;
    f[2] = 1;
    rep(i, 3, n){
        f[i] = (i - 1) * (f[i-1] + f[i-2]);
    }
    return f[n];
}

// ========== 容斥：求1~n中与m互质的数的个数 ==========
int cpc(int n, int m){
    vector<int> pr;
    int tmp = m;
    for(int i = 2; i * i <= tmp; i++){
        if(tmp % i == 0){
            pr.push_back(i);
            while(tmp % i == 0) tmp /= i;
        }
    }
    if(tmp > 1) pr.push_back(tmp);
    int k = pr.size();
    int ans = n;
    for(int ms = 1; ms < (1 << k); ms++){
        int bt = __builtin_popcount(ms);
        int prod = 1;
        rep(i, 0, k-1){
            if(ms & (1 << i)) prod *= pr[i];
        }
        if(bt & 1) ans -= n / prod;
        else ans += n / prod;
    }
    return ans;
}

// ========== 卡特兰数 C_n = 1/(n+1)*C(2n,n) ==========
int cat(int n){
    return C(2*n, n) * fpw(n + 1, MOD - 2) % MOD;
}

// ========== 第二类斯特林数 S(n,k) 递推版 ==========
int s2(int n, int k){
    if(k < 0 || k > n) return 0;
    vector<vector<int>> S(n+1, vector<int>(k+1, 0));
    S[0][0] = 1;
    rep(i, 1, n){
        rep(j, 1, min(i, k)){
            S[i][j] = (S[i-1][j-1] + j * S[i-1][j]) % MOD;
        }
    }
    return S[n][k];
}

// 第二类斯特林数 通项公式（需要预处理fac,ifc）
int s2f(int n, int k){
    int ans = 0;
    rep(i, 0, k){
        int tm = C(k, i) * fpw(i, n) % MOD;
        if((k - i) & 1) ans = (ans - tm + MOD) % MOD;
        else ans = (ans + tm) % MOD;
    }
    return ans * ifc[k] % MOD;
}

// ========== 第一类无符号斯特林数 c(n,k) ==========
int s1(int n, int k){
    if(k < 0 || k > n) return 0;
    vector<vector<int>> s(n+1, vector<int>(k+1, 0));
    s[0][0] = 1;
    rep(i, 1, n){
        rep(j, 1, min(i, k)){
            s[i][j] = (s[i-1][j-1] + (i-1) * s[i-1][j]) % MOD;
        }
    }
    return s[n][k];
}

// ========== 贝尔数 B_n ==========
int bel(int n){
    vector<int> b(n+1);
    b[0] = 1;
    rep(i, 0, n-1){
        b[i+1] = 0;
        rep(k, 0, i){
            b[i+1] = (b[i+1] + C(i, k) * b[k]) % MOD;
        }
    }
    return b[n];
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init(2000000);
    // 样例调用
    // cout << C(5,2) << '\n';
    // cout << cat(5) << '\n';
    // cout << s2(5,2) << '\n';
    // cout << s1(5,2) << '\n';
    // cout << bel(5) << '\n';
    return 0;
}

:::: 感谢你的观看，组合数学初步，至此完。