2010第三章myc_I_容斥_267006836.ppt

* 讨论 x1+x2+x3=S 0≤x1 ≤ m1, 0≤x2 ≤ m2； 0≤x3 ≤ m3 ?1=m1-x1, ?2=m2-x2, ?3=m3-x3 ?1+ ?2 + ?3 =m1+m2+m3-S 0≤ ?1 ≤ m1, ?2 ≤ m2, ?3 ≤ m3 若m1+m2+m3-S ≤min(m1,m2,m3)则 x1+x2+x3=S 0≤x1 ≤ m1, 0≤x2 ≤ m2； 0≤x1 ≤ m3 ?1+ ?2 + ?3 =m1+m2+m3-S ?1, ?2, ?3≥0 整数解个数相等 * §3.3 举例 例8: 错排问题: n个元素依次给以标号1，2，…，n。n个元素的全排列中，求每个元素都不在自己原来位置上的排列数。 设Ai为数i在第i位上的全体排列，i=1，2，…，n。因数字i不能动，因而有：|Ai|=(n-1)! |Ai∩Aj |=(n-2)! 每个元素都不在原来位置的排列数为 * 例9 在8个字母A,B,C,D,E,F,G,H的全排列中,求使A,C,E,G四个字母不在原来上的错排数目。 解：8个字母的全排列中，令AA,AC,AE,AG分别表A,C,E,G在原来位置上的排列，则错排数为： * 求8个字母A,B,C,D,E,F,G,H的全排列中只有4个不在原来位置的排列数。 解：8个字母中只有4个不在原来位置上，其余4个字母保持不动，相当于4个元素的错排，其数目为 故8个字母的全排列中有4个不在原来位置上的排列数应为：C(8,4)·9=630 * §3.4 棋盘多项式和有限制排列 有限制排列 例　4个x ，3个y，2个z的全排列中，求不出现xxxx，yyy，zz图象的排列。 解　设出现xxxx的排列的集合记为A1， |A1|= =60; 设出现yyy的排列的集合记为A2， | A2|= =105； 设出现zz的排列的集合记为A2， | A3|= =280； |A1∩A2|= =12； |A1∩A3|= =20； |A2∩A3|= =30； |A1∩A2∩A3|=3!=6； 全排列的个数为： 9！ =1260； 所以： |A1∩A2∩A3|=1260－(60+105+280)+(12+20+30)－6 =871 * §3.4 棋盘多项式和有限制排列 棋盘多项式 n个不同元素的一个全排列可看做n个相同的棋子在n×n的棋盘上的一个布局。布局满足同一行（列）中有且仅有一个棋子non-attacking rooks x x x x x 如图所示的布局对应 于排列41352。 1 2 3 4 5 P1 P2 P3 P4 P5 * §3.4 棋盘多项式和有限制排列 可以把棋盘的形状推广到任意形状： r1( )=1， r1( )=2， r1( )=2， r2( )=0， r2( )=1。 令r k（C）表示k个棋子布到棋盘C上的方案数。如： * §3.4 棋盘多项式和有限制排列 定义 　设C为一棋盘，称R(C)= ∑ rk(C) xk为C的棋盘多项式。　 规定 r0(C)=1，包括C=Ф时。 k=0 n 性质1:设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子后的棋盘，则 rk(C)=rk－1(Ci)＋rk(Ce) 对任一指定的格子， 要么布子，方案数为 rk-1(Ci)； 要么不布子，方案数为 rk(Ce)。 * Ci Ce * §3.4 棋盘多项式和有限制排列 　　 r0(C)＝1 ?? 设C有n个格子，则 r1(C)＝n． r1(C)＝r0(Ci) + r1(Ce)，∵　r1(Ce)＝n－1 ∴ r0(Ci)＝1．故规定 r0(C)＝1是合理的． * §3.4 棋盘多项式和有限制排列 　该性质扩展到棋盘多项式，从而　　 n k=0 　　R(C)= ∑ rk(C) xk n k=1 　　 ＝１＋∑[rk－1(Ci)+ rk(Ce)]xk n-1 k=0 n k=0 　 = x ∑ rk(Ci)xk + ∑ rk(Ce)xk 　　 　 ＝xR(Ci) + R(C e)