1、第一章 排列与组合 计数基本原理加法法则 :若 |A| = m , |B| = n , AB = , 则 |AB| = m + n 在加法法则中要注意事件 A 和 事件 B 的互斥乘法法则 :若 |A| = m , |B| = n , AB = (a,b) | a A,b B, 则 |A B| = m n在乘法法则中要注意事件 A 和 事件 B 的相互独立性 排列 从 n个不同的元素中，取 r个不重复的元素，按次序排列，称为从 n个中取 r个的无重排列。排列的全体组成的集合用 P(n,r)表示。排列的个数用 P(n,r)表示。当r=n时称为全排列。 P(n,r)=n(n-1)(n-r+1) 组
2、合 从 n个不同元素中取 r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从 n个中取 r个的无重组合。组合的全体组成的集合用 C(n,r)表示，组合的个数用 C(n,r)表示， C(n,r)=P(n,r)/r!=n!/(r!(n-r)!) 允许重复的排列 (多重集排列 ): 求 r1个 1， r2个 2， ， rt个 t的排列数，设 r1+r2+r t=n,设此排列数为 P(n;r1,r2,r t),对 1， 2， ， t分别加下标，得到 P(n； r1,r2,r t)r1!r2! rt! = n! P(n； r1,r2,r t)= =( ) 圆周排列 从 n个中取 r个的圆排列的排
3、列数为 P(n,r)/r , 2rn 项链排列 P(n,r)/2r , 3rn 在圆排列的基础上，正面向上和反面向上两种方式放置各个数是同一个排列。n!r1!r2!r t!nr1 r2 r t 允许重复的组合 (多重集的组合 )n个不同的元素中取 r个做允许重复的组合 ,其组合数为 C(n+r-1,r)线性方程非负整数解x1+x2+xn=b 的非负整数解的个数 C(n+b-1,b) 不相邻的组合n个数中取 r个作不相邻的组合 ,组合数为 C(n-r+1,b) 数学归纳法 多重集的组合 给三个孩子发水果 ,一共 12个一样的苹果 ,每个孩子至少有一个水果 ,问有多少种分法 ? 解 :设分给第 i
4、个孩子的水果数为 xi, xi1 x1+x2+x3=12 令 y1=x1-1,y2=x2-1,y3=x3-1 y1+y2+y3=9 yi0 非负整数解的个数为 C(9+3-1,9)=55 排列的生成算法 “原排列 ”“ 原中介数 ”“ 新中介数 ”“ 新排列 ” 递增进位制和递减进位制数 (A)字典序法(B)递增进位制数法(C)递减 进位制数法(D)邻位对换法 递增进位制数 4121，它的进制从右向左依次是 2、 3、 4、5 如果将 4121加上 1的话得到结果是 4200 序号 :十进制数 递增进位制数（ a1 a2 a3 a4 a5 a6 a7 a8 a9）的序号为a1*9! + a2*
5、8! + .+ a8*2! + a9*1! 序号 100的递增进位制数就是 4020，即 4*4！ + 0*3！ + 2*2！ + 0*1！ =100 递减进位制数（ a1 a2 a3 a4 a5 a6 a7 a8 a9）为： (a1 * 1 + a2) * 2 + a3) * 3 + + a7) * 8 + a8) * 9 + a9= 序号 序号 100的递减进位制数就是 131，即 （ 1*8 + 3） *9 + 1 = 100 其加减法的进位需要小心； 序号和数字的转换 5 4 3 27： 8的右边 比 8小 的数的个数 求 839647521的下 100个排列 字典序法求 839647
6、521的中介数此中介数加上 100的递增进位制数 4020后得到新中介数 72652011,计算对应的排列 2： 3的右边 比 3小 的数的个数6： 9的右边 比 9小 的数的个数4： 6的右边 比 6小 的数的个数： 4的右边 比 4小 的数的个数3： 7的右边 比 7小 的数的个数2： 5的右边 比 5小 的数的个数1： 2的右边 比 2小 的数的个数72642321由 72652011推算出P1 P2 P3 P4 P5 P6 P7 P8 P9(不对？）_ _ _ _ _ _ _ _ _8 3 9 7 4 1 5 2 6 P1=87+1=8 P2=32+1=36+1=73和 8已经出现 P3=9 不考的内容组合的生成Stirling公式第二章 递推关系与母函数 二项式定理(x+y)n=C(n,k)xn-kyk k=0-n(1+x)n= C(n,k)xn-k k=0-n 多项式定理(x1+x2+xt) n=C(n;r1,r2,.rt)x1 r1x2r2 xtrtr1+r2+rt=n因式分解一元二次方程求解多项式长除法
