不定方程非负整数解个数

问题

先从一个问题引入：假如一个湖里有4种鱼，而我总共钓上来了10条鱼，请问鱼的组合共有多少种可能？（注意这个问题里某种鱼的条数可以为0）

更一般地，我们可以假设有$r$种鱼，且一共钓到了$n$条，那可能的结果数就是满足：

$$x_1+x_2+\cdots +x_r=n$$
的非负整数向量 $(x_1,x_2,\cdots,x_r)$的个数。生活中经常会碰到类似的问题，所以就称呼为“不定方程非负整数解个数”问题。

解法

要计算非负整数向量的个数，我们可以先考虑正整数向量$(x_1,x_2,\cdots,x_r)$的个数。我们假设有n个连续的数值1排成一行：

$$1\;1\;1\;\cdots\;1\;1$$
注意，总共有n-1个间隔，我们需要将r-1个加号放到这些间隔中。例如，如果 $n=8,r=3$，那么选择
$$1+1\;1\;1\;1+1\;1\;1$$
对应解 $x_1=1,x_2=4,x_3=3$。

结论1

共有$C_{n-1}^{r-1}$个不同的正整数向量$(x_1,x_2,\cdots,x_r)$满足

$$x_1+x_2+\cdots +x_r=n\ x_i>0,i=1,\cdots,r$$

为了得到非负整数解（而不是正整数解）的个数，注意，$x_1+x_2+\cdots +x_r=n$的非负整数解个数与$y_1+y_2+\cdots +y_r=n+r$的正整数解个数是相同的（令$y_i=x_i+1,i=1,\cdots,r$）。因此得到结论2

结论2

共有$C_{n+r-1}^{r-1}$个不同的非负整数向量$(x_1,x_2,\cdots,x_r)$满足

$$x_1+x_2+\cdots +x_r=n$$

所以回到最开始的问题，总共有$C_{10+4-1}^{3}=C_{13}^{3}=286$中可能的情况