容斥原理解方程整数解个数:x1+x2+x3+x4=17,xi非负整数且有上限
首先考虑不考虑限制条件,即求非负整数解的个数。这是一个经典问题,可以用插板法得到答案为$C^{17+4}_{4}$。
然后考虑限制条件。先单独考虑$x_1≤3$的限制条件,设$A$为满足$x_1≤3$的整数解个数,则有$A=C^{14+4}_{4}$,即先把$x_1$设为$0,1,2,3$中的一种,然后把剩下的$17-x_1$个球放入$4$个盒子中。
同理,可以求出$x_2≤4$、$x_3≤5$、$x_4≤8$的限制条件下整数解的个数分别为$B$、$C$、$D$。
然后考虑两个限制条件的交,比如$x_1≤3$和$x_2≤4$的交。设$E$为满足$x_1≤3$且$x_2≤4$的整数解个数,则有$E=C^{13+4}_{4}$,即先将$x_1$设为$0,1,2,3$中的一种,$x_2$设为$0,1,2,3,4$中的一种,然后把剩下的$17-x_1-x_2$个球放入$4$个盒子中。
同理,可以求出其他限制条件的交的整数解个数。
最后考虑所有限制条件的交,即$x_1≤3$、$x_2≤4$、$x_3≤5$、$x_4≤8$的交。设$F$为满足所有限制条件的整数解个数,则有$F=C^{9+4}_{4}$,即先把$x_1,x_2,x_3,x_4$分别设为$0,1,2,3$、$0,1,2,3,4$、$0,1,2,3,4,5$、$0,1,2,3,4,5,6,7,8$中的一种,然后检验是否符合限制条件。
根据容斥原理,所求的整数解个数为$A+B+C+D-(E+F)$。代入上述计算结果即可。
原文地址: https://www.cveoy.top/t/topic/oci1 著作权归作者所有。请勿转载和采集!