从不定方程的非负整数解个数谈起 |
您所在的位置：网站首页 › 隔板法非空公式 › 从不定方程的非负整数解个数谈起 |
|
序
求将 \(n\) 个无标号元素用 \(m-1\) 个隔板分入 \(m\) 个有标号可空集合的方案数。 或 求不定方程 \[x_1 + x_2 + \dots + x_m = n \quad (m,n \in N_+, m \le n) \]的非负整数解的个数。 是一个非常经典的组合问题，众所周知其答案为组合数 \({n+m-1 \choose m-1}\) ，这可以根据其组合意义结合隔板法容易的得到。 然而，笔者发现还有很多有趣的方法可以得到上式，值得探讨一番。 组合意义如上文所说，组合意义可以结合隔板法容易的得到。考虑将 \(n\) 个无标号元素用 \(m-1\) 个隔板分入 \(m\) 个有标号非空集合，其方案数为 \({n-1 \choose m-1}\) 。然而我们需要的是各集合可空情况下的方案数。考虑新增 \(m\) 个元素，先给每个集合放一个元素垫底，再做各组可空的分配。这个小Trick让我们将问题转化为求 \(n+m\) 个无标号元素分入 \(m\) 个非空有标号集合的方案数。再用隔板法，得到答案 \({n+m-1 \choose m-1}\) 。 形式化的，我们令 \(y_i = x_i + 1\) ，则我们现在只需求 \(y_1 + y_2 + \dots + y_m = n + m\) 的正整数解，隔板法得到答案 \({n+m-1 \choose m-1}\) 。 枚举空位——范德蒙德卷积公式我们使用另一种方法将隔板法应用到可空集合上。 枚举 \(m\) 个集合中有几个是空集，可以得到下式 \[\mathrm{ans} = \sum_{k=0}^{m-1} {m \choose k} {n-1 \choose m-k-1} \]又由范德蒙德卷积公式 \[{n+m \choose k} = \sum_{i=\max(0,k-m)}^{\min(n,k)} {n \choose i} {m \choose k-i} \]（范德蒙德卷积公式易由 \((1+x)^{n+m} = (1+x)^n (1+ x)^m\) 的二项式展开说明） 可直接得到（ \(k' = m-1\) ， \(n' = m\) ， \(m' = n-1\) ） \[\mathrm{ans} = \sum_{k=\max(0,(m-1)-(n-1))}^{\min(m,m-1)} {m \choose k} {n-1 \choose m-k-1} = {n+m-1 \choose m-1} \]递推——杨辉三角这固然很妙，但要是我想不到这些Trick怎么办？ 不会通项就设状态dp呗（反正是OIer有电脑帮我算 设状态 \(f(n,m)\) 表示将 \(n\) 个无标号元素放入 \(m\) 个有标号可空集合的方案数。 考虑当前正在为第 \(n\) 个元素确定所属集合。既然元素是无标号的，不妨按升序排列集合。于是放入新的元素时，只需决定要先跳过多少个集合再放入。易得下面的递推式 \[f(n,m) = \sum_{k=1}^m f(n-1,k) \]初始状态满足 \[\begin{aligned} &f(0,m)=1 \\ &f(n,0)=[n=0] \end{aligned} \quad (n,m \in N) \]（中括号是艾弗森括号） 不妨列出 \(f\) 的前几项—— n\m m0 m1 m2 m3 m4 n0 1 1 1 1 1 n1 0 1 2 3 4 n2 0 1 3 6 10 n3 0 1 4 10 20很熟悉...这是杨辉三角！ 可以由递推式得到杨辉三角的特征—— \[\begin{aligned} f(n,m) &= f(n-1, m) + \sum_{k=1}^{m-1} f(n-1,k) \\ &= f(n-1, m) + f(n, m-1) \end{aligned} \]那么，只需观察并将表格的每一项映射到杨辉三角，我们就能得到 \(f(n,m) = {n+m+1 \choose m-1}\) 。 生成函数——广义二项式定理要是我连杨辉三角都没看出来怎么办 方便起见，此处我们不研究 \(m=0\) 的情况。不妨设 \[g(n,m) = f(n,m+1) \]显然， \(g\) 的递推式为 \[g(n,m) = \sum_{k=0}^m g(n-1,k) \]据此我们发现，每一排是其前一排的前缀和数组，或者换句话说，每一排是其后一排的向前差分数组。我们先拿出 \(n=0\) 一排的OGF \[g_0(x) = \frac{1}{1-x} \]又根据差分 \[g_n(x) = g_{n+1}(x) - x g_{n+1}(x) \iff g_{n+1} = \frac{1}{1-x} g_n(x) \]得 \[g_n(x) = (1-x)^{-(n+1)} \]又由广义二项式定理 \[(x+y)^\alpha = \sum_{k=0}^{\infty} {\alpha \choose k} x^k y^{\alpha - k} \]其中 \[{\alpha \choose k} = \frac{\alpha(\alpha-1)\dots(\alpha-k+1)}{k!}\\ \]展开，得到 \[g_n(x) = \sum_{k=0}^{\infty} {-n-1 \choose k} (-1)^k x^k \]故 \[\begin{aligned} g_n(x)[x^k] &= (-1)^k {-n-1 \choose k} \\ &= (-1)^k \frac{(-n-1)(-n-2)\dots(-n-k)}{k!} \\ &= \frac{(n+1)(n+2)\dots(n+k)}{k!} \\ &= {n+k \choose k} \end{aligned} \]即 \[g(n,k) = {n+k \choose k} \]换回 \(f\) 表示就得到答案 \[f(n,m) = g(n,m-1) = {n+m-1 \choose m-1} \]Burnside——第一类斯特林数如果要分组的 \(n\) 个元素是有标号的，问题将会简单很多——直接枚举每个元素的所属集合即可，显然方案数为 \(m^n\) 。 但关键是它们没有标号。 无标号的本质是认为任意置换标号前后是同构的。这启发我们将所有 \(n\) 元置换（即置换群）作为变换集，使用等价类计数Burnside来解决该问题。 根据Burnside定理 \[\mathrm{ans} = \frac{1}{|G|} \sum_{f \in G} C(f) \]其中 \(G\) 是变换集， \(C(f)\) 是变换 \(f\) 的不动点。 可以写出 \[\mathrm{ans} = \frac{1}{n!} \sum_{p \in \mathrm{perm}(n)} m^{\mathrm{cyc}(p)} \]其中 \(\mathrm{perm}(n)\) 表示所有 \(n\) 元置换的集合，而 \(\mathrm{cyc}(p)\) 指置换 \(p\) 的形成的置换图中环的个数。 在外层枚举 \(\mathrm{cyc}(p)\) ，得 \[\mathrm{ans} = \frac{1}{n!} \sum_{k=1}^n m^k \sum_{p \in \mathrm{perm}(n)} [\mathrm{cyc}(p) = k] \]\(\sum_{p \in \mathrm{perm}(n)} [\mathrm{cyc}(p) = k]\) 是什么？ 第一类斯特林数 \({n \brack k}\) 表示将 \(n\) 个有标号元素分成 \(k\) 个无标号圆排列的方案数。 在置换图中， \(p_i\) 表示节点 \(i\) 的下一个节点是 \(p_i\) 。而枚举置换的过程，正是枚举置换图的过程，也正是枚举圆排列的过程！而 \([\mathrm{cyc}(p) = k]\) 则为我们确定了环，或者说圆排列的个数。 惊讶的，我们发现 \[{n \brack k} = \sum_{p \in \mathrm{perm}(n)} [\mathrm{cyc}(p) = k] \]带入其中，答案式变为 \[\mathrm{ans} = \frac{1}{n!} \sum_{k=1}^n {n \brack k} m^k \]于是，根据第一类斯特林数性质之一 \[\sum_{k=1}^n {n \brack k} m^k = m(m+1)\dots(n+m-1) \]（该性质可以结合第一类斯特林数的递推式做数学归纳得出） 我们愉快的得到了答案 \[\mathrm{ans} = \frac{m(m+1)\dots(n+m-1)}{n!} = {n+m-1 \choose m-1} \]用Burnside解决无标号问题的思路极具启发性，例如烷基计数问题的Burnside解法。 后记&致谢同分异构体计数带我重回OI 感谢TbYangZ菊苣全程提供技术支持。 感谢神仙化学老师提供组合意义解释。 2021/05/01 |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |