令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