1、组合数学组合数学的蓬勃发展是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。这里主要讲组合分析（计数和枚举）。组合分析是组合算法的基础第一讲 基本计数方法一1.1 加法法则与乘法法则1.1 加法法则与乘法法则 加法法则 设事件 A有 m种产生方式，事件 B有 n种产生方式，则事件 A或 B之一有 m+n种产生方式。集合论语言：若 |A| = m , |B| = n , AB = , 则 |AB| = m + n 。1.1 加法法则与乘法法则 例 某班选修企业管理的有 18 人，不选的有 10 人，则该
2、班共有 18 + 10 = 28 人。 例 北京每天直达上海的客车有 5 次，客机有 3 次， 则每天由北京直达上海的旅行方式有 5 + 3 = 8 种。1.1 加法法则与乘法法则 乘法法则 设事件 A有 m种产生式，事件 B有 n种产生方式，则事件 A与 B有 m n种产生方式。集合论语言：若 |A| = m , |B| = n , AB = (a,b) | a A,b B, 则 |A B| = m n 。1.1 加法法则与乘法法则例 某种字符串由两个字符组成，第一个字符可选自 a， b， c， d， e， 第二个字符可选自 1， 2， 3，则这种字符串共有 5 3 = 15 个。例 从 A
3、到 B有三条道路，从 B到 C有两条道路，则从 A经 B到 C有 32=6 条道路。1.1 加法法则与乘法法则 例 某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有 42 = 8种着色方案。 若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则，方案数就不是 4 4 = 16， 而只有 4 3 = 12 种。 在乘法法则中要注意事件 A 和 事件 B 的相互独立性。1.1 加法法则与乘法法则例 1)求小于 10000的含 1的正整数的个数2)求小于 10000的含 0的正整数的个数1)小于 10000的不含 1的正整数可看做 4位数 ,但 0
4、000除外 .故有 9999 1 6560个 .含 1的有： 9999 6560=3439个另 : 全部 4位数有 10 个 ,不含 1的四位数有 9 个 ,含 1的 4位数为两个的差 : 10 9 = 3439个4 44 42)“含 0”和 “含 1”不可直接套用 。 0019含 1但不含 0。在组合的习题中有许多类似的 隐含 的规定，要特别留神。不含 0的 1位数有 9个， 2位数有 9 个，3位数有 9 个， 4位数有 9 个 不含 0小于 10000的正整数有9+9 +9 +9 =(9 1)/(9 1)=7380个含 0小于 10000的正整数有 9999 7380=2619个23 42 3 4 51.2排列与组合定义 从 n个不同的元素中，取 r个不重复的元素，按次序排列，称为从 n个中取 r个的 无重排列 。排列的全体组成的集合用 P(n,r)表示。排列的个数用 P(n,r)表示。当 r=n时称为 全排列 。一般不说可重即无重。可重排列的相应记号为 - P(n,r),P(n,r)。 l
