利用容斥原理求解方程 x1+x2+x3+x4=17 的整数解个数

首先不考虑限制条件，根据组合数学的知识，方程$x_{1}+x_{2}+x_{3}+x_{4}=17$的非负整数解的个数为$/binom{17+4-1}{4-1}=/binom{20}{3}=1140$。/n/n然后考虑限制条件。设$A_{i}$表示$x_{i}>3$的情况，$B_{i}$表示$x_{i}>4$的情况，$C_{i}$表示$x_{i}>5$的情况，$D_{i}$表示$x_{i}>8$的情况。根据容斥原理，我们要求的就是满足条件$x_{1}/leq 3,x_{2}/leq 4,x_{3}/leq 5,x_{4}/leq 8$的非负整数解的个数，即$S=/overline{A_{1}A_{2}A_{3}A_{4}}/cap/overline{B_{1}B_{2}B_{3}B_{4}}/cap/overline{C_{1}C_{2}C_{3}C_{4}}/cap/overline{D_{1}D_{2}D_{3}D_{4}}$。/n/n根据容斥原理，$S$的大小可以表示为：/n/n$$//begin{aligned}//|S|&=|U|-/sum_{i=1}^{4}|A_{i}|+/sum_{i<j}|A_{i}A_{j}|-/sum_{i<j<k}|A_{i}A_{j}A_{k}|+|A_{1}A_{2}A_{3}A_{4}|////&-/sum_{i=1}^{4}|B_{i}|+/sum_{i<j}|B_{i}B_{j}|-/sum_{i<j<k}|B_{i}B_{j}B_{k}|+|B_{1}B_{2}B_{3}B_{4}|////&-/sum_{i=1}^{4}|C_{i}|+/sum_{i<j}|C_{i}C_{j}|-/sum_{i<j<k}|C_{i}C_{j}C_{k}|+|C_{1}C_{2}C_{3}C_{4}|////&-/sum_{i=1}^{4}|D_{i}|+/sum_{i<j}|D_{i}D_{j}|-/sum_{i<j<k}|D_{i}D_{j}D_{k}|+|D_{1}D_{2}D_{3}D_{4}|////end{aligned}//$$ /n/n其中$U$表示所有非负整数解的集合。我们已经知道$|U|=1140$。/n/n对于$|A_{i}|$，要求$x_{i}>3$，相当于将$x_{i}$减去$4$，然后将剩下的$17-4/times 4=1$分配给$x_{1},x_{2},x_{3},x_{4}$，得到$/binom{1+4-1}{4-1}=/binom{4}{3}=4$种分配方案，因此$|A_{i}|=4$。同理，$|B_{i}|=/binom{5}{3}=10$，$|C_{i}|=/binom{6}{3}=20$，$|D_{i}|=/binom{9}{3}=84$。/n/n对于$|A_{i}A_{j}|$，要求$x_{i}>3$且$x_{j}>3$，相当于将$x_{i}$和$x_{j}$分别减去$4$，然后将剩下的$17-2/times 4=9$分配给$x_{1},x_{2},x_{3},x_{4}$，得到$/binom{9+4-1}{4-1}=/binom{12}{3}=220$种分配方案，因此$|A_{i}A_{j}|=220$。同理，$|B_{i}B_{j}|=/binom{6}{3}=20$，$|C_{i}C_{j}|=/binom{7}{3}=35$，$|D_{i}D_{j}|=/binom{10}{3}=120$。/n/n对于$|A_{i}A_{j}A_{k}|$，要求$x_{i}>3$且$x_{j}>3$且$x_{k}>3$，相当于将$x_{i}$、$x_{j}$和$x_{k}$分别减去$4$，然后将剩下的$17-3/times 4=5$分配给$x_{1},x_{2},x_{3},x_{4}$，得到$/binom{5+4-1}{4-1}=/binom{8}{3}=56$种分配方案，因此$|A_{i}A_{j}A_{k}|=56$。同理，$|B_{i}B_{j}B_{k}|=0$，$|C_{i}C_{j}C_{k}|=/binom{8}{3}=56$，$|D_{i}D_{j}D_{k}|=0$。/n/n最后，$|A_{1}A_{2}A_{3}A_{4}|=0$，因为$x_{1}/leq 3$且$x_{2}/leq 4$且$x_{3}/leq 5$且$x_{4}/leq 8$不可能同时成立。/n/n将以上结果代入$|S|$的式子中，得到：/n/n$$//begin{aligned}//|S|&=1140-4/times 4+6/times 220-4/times 56-10/times 20+3/times 35+20/times 56-4/times 84////&=1140-16+1320-224-200+105+1120-336////&=2789////end{aligned}//$$ /n/n因此，方程$x_{1}+x_{2}+x_{3}+x_{4}=17$的整数解的个数为$2789$。