不定方程解的数量

​ (公式加载较慢，多刷新一下)

抛出问题：

$$求不定方程 x_1+x_2+x_3+......x_k=n的解的数量，且x_i\ge1，（1\le i\le k）$$

1、隔板法

​ 将$n$看成$n$个球，$k$个解表示最终拆成了$k$份

​ 那么问题等价于：用$k-1$个板将$n$个球隔开，$n$个球有$n-1$个缝隙，这$n-1$缝隙可以插入$k-1$个隔板，问：有多少种放法？

​ 显然，有$C_{n-1}^{k-1}$种放法

​ 此时，基本问题解决了

2、将$x_i\ge 1$改成$x_i\ge a_i$

​ 原问题变为：

​

$$\begin{cases} x_1+x_2+x_3+......x_k=n \\ x_1\ge a_1 \\ x_2\ge a_2 \\ .... \\ x_n\ge a_n \end{cases}$$

我们只需要将问题转化为原来的子问题：

​ 令$y_i=x_i-(a_i-1)$

​ 此时：$y_i\ge 1$

那么此时：

$$\begin{cases} y_1+y_2+y_3+.....y_k=x_1+x_2+..+x_k-(a_1+a_2+..+a_k)+k\\ y_i\ge 1 \end{cases}$$

化简一下：

$$\begin{cases} y_1+y_2+y_3+.....y_k=n-\sum_{i=1}^{k}a_i+k\\ y_i\ge 1 \end{cases}$$

所以此时这种情况的解的数量为：

$$C_{n-\sum_{i=1}^{k}a_i+k}^{k-1}$$

3、再变形！$x_1+x_2+x_3+……x_k\le n$的解的数量（其余条件不变，即$x_i\ge1，（1\le i\le k）$）

引入一个变量$z$

​ 使：$x_1+x_2+x_3+……x_k+z= n$,其中$z\ge 0$

3.1、$z=0$时

问题没有发生变化，此时的解法为：$C_{n-1}^{k-1}$

3.2、$z\ge 1$时

此时的$z$相当于$x_{k+1}$，相当于在原问题上加一个解，

此时的解法为：

$$C_{n-1}^{k}$$

所以最终的解的数量为：

$$C_{n-1}^{k-1}+C_{n-1}^{k}$$