令A(i=1,2,3)表示D的具有性质Pi=1,2,3)的10-组 合全体。则s的10-组合数等于14∩n∩ n=n1+n2+….+nk 当r<n,且存在某个nr时,S的r组合数没有 一般的求解方法,但可利用容斥原理予以解决 例:求S={3a,4b,5c}的10组合数 解:把容斥原理应用到多重集D=oa,∞b, 考察A1:A是D的10-组合中多于3个a的组合全体 即A是D的10-组合中至少出现4个的组合全体。 对A的任一10-组合中拿走4个a,就是D的6组合。 对D的任一6组合,加入4个a,就是a至少出现4个的 10-组合,所以A1就是D的6组合数,即 A1=C(3+6-1,6)=C(8,6)=C(8,2)
二、有限多重集的r-组合数 设多重集 S={n1·a1 ,n2·a2 ,…,nk·ak }, n=n1+n2+…+nk， 当r<n，且存在某个ni<r时，S的r-组合数没有 一般的求解方法，但可利用容斥原理予以解决 例：求S={3·a,4·b,5·c}的10-组合数。 解：把容斥原理应用到多重集D={·a, ·b, ·c}的所有10-组合的集合Y上， 则S的10-组合全体即为Y的子集。 令P1表示D的10-组合中多于3个a这一性质， P2表示D的10-组合中多于4个b这一性质， P3表示D的10-组合中多于5个c这一性质， 令Ai (i=1,2,3)表示D的具有性质Pi (i=1,2,3)的10-组 合全体。则S的10-组合数等于 | | A1 A2 A3 考察A1：A1是D的10-组合中多于3个a的组合全体， 即A1是D的10-组合中a至少出现4个的组合全体。 对A1的任一10-组合中拿走4个a，就是D的6-组合。 对D的任一6-组合，加入4个a，就是a至少出现4个的 10-组合，所以|A1 |就是D的6-组合数，即 |A1 |=C(3+6-1,6)=C(8,6)=C(8,2)
考察A2:A2是D的10组合中多于4个b的组合全体 即A2是D的10组合中b至少出现5个的组合全体 对A2的任-10-组合中拿走5个b,就是D的5组合。 对D的任一5组合,加入5个b,就是b至少出现5个 的10-组合 所以|A2就是D的5-组合数,即 A2=C(3+5-1,5)=C(7,5)=C(7,2), 考察A3:A3是D的10-组合中多于5个c的组合全体 即A3是D的10-组合中c至少出现6个的组合全体 对A3的任-10-组合中拿走6个c,就是D的4组合。 对D的任一4组合,加入6个c,就是c至少出现6个 的10组合 所以A3就是D的4组合数,即 1A3=C(3+4-1,4)=C(6,4)=C(6,2)
考察A2：A2是D的10-组合中多于4个b的组合全体 即A2是D的10-组合中b至少出现5个的组合全体 对A2的任一10-组合中拿走5个b，就是D的5-组合。 对D的任一5-组合，加入5个b，就是b至少出现5个 的10-组合， 所以|A2 |就是D的5-组合数，即 |A2 |=C(3+5-1,5)=C(7,5)=C(7,2)， 考察A3：A3是D的10-组合中多于5个c的组合全体， 即A3是D的10-组合中c至少出现6个的组合全体 对A3的任一10-组合中拿走6个c，就是D的4-组合。 对D的任一4-组合，加入6个c，就是c至少出现6个 的10-组合， 所以|A3 |就是D的4-组合数，即 |A3 |=C(3+4-1,4)=C(6,4)=C(6,2)
考察A1nA2:A1nA2是D的10-组合中多于3个a 和多于4个b的组合全体, 即A1nA2是D的10-组合中a至少出现4个且b至 少出现5个的组合全体。 对A1nA2的任-10组合中拿走4个a和5个b就是 D的1-组合。 对D的任一1组合,加入4个a和5个b,就是a至 少出现4个且b至少出现5个的10-组合, 所以|A1∩A2就是D的1组合数,即 A1∩A2=C(3+1-1,1)=C(3,1)
考察A1∩A2：A1∩A2是D的10-组合中多于3个a 和多于4个b的组合全体， 即A1∩A2是D的10-组合中a至少出现4个且b至 少出现5个的组合全体。 对A1∩A2的任一10-组合中拿走4个a和5个b就是 D的1-组合。 对D的任一1-组合，加入4个a和5个b,就是a至 少出现4个且b至少出现5个的10-组合， 所以|A1∩A2 |就是D的1-组合数，即 |A1∩A2 |=C(3+1-1,1)=C(3,1)
考察A1∩A2A3:AnA2A3是D的10组合中多于3 个a、多于4个b和多于5个c的组合全体, 即A1∩A2A3是D的10-组合中a至少出现4个,b至少出 现5个且c至少出现6个的组合全体, 这样的组合是不存在的。 所以A20A=A1A2nA3=0。 因此 A∩A2∩A3=C(12,2)-(C(8,2)+C(7,2)+C(62)+(C(3)+1)=6 考察A2A3:A2A3是D的10组合中多于4个b和多 于5个c的组合全体 即A2∩A3是D的10-组合中b至少出现5个且c至少出 现6个的组合全体, 这样的组合是不存在的
考察A1∩A3：A1∩A3是D的10-组合中多于3个a和多 于5个c的组合全体， 即A1∩A3是D的10-组合中a至少出现4个且c至少出 现6个的组合全体。 对A1∩A3的任一10-组合中拿走4个a，6个c就是D的 0-组合。 所以|A1∩A3 |就是D的0-组合数，即 |A1∩A3 |=1， 考察A2∩A3：A2∩A3是D的10-组合中多于4个b和多 于5个c的组合全体， 即A2∩A3是D的10-组合中b至少出现5个且c至少出 现6个的组合全体， 这样的组合是不存在的。 考察A1∩A2∩A3：A1∩A2∩A3是D的10-组合中多于3 个a、多于4个b和多于5个c的组合全体， 即A1∩A2∩A3是D的10-组合中a至少出现4个,b至少出 现5个且c至少出现6个的组合全体， 这样的组合是不存在的。 所以|A2∩A3 |=| A1∩A2∩A3 |=0。 因此 | A1 A2 A3 |= C(12,2) − (C(8,2) + C(7,2) + C(6,2)) + (C(3,1) +1) = 6
例:求x1+x2+x3=5(0≤x1≤2,0≤x2≤2,1≤x3≤5) 的整数解个数。 解:将约束条件一律改为≥0。 X2=X 3 3-19 则原问题即为求在约束条件0≤x≤2, 0≤x2≤2,0≤x3≤4下x1+x2+x3=4的整数解个 数。 此问题与多重集S={2a,2b,4c}的4组合 数相同。 把容斥原理应用到多重集 D={∞a,∞b,c}的所有4组合的集合Y上, 则S的4组合全体即为Y的子集
例：求x1+x2+x3 =5(0x12,0x22,1x35) 的整数解个数。 解:将约束条件一律改为0。 令x3 '=x3 -1， 则 原问题即 为求在约 束条件 0 x12, 0x22,0x3 '4下x1+x2+x3 '=4的整数解个 数。 此问题与多重集S={2·a,2·b,4·c}的4-组合 数相同。 把 容 斥 原 理 应 用 到 多 重 集 D={·a,·b,·c}的所有4-组合的集合Y上， 则S的4-组合全体即为Y的子集