数论小结 - 程序员

第一次写数学专题的笔记有点小激动欸~跪求LeTax不要炸我的废话可能有点多 \bx 求原谅 \bx

数论真的我搁了好久没碰，因为长官这真的太抽象了！于是搁到了现在终于鼓起勇气写了一篇学习笔记以此加深印象。（不然我肯定一秒钟后又要全部忘完）

part1 容斥

公式推导

首先我们的目标是推出以下这个看着就很狗屎的式子：

\[\left| \bigcup_{i=1}^{n} A_i \right| = \sum_{\varnothing \neq J \subseteq \{1,2,\dots,n\}} (-1)^{|J|+1} \left| \bigcap_{j \in J} A_j \right|\]

考虑从特殊到一般，我们先来列一个简单的式子\(|A_1 \cup A_2|\) 易得出化简结果为 \(|A_1|+|A_2|-|A_1 \cap A_2|\) 简单解释一下，就是 \(|A_1|\) 和 \(|A_2|\) 的交集加多了所以要减去。

\[|A_1 \cup A_2 \cup A_3| = |A_1| + |A_2| + |A_3| - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_2 \cap A_3| + |A_1 \cap A_2 \cap A_3| \]

用\(\Sigma\)化简一下就变成了：

\[|A_1 \cup A_2 \cup A_3| = \sum_{i} |A_i| - \sum_{i

这是是什么意思，我根本看不懂啊？那如果我这么写呢：

\[|A_1 \cup A_2 \cup A_3| = 所有集合交集 - 两两相交 + 三三相交 \]

怎么样是不是有那画面啦~

然后类比只有两个集合的时候，感觉这好像都是先把全部的加上，加多了再减，减多了再加。对吧？那我们稍微试着再扩展一下，写到四项呢？再写道五项呢？请自己在草稿纸上写一下再接着往下看。

观察到什么规律了吗？就是啊我们每次都是先加上所有集合的交集再减去所有集合两两之间的交集，再加上三个集合之间的交集，再减去四个集合之间的交集......如此循环往复

那我们是不是就能整理出如面的式子：

\[\left| \bigcup_{i=1}^{n} A_i \right| = \sum_{i} |A_i| - \sum_{i

注意是 \(-1^{n+1}\)，观察一下上面的公式就知道为什么了。最后化简一下，即可得到我们最开始列出来的式子啦。

应用

本蒟蒻刚学完容斥公式后就想着：这个式子有了，但是有什么用呢？抱着和本蒟蒻同样想法的同学先别着急下面就是公式的应用部分，也就是容斥真正的重头戏~

先上一个引题（夫妻不相邻问题）：

有 \(n\) 对夫妻，站成一排，要求夫妻不相邻，有多少种方案？

我也不知道这是谁出的题，明显棒打鸳鸯来的（bs）

注意到其实只求一对不相邻是好求的。但是 \(n\) 对？试试我们刚刚学的容斥公式吧~

考虑引入一个集合 \(U\) 集合这 \(n\) 对夫妻站一起的全排列。那全排列减去不合法的排列，不就是答案吗？那就再引入一个 \(A_i\) 表示第 \(i\) 对夫妻站在一起的排列。那我们就很简单地弄出来了一个式子：

\[ans=|U|-\left| \bigcup_{i=1}^{n} A_i \right| \]

拆一下发现 \(|U|=(2n)!\) （全排列嘛，就是阶乘级别的）注意 \(n\) 对夫妻是 \(2\times n\) 个人，然后后面的式子就是我们刚刚学的容斥公式啊~

化简一下式子

\[ans = (2n)! - \sum_{i} |A_i| + \sum_{i

可是我们发现了一个问题，到底应该怎么求\(|A_i|\)，\(|A_i \cup A_j|\) ... 呢？考虑引入组合数的意义。 \(n\) 对人，有一对不相邻，那我们先排前 \(n-1\) 对方案数就是 \((2\times n-1)!\) 种（至于为什么不是\(2\times n-2\)，因为你还要考虑第 \(i\) 对夫妻的位置嘛）。再拍后面两人（因为人是有差别的）方案数就是 \(2!\) 种。合并一下就可以得到：

\[|A_i|=(2n-1)! \cdot 2! \]

那 \(|A_i \cap A_j|\) 是多少呢？那我们就先排前 \(n-2\) 对和两人。然后考虑组内的顺序，合并一下就成了：

\[|A_i\cap A_j|=(2n -2)! \cdot (2!)^2 \]

有没有发现什么规律呢~什么你说你没有发现，那我们同理，再列一下三个的公式：

\[|A_i \cap A_j \cap A_k|=(2n -3)!\cdot(2!)^3 \]

那这个规律就很明显了呀，每多一项 \(2n\) 就会多减一，而 \(2!\) 的指数也会多加一。什么你说你还是没看出来！？那我们考虑组合意义：我们考虑把当前必须相邻的夫妻全部捆起来，捆成一个人。那我们就有 \(2n-k\) 个人需要排队，那组数就是 \((2n-k)!\) 个。但是夫妻两人必然是有差异的，所有我们需要再乘上 \(k\) 个 \(2!\)。

当我们愉快的准备将求出来的式子带入到公式中求解的时候，但是我们又发现了一个问题：那诸如 \(\sum_{i （也就是式子外面带了个\(\Sigma\)）这种该怎么求呢？其实也是很简单的。因为每项的贡献都是一样的，那我们考虑从 \(n\) 个里面取 \(k\) 个有多少种取法，即为每项的系数。比如首先化简一下最简单的一对夫妻必须相邻的公式即为：\(n\times(2n-1)!\times 2\) 。稍微扩展一下，如果是两对呢？直接 \(\mathrm{C}_n^2\) 再带上之前推导的公式嘛。那 \(k\) 对夫妻？类比一下，不就是 \(\mathrm{C}_n^k(2n-k)!2^k\) 吗？

那我们就可以愉快地带入了，最终答案即为：

\[ans=(2n)!+\sum_{k=1}^{n}(-1)^k \cdot \mathrm{C}_n^k(2n-k)! \cdot 2^k \]

到这里这东西终于是推完了！其实好像也不难嘛（确信）总结一下这道题我们用了什么方法：

首先发现直接求不相邻，貌似是不好求的。正难则反，考虑全排列减去不合法的排列。
首先求出一个不合法排列的大小，再求出每个交集大小。
找出规律后再求出前面的系数。
【通项公式】得到了！

怎么样这东西是不是还挺套路的？就是题目让我干个事，我觉得难了，我反着干。是这道理吧？

好题推荐

前面我讲得有点啰嗦，下面是几道练手题可以自己写写完再看答案（我不会咋讲了）。

有n种颜色的小球，每种有且仅有2个，排成一排，同色小球不相邻，有几种排法？

答案

\[\text{ans}=\sum_{k=0}^{n}(-1)^k\mathrm{C}_n^k(2n-k)! \]
n 个人各写一张贺卡，打乱后每人拿一张，问没人拿到自己的贺卡的方案数。

提示1

考虑设计\(A_i\) 表示第 \(i\) 个人拿到了自己的贺卡的排列集合

答案

\[D_n=\sum_{k=0}^{n}(-1)^k C_n^k (n-k)! \]
n 个不同小球放入 m 个不同盒子，要求至少有一个空盒的方案数。

答案

\[m^n-\sum_{k=0}^{m}(-1)^k C_m^k (m-k)^n \]

part2 第二类斯特林数

引入

为啥不讲第一类斯特林数，因为第二类嘛更适用于竞赛宝宝体制。我绝对不会告诉你其实是因为我也不会啊（快点划掉！）。

那到底啥是第二类斯特林数嘞？引入个题， \(n\) 个不同的球，放入 \(m\) 个相同的盒子里，每个盒子至少一个，求方案总数。

哇这竟然有两个未知数欸！那我们干脆整一个函数 \(\begin{Bmatrix} n \\ k \end{Bmatrix}\) 来表示这类问题的答案吧~

方法1 容斥

欸，这东西是不是如果没有这个非空和盒子相同的限制是好算的？直接口算即可得出答案是 \(m^n\) ，简单解释一下你有 \(m\) 个不相同的盒子，每个盒子可以有 1 到 n 个球而且没有非空的限制。

那考虑到这个性质，尝试一下容斥？引入一个函数\(S(n,m)\)表示盒子不同时的答案。设 \(A_i\) 表示第 \(i\) 个为空的集合。代入公式算一算，就可以得到通项公式了~（相信大家都对容斥很熟练了吧？我就不讲了）

直接给个过程吧：

\[S(n,m) = m^n - \left| \bigcup_{i=1}^{m} A_i \right| \]

由容斥化简：

\[S(n,m) = m^n - \sum_{k=1}^{m} (-1)^{k+1} C_m^k (m-k)^n \]

把 \(m^n\) 并入\(\Sigma\)里：

\[S(n,m) = \sum_{k=0}^{m} (-1)^k C_m^k (m-k)^n \]

盒子不同的话，咋整啊？因为每个盒子非空的放法，会在盒子不同时被重复计算 \(m\) 的全排列次，也就是 \(m!\) 。那我们就可以推出来：

\[\begin{Bmatrix} n \\ k \end{Bmatrix} = \frac{S(n,m)}{m!} \]

带入一下？

\[\begin{Bmatrix} n \\ k \end{Bmatrix} = \sum_{k=0}^{m} (-1)^k C_m^k (m-k)^n \times \frac{1}{m!} \]

第二类斯特林数的通项就有了，哦耶！

方法2 递推

貌似斯特林数可以依赖前一个转换过来吧？试试看？首先考虑 \(\begin{Bmatrix} n \\ 1 \end{Bmatrix}=1\) 也就是全部都放到一个盒子里面，显然只有一种放法嘛。

接着大力推递推式，考虑第 \(n\) 个球怎么放。第一种情况，考虑第 \(n\) 个球单独放在一个盒子里面，因为盒子相同，所以方案数即为：

\[\begin{Bmatrix} n-1 \\ m-1 \end{Bmatrix} \]

第二种情况考虑第 \(n\) 个球和别的球共用一个盒子。因为非空，所以我们先把前 \(n\) 个球放到 \(m\) 个盒子里面。而因为第 \(n\) 可以放到 \(m\) 个球里的任意一个，一共有 \(m\) 个选择。（虽然盒子一样，但是盒子里球的个数不一样即为 \(m\) 个选择）方案数即为：

\[m\begin{Bmatrix} n-1 \\ m \end{Bmatrix} \]

因为这两种情况并不互相依赖，第 \(n\) 个球要么单独一个盒子要么和别的球共用一个盒子，所以应该是加上。最后合并一下变成了：

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

第二类斯特林数的递推式也有了，哦耶！

part3：母函数

引入

母函数是啥嘞？母函数就是用一个多项式来装一个数列。把数列的每一项当作 \(a_n\) 当作 \(x_n\) 的系数。这样数列的问题就变成了多项式/级数的运算问题。比如一个数列 \(a_0,a_1,a_3,\cdots\)，其母函数就是 \(G(x)=a_0+a_1x+a_2x^2+a_3x^3+\cdots\)。

再举一个简单的例子：\(1,2,3,4,\cdots\) ，其母函数即为 \(G(x)=1+x+x^2+x^3+\cdots\)。

具体地来说对于普通的母函数：

\[G(x)=\sum_{n=0}^{\infty} a_n x^n \]

当然我们也需要接受一个写法：

\[G(x)[b] \]

啥意思嘞？就是当母函数是 \(G(x)\) 的时候 \(b\) 的系数。举个例子：二项式定理都知道吧？比如 \((x+y)^n\) 展开后 \(x^iy^{n-i}\) 系数是多少呢？很简单嘛就是 \(C_n^i\)。写成上面的形式之后即为：

\[C_n^i=(x+y)^n[x^iy^{n-i}] \]

最好在这里接受一下这个写法，后面比较常用。

应用

那这个东西有啥用呢？本蒟蒻在这里引入一个各位大佬想必都听过的组合恒等式——朱世杰恒等式。

\[C_k^k+C_{k+1}^k+\cdots+C_{k+r}^k=C_{k+r+1}^{k+1} \]

那学了这个母函数，我们一起来试着证明这东西吧~

首先我们先写一个组合数的母函数，很好理解二项式定理把 \(y\) 换成1就好了：

\[C_{k+i}^k=(1+x)^{k+i}[x^k] \]

注意到左边的式子里一定有 \(x^k\) 这一个因数就可以把它改写成如下的母函数：

\[((1+x)^k+(1+x)^{k+1}+\cdots + (1+x)^{k+r})[x^k] \]

考虑等比数列求和公式继续化简：

\[(\frac{(x+1)^{k+r+1}-(x+1)^k}{(x+1)-1})[x^k] \]

把分母的 \(x\) 乘到后面的 \(x^k\) 里：

\[((x+1)^{k+r+1}-(x+1)^k)[x^{k+1}] \]

合并一下指数可得：

\[(x+1)^{k+r+1}[x^{k+1}] \]

哇，发现这个东西貌似好像等于\(C_{k+r+1}^{k+1}\)，对吧根据二项式定理。

那我们好像就证完了欸~

码字不易，无耻求赞