组合计数问题是组合数学中重要的最古典的分支。有人将组合计数问题归为 \(12\) 个集合映射问题。但是其中有 \(2\) 个是平凡的，所以我们只研究 \(10\) 个。
十二重计数法
在数学上，严谨的定义是“从一个集合对另一个集合的映射的个数”。但是我们可以用更简单的方法定义它：把 \(n\) 个苹果装进 \(m\) 个盒子的方案数。
首先，我们根据集合的性质来进行分类。对集合 \(S\)，如果在映射的过程中，我们令打乱 \(S\) 中的数的顺序后得到的映射和原先的映射是等价的，我们就可以把 \(S\) 中的数划分为同一个等价类，这时我们称 \(S\) 中的元素是不区分的。也就是，所有的苹果 \(/\) 盒子都是相同的。因为有两个集合 \(N\) 和 \(M\)，所以一共能分 \(4\) 种。
其次，我们按照映射的性质来分类，分为“不受限”“单射”和“满射”。也就是，每个盒子随便装、最多装一个、最少装一个。
这样，我们列出一张 \(3*4\) 的表，表示所有 \(12\) 种问题。不过其中有 \(2\) 个是平凡的。分别是 XI 和 VIII。
| \(N\) | \(M\) | 不受限 | 单射 | 满射 |
|---|---|---|---|---|
| 区分 | 区分 | I | II | III |
| 不区分 | 区分 | IV | V | VI |
| 区分 | 不区分 | VII | VIII | IX |
| 不区分 | 不区分 | X | XI | XII |
计数公理
映射法则
对于集合 \(S\) 和 \(T\)，其中若存在映射 \(f:S\rightarrow T\) 满足：
-
\(f\) 是单射，则 \(|S|\le|T|\)
-
\(f\) 是满射，则 \(|S|\ge|T|\)
-
\(f\) 是双射，则 \(|S|=|T|\)
法则本身的内容只涉及第三条，剩余两条是补充的。其意义在于如果两个集合中的所有元素一一对应，则两者元素数量相同。
实际上，双射法则常常出现在很多的定义中，
乘法法则
不同的代数对象有不同的乘法法则，例如生成函数中的乘法法则就和集合计数的乘法法则不同。
两个集合的笛卡尔积 \(S\times T\) 的定义是 \(\{(a,b)|a\in S,b\in T\}\)
\(|S\times T|=|S|\cdot|T|\)
乘法法则的应用情形是比较好判断和容易使用的。
加法法则
两个不相交的集合 \(S\) 和 \(T\)，\(|S\cup T|=|S|+|T|\)
加法法则则不好运用，因为其满足的条件相较苛刻，应用情形难以直观看出，更具技巧性。
组合数
子集总数
组合数是有穷集合的子集。
定义 \([n]\) 的幂集 \(2^{[n]}=\{S|S\subseteq [n]\}\)
我们证明 \(|2^{[n]}|=2^n\)
组合的证明方法是把 \(S\) 表示为一个长 \(n\) 的 \(0/1\) 特征向量（编码集合）。
具体而言，对于 \(i\in [n]\)，如果 \(i\in S\)，则特征向量的这一位是 \(1\)，否则是 \(0\)。我们从而建立了特征向量和子集的双射。而特征向量是 \(\{0,1\}^n\)，根据乘法法则，就是 \(2^n\)
或者，我们定义 \(f(n)=|2^{[n]}|\)，然后把 \(2^{[n]}\) 表示成 \(\{ S\subseteq [n]|n\in S\}\cup\{ S\subseteq [n]|n\notin S\}\)
则前后无交集且存在双射，都是 \(2^{[n-1]}\)
所以 \(f(n)=2f(n-1)\)
而且 \(2^{\varnothing}=1\) 是良定义的，所以 \(f(n)=|2^n|\)
现在我们在解的是比较简单的线性递推式，那么别的线性递推呢？例如 \(f(n)=a_1f(n-1)+a_2f(n-2)+\cdots+a_kf(n-k)+a_0\)？
这就需要使用生成函数的知识解决，例如我的这篇博客讲解了斐波那契数列的通项。
子集
我们定义 \(\text{k-uniform}\) 为 \({S\choose k}=\{T\subseteq S|\ |T|=k\}\)。它涉及到 \(\text{k-complete hypergraph}\) 的一些内容。
十二重计数法
I：\(\text{Tuples}\)
我们定义 \([m]\) 是小于等于 \(m\) 的正整数的集合，那么 \([m]=\{1,2,\cdots,m\}\)。
根据乘法原则，它的 \(n\) 次笛卡尔积 \([m]^n\) 的大小 \(|[m]^n|\) 就是值域为 \([1,m]\) 的 \(n\) 元组的个数。
那么我们定义 \(f:[n]\rightarrow [m]\)，找到 \(f\) 的真值向量 \((f(1),f(2),\cdots,f(n))\)，这个向量的集合就和映射的集合建立了双射。同时它还和值域为 \([1,m]\) 的 \(n\) 元组建立了双射。
那么，映射的个数就是 \(m^n\)。
II：\(\text{Permutation}\)
我们还是找到 \(f\) 的真值向量 \((f(1),f(2),\cdots,f(n)\)。但是因为是单射，所以 \((f(1),f(2),\cdots,f(n))\) 是一个排列 \(\pi\)，它是 \([m]^n\) 的一个子集。
我们考虑别的方法，我们发现，确定第一位的时候有 \(m\) 种，第二位有 \(m-1\) 种……最终一共有 \(m(m-1)(m-2)\cdots(m-n+1)\) 种。我们记作 \((m)_n\)，或者 \(m^{\underline{n}}\)，也就是 \(m\) 的 \(n\) 次下降幂。
至于严格论证，我们需要链式法则，它不包含于上述法则众，因为它是另一种积而非笛卡尔积，涉及条件概率。
标签：双射,法则,映射,组合,笔记,计数,cdots,集合,定义 From： https://www.cnblogs.com/jucason-xu/p/17130269.html