|
本帖最后由 lihp2020 于 2021-7-17 21:53 编辑
陆老师的 的解释 就是容斥原理
这类问题的解法
前提知识
在每个对象的供给是无限的情况下,k个不同对象的r组合个数等于C(r+k-1,r)由于组合的性质也等于C(r+k-1,k-1)
(叫做多重集合的组合)
对于方程 就可以解释
x1+x2+...xk=r 有多少非负整数解C(r+k-1,r)
而原题是正整数 利用替代思想引入一些变量
y1=x1-1,y2=x2-1 y3 =x3-1 ……
就有
y1+y2+y3+y4+y5=10 (对于y就是0<=y<=4)
全集 |S| =C(10+5-1,5-1)(k=5,r=10)
一个不满足 就是 y1+y2+y3+y4+y5=10 其中一个yi>4
令其中一个ui=yi-5 其他 ui=yi
u1+u2+u3+u4+u5=10-5 =6非负整数解 C(6+5-1,5-1)
ui中的i 就是任意5个选1个就是C(5,1)
-----------
两个不满足 就是 y1+y2+y3+y4+y5=10 其中两个个yi>4
令其中两个ui=yi-5 其他 ui=yi
u1+u2+u3+u4+u5=10-5 -5=0非负整数解C(0+5-1,5-1)
ui中的i 就是任意5个选2个就是C(5,2)
-----------
三个不满足
令其中三个ui=yi-4 其他 ui=yi
u1+u2+u3+u4+u5=10-5 -5-5=-5非负整数解 无解
结果C(10+5-1,5-1)-C(5,1)C(6+5-1,5-1)+C(5,2)C(0+5-1,5-1)- 0
和 陆老师的是一样
但是 我想解释 容斥原理 结束条件 要么找完 要么一定要找到空集
空集 也是找完了 同时满足n个条件是空集 再加一个条件 也是空集
由于组合的性质也等于C(m,n) 如果n<0 C(m,n) 一定等于0
这种题可以总结成
x1+x2+...xk=r 有多少[a,b] 的整数解
\( \binom{k}{0} \binom{r-ak}{k-1}-\binom{k}{1} \binom{r-ak-(b-a+1)}{k-1}+\binom{k}{2} \binom{r-ak-2(b-a+1)}{k-1}...\\+(-1)^i\binom{k}{i} \binom{r-ak-i(b-a+1)}{k-1}...\\+(-1)^k\binom{k}{k} \binom{r-ak-k(b-a+1)}{k-1}\) |
|