令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的子集
令P表示D的4-组合中多于2个a这一性质, P2表示D的4组合中多于2个b这一性质, P表示D的4组合中多于4个c这一性质, 令A(i=1,2,3表示D的具有性质P(i=1,2,3) 的4组合全体。则4组合数等于 A∩A2∩石3
令P1表示D的4-组合中多于2个a这一性质， P2表示D的4-组合中多于2个b这一性质， P3表示D的4-组合中多于4个c这一性质， 令Ai (i=1,2,3)表示D的具有性质 Pi (i=1,2,3) 的 4-组合全体。则4-组合数等于 | | A1 A2 A3
考察A1:A1是D的4组合中多于2个a的组合全体, 即A是D的4组合中至少出现3个的组合全体。 对A的任-4组合中拿走3个a,就是D的1组合。 又对D的任一1组合,加入3个a,就是a至少出现3 个的4组合, 所以1就是D的1组合数,即 A1=C(3+1-1,1)=C(3,1), 考察A2:A2是D的4组合中多于2个b的组合全体, 即A2是D的4组合中b至少出现3个的组合全体。 对A2的任一4组合中拿走3个b,就是D的1组合。 对D的任一1组合,加入3个b,就是b至少出现3个 的4组合, 所以2就是D的1组合数,即 1A2=C(3+1-1,1)=C(3,1)
考察A1：A1是D的4-组合中多于2个a的组合全体， 即A1是D的4-组合中a至少出现3个的组合全体。 对A1的任一4-组合中拿走3个a，就是D的1-组合。 又对D的任一1-组合，加入3个a，就是a至少出现3 个的4-组合， 所以|A1 |就是D的1-组合数，即 |A1 |=C(3+1-1,1)=C(3,1)， 考察A2：A2是D的4-组合中多于2个b的组合全体， 即A2是D的4-组合中b至少出现3个的组合全体。 对A2的任一4-组合中拿走3个b，就是D的1-组合。 对D的任一1-组合，加入3个b，就是b至少出现3个 的4-组合， 所以|A2 |就是D的1-组合数，即 |A2 |=C(3+1-1,1)=C(3,1)
考察A3:A3是D的4组合中多于4个c的组合全体 即A3是D的4组合中c至少出现5个的组合全体, 这样的组合是不存在的。即A3=0 考察A1∩A2:A10A2是D的4-组合中多于2个a和多于2 个b的组合全体, 即A1∩A2是D的4组合中至少出现3个且b至少出现3个 的组合全体。 这样的组合是不存在的。即AnA=0, 类似可以知道A1∩A3=A2OA3=A10A2∩A3=0。 因此 A∩2∩A3上=C(6,2)-(C(3,1)+C(31)=9
考察A3：A3是D的4-组合中多于4个c的组合全体 即A3是D的4-组合中c至少出现5个的组合全体, 这样的组合是不存在的。即|A3 |=0 考察A1∩A2：A1∩A2是D的4-组合中多于2个a和多于2 个b的组合全体， 即A1∩A2是D的4-组合中a至少出现3个且b至少出现3个 的组合全体。 这样的组合是不存在的。即|A1∩A2 |=0， 类似可以知道|A1∩A3 |=|A2∩A3 |=|A1∩A2∩A3 |=0。 因此 | A1 A2 A3 |= C(6,2) − (C(3,1) + C(3,1)) = 9
三、错位问题 现在考虑这样的问题:在书架上有5本书,把 它们全部拿下来,然后再放回去,要使得没有 一本在原来位置上,有多少种放法? 这就是错位排列问题。 定义:设集合S={1,2,…,mn},如果S的一个排列, i满足i1≠1,i2≠2,in≠n,则称该排列是S 的一个错位排列。S的所有错位排列数记为Dn 当n=1时,只有一个数,不存在错位,所以 D1=0 当n=2时,1,2错位,只能排成2,1,所以D2=1; 当n=3时,1,2,3错位,可排成2,3,1,或3,1,2 所以D3=2;
三、错位问题 现在考虑这样的问题：在书架上有5本书，把 它们全部拿下来，然后再放回去，要使得没有 一本在原来位置上，有多少种放法？ 这就是错位排列问题。 定义：设集合S={1,2,…,n}，如果S的一个排列， i1 ,i2 ,…,in ,满足i11,i22,…,inn,则称该排列是S 的一个错位排列。S的所有错位排列数记为Dn。 当n=1时，只有一个数，不存在错位，所以 D1=0； 当n=2时，1,2错位，只能排成2,1，所以D2=1； 当n=3时，1,2,3错位，可排成2,3,1，或3,1,2， 所以D3=2；
定理:对于n1,有 D=n (1-+ +…+( 2!3! 证明:设S={1,2,…,n},用X表示S的所有排列集 合,则X|= n 对于j=1,2,…,n,规定在一个排列中,如果j在第 j个位置上,则该排列具有性质p 令A表示具有性质p的所有排列集合。 则S的错位排列全体是: A1∩A2∩…∩A
定理：对于n1，有 ) ! 1 ( 1) 3! 1 2! 1 1! 1 !(1 n D n n n = − + − ++ − 证明：设S={1,2,…,n}，用X表示S的所有排列集 合，则|X|=n!。 对于j=1,2,…,n，规定在一个排列中，如果j在第 j个位置上，则该排列具有性质pj。 令Aj表示具有性质pj的所有排列集合。 则S的错位排列全体是： A1 A2 An