第2章-组合数学初步.ppt

第2章 组合数学初步 引言 2.1 计数基本原理 2.2 鸽笼原理 2.3 排列与组合 *2.4 递推关系 引言 2.1 计数基本原理 2.1.1 加法原理和乘法原理 2.1.2 包含排斥原理 2.1.1 加法原理和乘法原理 2.1.2 包含排斥原理 2.2 鸽笼原理 2.2.1 鸽笼原理 2.2.2 鸽笼原理的加强形式 2.3 排列与组合 2.3.1 基本的排列与组合 2.3.2 多重集合的排列与组合 2.3.3 二项式系数 2.3.1 基本的排列与组合 2.3.1.1 集合的排列 线排列 圆排列 2.3.1.2 集合的组合 2.3.1.1 集合的排列 2.3.1.2 集合的组合 2.3.2 多重集合的排列与组合 2.3.2.1 多重集合的排列 2.3.2.2 多重集合的组合 2.3.2.1 多重集合的排列 2.3.2.2 多重集合的组合 2.3.3 二项式系数 2.3.3.1 二项式定理 2.3.3.2 二项式系数的基本性质 2.3.3.3 组合恒等式 2.3.3.1 二项式定理 2.3.3.2 二项式系数的基本性质 2.3.3.3 组合恒等式 第6章 复习 1。基本原理：加法原理、乘法原理、容斥原理、 2。鸽笼原理及其加强形式（3个） 3。基本的排列组合（圆排列） 4。多重集合的排列组合 5。二项式定理 6。二项式系数的基本性质 7。组合恒等式 解: A单位7人共有 种排列. 7! 设A1 A2 A3 A4 A5 A6 A7是A的一个排列, 定后, B单位3人中的第1人有 种选择, 两端固 6 见下图: 例 A单位有7位代表, B单位有3位代表, 排成一行合影, 要求B单位3人不能相邻，而且A单位的两人排在两端. 问有多少种不同的排列方案? A1*A2*A3*A4*A5*A6*A7 其中*的位置是第1人可选的位置. 第2位为了不与第1位相邻, 故只有 种选择. 5 第3位有 种选择. 4 故排列总数为 . 7!×6×5×4 显然, 同一个圆排列（循环排列） A1 A4 A3 A7 A6 A5 A2 对应7个不同的线性排列: A1 A2 A3 A4 A5 A6 A7, A2 A3 A4 A5 A6 A7 A1, A3 A4 A5 A6 A7 A1 A2, A4 A5 A6 A7 A1 A2 A3, A5 A6 A7 A1 A2 A3 A4, A6 A7 A1 A2 A3 A4 A5, A7 A1 A2 A3 A4 A5 A6, 说明: 对于相同的问题，圆排列的数目比线排列的的数目少. 前面所学的r排列都是在直线上进行的, 所以也叫线性r排列. 若在圆周上进行排列, 结果又如何呢? 定理2.10 n元集合的圆r排列数为 特别地, n个元素的圆n排列(r=n时)个数是(n-1)!. 例 10个男生和5个女生聚餐, 围坐在圆桌旁, 任意两个女生不相邻的坐法有多少种？ 解: 先将10个男生进行圆排列, 共有 种排法. 9! 对男生的任一种排法, 生之间, 每两个男生之间只能插一个女生, 把5个女生插在10个男 女生在10个位置中任选 5个位置的排列数为 P(10, 5) 由乘法原则知,共有 种坐法. 9!×P(10, 5) . 定义: n元集合S的r组合是指从S中取出r个元素的一种无序选择, 其组合数记为C(n, r) 或 或 定理2.11 若0≤r≤n, 则 显然有: 证明: 设S是一n元集合, 任取S的一个r组合, 将该 r组合中的r个元素进行排列, 可得到 个 P(r, r)=r! S中的r排列. 且S中的任一r排列都恰好可通过 将S中的某一r组合排序而得到. 所以, 有 例 学院欲将6名保送研究生推荐给3个单位, 每个单位2名, 问有多少种方案? 解: 推荐给某个单位的两名学生的顺序是无关紧 要的, 这是一个组合问题. 先从6名学生中选出2名给第1个单位, 有 种 选法. 然后从余下的4名学生中选出2名给第2个 单位, 有 种选法. 最后2名学生给第三个单位. 由乘法原理: 所以共有90种方案. n元集合的r排列是指从n个不同的元素里, 每次取出r个互不相同的元素进行排列. 然而在现实生活中, 并不一定是对不同的元素进行排列. 例如, 对一组数据排序就是求它的一个排列, 而这些数据中可能