数组合数学

系数均为1的线性不定方程解的个数：母函数与容斥原理

字数统计: 2.7k字   |   阅读时长: 12分
, ,

摘要: 母函数+容斥原理

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

设 $a_{1}, a_{2}, \cdots, a_{n}$ 为非零整数，$b$ 为整数，关于未知数 $x_{1}, x_{2}, \cdots, x_{n}$ 的以下方程，称为一次不定方程，也称为线性不定方程：

线性不定方程的正整数解的性质是初等数论的重要问题。如果所有系数 $a_{i}$ 均为 1，那么就是一种简单情况。本文我们研究这种系数均为 1 的线性不定方程的非负整数解的个数问题。

首先讨论 $x_{i}$ 没有上下界限制的情况，我们分别通过隔板法和母函数法给出解的个数；对于未知变量有上下界限制 $l_{i} \leq x_{i} \leq r_{i}$ 的情况，需要做一些变量代换以及容斥原理相关的工作。最终我们解决 2929. 给小朋友们分糖果 II。

变量无约束

求以下不定方程的非负整数解的个数。

隔板法

将 $n$ 个不区分的星号排成一行，我们需要在这 $n$ 个星号之间防止 $k - 1$ 个隔板，将星号分为 $k$ 组，每组代表一个 $x_{i}$ 的值，且 $\sum\limits_{i=0}\limits^{k}x_{i} = n$

例如，$n=7$，$k=3$，则一种可能的放置隔板的方法如下：

1
*****|*|*

这种放置方法对应了 $x_{1} = 5, x_{2} = 1, x_{3} = 1$ 这一组解。

$n$ 个星号和 $k-1$ 个隔板都视为占一个槽位，问题可以转化为：一排 $n + k - 1$ 个槽位，$k-1$ 个放隔板，$n$ 个放星号，有多少种放法，这样就可以轻易得出答案 $\binom{n + k - 1}{k - 1}$。

组合构造法 (欧拉)

有 $k$ 个不同物体，每一个都可以重复选取任意多次，选取一个基数为 $n$ 的多重集有多少种方法。

设想 $k$ 个物体与自然数 $1, 2, \cdots, k$ 一一对应，于是所考虑的组合可以视为一个含 $n$ 个数的多重集 $\{c_{1}, c_{2}, \cdots, c_{n}\}$。由于与次序无关，不妨设 $c_{1} \leq c_{2} \leq c_{n}$。

另构造一组数 $\{d_{1}, d_{2}, \cdots, d_{n}\}$ 与 $\{c_{1}, c_{2}, \cdots, c_{n}\}$ 对应，其中：

这样即使有的 $c_{i}$ 有重复，$d_{i}$ 也不会相同。

另一方面，任意一种 $\{d_{1}, d_{2}, \cdots, d_{n}\}$ 的取法都对应一种 $\{c_{1}, c_{2}, \cdots, c_{n}\}$ 的取法，反之亦然，因此这两个组合计数问题等价。

由于 $c_{i}$ 最大可取 $k$，所以 $d_{i}$ 最大可取 $k + n - 1$。因此从 $k$ 个不同物体中可以重复地任意多次地选取一个基数是 $n$ 的多重集的方法数，等于从 $k + n - 1$ 个不同元素中不重复地取 $n$ 个元素的方法数，即：

母函数法

记 $b_{k}(n)$ 表示不定方程 $x_{1} + x_{2} + \cdots + x_{k} = n$ 非负整数解的个数。$b(x)$ 为 $b_{k}(n)$ 的普通生成函数：

考察 $b(x)$ 的 $x^{n}$ 的系数，得到：

变量有范围

考虑以下方程：

这里 $x_{i}$ 有上下界的约束：$1 \leq x_{1} \leq 5$、$-2 \leq x_{2} \leq 4$、$0 \leq x_{3} \leq 5$、$3 \leq x_{4} \leq 9$。

求满足该范围的整数解的个数。

方法1：变量代换+容斥原理

下界的处理：变量代换

令：$y_{1} = x_{1} - 1$、$y_{2} = x_{2} + 2$、$y_{3} = x_{3}$、$y_{4} = x_{4} - 3$。方程转化为：

下界均变为了 0，若没有上界，那么就是常规的求非负整数解个数的问题。但这里还有上界需要处理。

上界的处理：容斥原理

令 $S$ 表示不定方程 $y_{1} + y_{2} + y_{3} + y_{4} = 16$ 所有非负整数解构成的集合。

记 $y_{i}$ 的上界为 $n_{i}$。这里 $n_{1} = 4$、$n_{2} = 6$、$n_{3} = 5$、$n_{4} = 6$。

定义性质 $P_{i}$：$y_{i} \geq n_{i} + 1$，$X_{i}$ 表示 $S$ 中满足性质 $P_{i}$ 的整数解构成的集合。

记 $b_{k}(n) = \binom{n + k - 1}{n}$ 表示 $y_{1} + y_{2} + \cdots + y_{k} = n$ 的非负整数解个数。于是：

有一个变量大于上界的解：

有两个变量大于上界的解：

有三个变量大于上界的解：

由于 $5 + 6 + 7 = 18 > 16$，因此任意三个 $X_{i}$ 相交都是空集。

综上，由容斥原理，$y_{1} + y_{2} + y_{3} + y_{4} = 16$ 的非负整数解的个数为：

方法2：母函数

变量代换后不带负幂次项

考虑变量代换后的方程 $y_{1} + y_{2} + y_{3} + y_{4} = 16$，记 $y_{i}$ 的上界为 $n_{i}$。这里 $n_{1} = 4$、$n_{2} = 6$、$n_{3} = 5$、$n_{4} = 6$。

由取值范围，直接普通生成函数为 $f(y) = (\sum\limits_{i=0}\limits^{4}y^{i})(\sum\limits_{i=0}\limits^{6}y^{i})(\sum\limits_{i=0}\limits^{5}y^{i})(\sum\limits_{i=0}\limits^{6}y^{i})$，取其 $y^{16}$ 的系数即可。

用 Python 的 Sympy 库来进行符号计算。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import sympy as sp

y = sp.symbols('y')

def f(y):
    ans = 1 + y + y**2 + y**3 + y**4
    ans *= 1 + y + y**2 + y**3 + y**4 + y**5 + y**6
    ans *= 1 + y + y**2 + y**3 + y**4 + y**5
    ans *= 1 + y + y**2 + y**3 + y**4 + y**5 + y**6
    return ans

fy = f(y)

expansion = fy.series(y, 0, 17)

此时 expansion 中的内容为带大 O 余项的泰勒展开，如下：

1
1 + 4*y + 10*y**2 + 20*y**3 + 35*y**4 + 55*y**5 + 79*y**6 + 104*y**7 + 127*y**8 + 145*y**9 + 155*y**10 + 155*y**11 + 145*y**12 + 127*y**13 + 104*y**14 + 79*y**15 + 55*y**16 + O(y**17)

我们要求的是第 16 项系数：

1
2
n = 16
n_coefficient = expansion.coeff(y, n)

结果为 55。

带着负幂次项，省去变量代换

用普通生成函数的话，还可以不进行变量代换，直接在生成函数中带着负幂次项走。考虑原方程：

这里 $x_{i}$ 有上下界的约束：$1 \leq x_{1} \leq 5$、$-2 \leq x_{2} \leq 4$、$0 \leq x_{3} \leq 5$、$3 \leq x_{4} \leq 9$。

由取值范围，直接写出普通生成函数 $g(x) = (\sum\limits_{i=1}\limits^{5}x^{i})(\sum\limits_{i=-2}\limits^{4}x^{i})(\sum\limits_{i=0}\limits^{5}x^{i})(\sum\limits_{i=3}\limits^{9}x^{i})$。

这样取其展开后的 $x^{18}$ 项系数即可，Sympy 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import sympy as sp

x = sp.symbols('x')

def g(x):
    ans = x + x**2 + x**3 + x**4 + x**5
    ans *= x**(-2) + x**(-1) + 1 + x + x**2 + x**3 + x**4
    ans *= 1 + x + x**2 + x**3 + x**4 + x**5
    ans *= x**3 + x**4 + x**5 + x**6 + x**7 + x**8 + x**9
    return ans

gx = g(x)
expansion = gx.series(x, 0, 19)

n = 18
n_coefficient = expansion.coeff(x, n)

答案仍然为 55。

2929. 给小朋友们分糖果 II

给你两个正整数 n 和 limit 。

请你将 n 颗糖果分给 3 位小朋友，确保没有任何小朋友得到超过 limit 颗糖果，请你返回满足此条件下的 总方案数 。

提示：

1
2
1 <= n <= 1e8
1 <= limit <= 1e8

示例 1：
输入：n = 5, limit = 2
输出：3
解释：总共有 3 种方法分配 5 颗糖果，且每位小朋友的糖果数不超过 2 ：(1, 2, 2) ，(2, 1, 2) 和 (2, 2, 1) 。

示例 2：
输入：n = 3, limit = 3
输出：10
解释：总共有 10 种方法分配 3 颗糖果，且每位小朋友的糖果数不超过 3 ：(0, 0, 3) ，(0, 1, 2) ，(0, 2, 1) ，(0, 3, 0) ，(1, 0, 2) ，(1, 1, 1) ，(1, 2, 0) ，(2, 0, 1) ，(2, 1, 0) 和 (3, 0, 0) 。

算法：容斥原理

考虑不定方程 $x_{1} + x_{2} + x_{3} = n$，其中 $x_{1}, x_{2}, x_{3}$ 的范围均为 $[0, l]$。

令 $S$ 表示不定方程 $x_{1} + x_{2} + x_{3} = n$ 所有非负整数解构成的集合。

定义性质 $P_{i}$：$x_{i} \geq l + 1$，$X_{i}$ 表示 $S$ 中满足性质 $P_{i}$ 的整数解构成的集合。

记 $b_{k}(n) = \binom{n+k-1}{k-1}$ 为 $x_{1} + x_{2} + \cdots + x_{k} = n$ 的非负整数解个数。

变量无任何限制的情况：

有一个变量大于上界的情况（需要 $n - (l + 1) \geq 0$）：

有两个变量大于上界的情况（需要 $n - 2(l + 1) \geq 0$）：

三个变量均大于上界的情况（需要 $n - 3(l + 1) \geq 0$）：

综上，由容斥原理，$x_{1} + x_{2} + x_{3} = n$ 的非负整数解的个数为：

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import math

def b(k, n):
    return math.comb(n + k - 1, k - 1)

class Solution:
    def distributeCandies(self, n: int, l: int) -> int:
        ans = b(3, n)
        if n - (l + 1) >= 0:
            ans -= b(3, n - (l + 1)) * 3
        if n - (l + 1) * 2 >= 0:
            ans += b(3, n - (l + 1) * 2) * 3
        if n - (l + 1) * 3 >= 0:
            ans -= b(3, n - (l + 1) * 3) 
        return ans
Share