基于容斥原理解决的有限制不定方程非负整数解（多重集组合数）计数问题

此类问题通常被表示为：

给出$n$元一次不定方程${\sum }_{i=1}^n{x}_i=m$与$n$个限制条件$x_i\le b_i$，其中$m,b_i\in \mathbb{N}$。求该不定方程的非负整数解的个数。

解决此问题的通常思路是：将有限制的不定方程非负整数解计数转化为无限制的不定方程非负整数解计数。

无限制的不定方程非负整数解计数

先考虑如下问题：给出$n$元一次不定方程${\sum }_{i=1}^n{x}_i=m$，其中$m\in \mathbb{N}$。求方程的非负整数解的个数。

在无限制的情况下，该方程非负整数解的个数为$C_{m+n-1}^{n-1}$。

证明：隔板法：假设有$n+m-1$个位置，选出其中$n-1$个位置作为隔板，其余$m$个位置作为数字$1$，这$n-1$个将$m$个$1$分成了$n$段，每一段$1$的个数即为两个隔板间代表的数。故$C_{m+n-1}^{n-1}$即为答案。

如何转化

有一个关于集合交并补差运算的公式：
​ $$|\bigcap _{i=1}^n{S}_i|=|U|-|\bigcup _{i=1}^n{\complement }_U{S}_i|$$
所以，令$U$为无限制下满足原方程的全体非负整数解的集合，$S_i$为满足约束条件$x_i\le b_i$的解的集合，此时$|{\bigcap }_{i=1}^n{S}_i|$显然即为同时满足所有约束条件、即合法解的集合的元素个数。根据这个公式，我们只需要考虑不满足$x_i\le b_i$的解的集合（即${\complement }_U{S}_i$），此时$|U|=C_{m+n-1}^{n-1},|{\bigcup }_{i=1}^n{\complement }_U{S}_i|$显然可以直接运用容斥公式求出来。这样一来，我们就将有限制的不定方程非负整数解计数转化为无限制的不定方程非负整数解计数。

如何计算$|{\bigcup }_{i=1}^n{\complement }_U{S}_i|$

根据容斥公式${\bigcup }_{i=1}^n{S}_i={\sum }_{k=1}^n(-1{)}^{k-1}{\sum }_{a_i<a_{i+1}}^{|a|=k}|{\bigcap }_{i=1}^k{S}_{a_i}|$，我们只需要考虑如何计算${\sum }_{a_i<a_{i+1}}^{|a|=k}|{\bigcap }_{i=1}^k{\complement }_U{S}_{a_i}|$即可。
$|{\bigcap }_{i=1}^k{\complement }_U{S}_{a_i}|$意为满足所有$k$个限制条件$x_i\ge b_i+1(i\in a)$（即不满足$x_i\le b_i$）解的个数，那么，为了保证$x_i\ge b_i+1(i\in a)$对$\forall i$成立，我们将原方程转化为：
​ $$\sum _{i=1}^n{x}_i=m-\sum _{i=1}^k(b_{a_i}+1)$$
此时，由于已保证每一个$x_i$恰好不会被满足（取值至少为$b_i+1$），故此时只需令所有$x$（包括$x_{a_i}$）任意取非负值累加得到$m-{\sum }_{i=1}^k(b_{a_i}+1)$，即可得到原方程不满足此$k$个约束条件的解。而这个问题的解便是无约束不定方程$$\sum _{i=1}^n{x}_i=m-\sum _{i=1}^k(b_{a_i}+1)$$的解的个数，等于$C_{m+n-1}^{n-1}$。

因此，原有约束的不定方程的解的个数即为：
​ $$C_{m+n-1}^{n-1}+\sum _{k=1}^n(-1{)}^k\sum _{a_i<a_{i+1}}^{|a|=k}{C}_{m-{\sum }_{i=1}^k(b_{a_i}+1)+n-1}^{n-1}$$

最后注意：在原不定方程被变换形式后此通式可能不适用，但依然可以考虑将有约束问题转化为无约束问题。

最后

以上就是天真台灯最近收集整理的关于基于容斥原理解决的有限制不定方程非负整数解（多重集组合数）计数问题的全部内容，更多相关基于容斥原理解决内容请搜索靠谱客的其他文章。