Question

求不定方程x1+x2+x3=14的数值不超过6的正整数解的个数。利用生成函数算。

Answer 1

问：求不定方程x1+x2+x3=14的数值不超过6的正整数解的个数。利用生成函数算。

问：OK

答：您好，考虑将每个变量表示为一个数不超过6的整数加一，即$x_i=y_i+1$，则原方程变为$y_1+y_2+y_3=11$，其中$y_i$取值范围为$0$到$5$。因此我们可以定义生成函数：$$f(x)=(1+x+x^2+x^3+x^4+x^5)^3$$其中$x^k$的系数就是和为$k$的$y_1,y_2,y_3$的方案数。我们只需要求出$x^{11}$的系数即可，即：$$[x^{11}]f(x)=[x^{11}](1+x+x^2+x^3+x^4+x^5)^3$$利用二项式定理展开，得到：$$[x^{11}]f(x)=[x^{11}]\sum_{i=0}^5x^i\sum_{j=0}^5x^j\sum_{k=0}^5x^k$$$$=[x^{11}]\sum_{i=0}^5\sum_{j=0}^5\sum_{k=0}^5x^{i+j+k}$$当$i+j+k=11$时，$x^{i+j+k}=x^{11}$，因此系数为$1$，所以我们只需要计算$i+j+k=11$的方案数即可。这可以通过插板法得到，即将$11$个球插入$3$个盒子中，每个盒子至少一个球。这样的方案数为$\binom{10}{2}=45$。因此$x^{11}$的系数就是$45$，所以原方程的解的个数为$45$。