组合数学第一章基本计数问题精品文稿.ppt

《组合数学第一章基本计数问题精品文稿.ppt》由会员分享，可在线阅读，更多相关《组合数学第一章基本计数问题精品文稿.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、组合数学第一章基本计数问题第1页，本讲稿共26页一、基本计数问题一、基本计数问题 1.3 多重集合的排列与组合1.1 加法原则与乘法原则 1.2 排列与组合 1.4 二项式系数1.5 集合的分划与第二类Stirling数1.6 正整数的分拆1.7 分配问题第2页，本讲稿共26页1.1 1.1 加法原则与乘法原则加法原则与乘法原则 加法原则:设事件A有m种选取方式,事件B有n种选取方式,则选A或B共有m+n种方式.定理1.1.1 设A,B为有限集，则 推论1.1.1设n个有限集合 满足 则 机动 目录 上页 下页 返回 结束 第3页，本讲稿共26页例1：在所有六位二进制数中，至少有连续4位是1的

2、有多少个？机动 目录 上页 下页 返回 结束 第4页，本讲稿共26页乘法原则:设事件A有m种选取方式,事件B有n种选取方式,则选取A以后再选取B共有mn种方式.定理1.1.2设A,B为有限集，则 推论1.1.2 设n个有限集合 则则 机动 目录 上页 下页 返回 结束 第5页，本讲稿共26页例2：从5位先生、6位女士、2位男孩和4位女孩中选取 1位先生、1位女士、1位男孩和1位女孩，有多少种方式？从中选取一个人的方式有多少种？例3：从1000到9999之间有多少个各位数字不同的奇数？机动 目录 上页 下页 返回 结束 第6页，本讲稿共26页1.2 1.2 排列与组合排列与组合 n元集合S的一个

3、r 排列是指从S中选出r个元素,然后 将其按次序排列。记为P(n,r)。当r=n时，称为全排列。定理1.2.1设n，r为正整数，则 机动 目录 上页 下页 返回 结束 第7页，本讲稿共26页例1：将a,b,c,d,e,f 进行排列，问：（1）使得字母b正好在字母e的左邻的排列有多少种？（2）使得字母b在字母e的左边的排列有多少种？例2：从1,2,9中选出不同的7个数字组成七位数，要求5与6不相邻，问有多少种方法？机动 目录 上页 下页 返回 结束 第8页，本讲稿共26页定理1.2.2n元集合的r圆排列数为：例如：集合S=1,2,3,4有6个4圆排列。例3：10个男生和5个女生聚餐，围坐在圆桌旁

4、，任意两个女生不相邻的坐法有多少种？机动 目录 上页 下页 返回 结束 第9页，本讲稿共26页 n元集合S的一个r组合是指从S中选出r个元素的一种 无序选择。其组合数记为定理1.2.3则 推论1.2.1则 机动 目录 上页 下页 返回 结束 第10页，本讲稿共26页例4：系里欲将6名保送研究生推荐给3个单位，每个单位2名，问有多少种方案？例5：在一个凸n(n3)边形C的内部，如果没有三条对角线共点，求其全部对角线在C内部的交点的个数。定理1.2.4 对任意正整数n，有机动 目录 上页 下页 返回 结束 第11页，本讲稿共26页例6：单射函数的个数等于P(m,n)，其中，例7：求至少出现一个6且

5、能被3整除的五位数的个数。例8：某车站有6个入口，每个入口每次只能进一个人，问9人小组共有多少种进站方案？机动 目录 上页 下页 返回 结束 第12页，本讲稿共26页1.3 1.3 多重集合的排列与组合多重集合的排列与组合机动 目录 上页 下页 返回 结束 多重集合表示为：其中为M中所有的互不相同的元素，M中有是正整数，也可以是。定理1.3.1多重集合 的r排列 例1：用26个英文字母可以构造出多少个包含4个元音字母、长度为8的字符串。第13页，本讲稿共26页定理1.3.2多重集合 的全排列数为：机动 目录 上页 下页 返回 结束 例2：(0,0)(m,n)从(0,0)点沿水平和垂直道路可以走

6、到(m,n)点，例3：将6个蓝球，5个红球，4个白球，3个黄球排成一行，要求黄球不挨着，问有多少种排列方式？问有多少种走法？第14页，本讲稿共26页定理1.3.3多重集合 的r组合机动 目录 上页 下页 返回 结束 例4：从M=1,2,n中能够取出多少个长为r的递增序列使得定理1.3.4多重集合 要求至少出现一次的r组合数为第15页，本讲稿共26页定义1.3.1 设集合 是一个全序集，那么由X 中的n个字母构成的字符串 只要 就称其为X上长度为 n的增字。例如例如若M=a,b,c,d,且有顺序abcd,则acc是一个增字.机动 目录 上页 下页 返回 结束 定理1.3.5设集合 是一全序集，则

7、X上长度为n的增字共有第16页，本讲稿共26页1.4 1.4 二项式系数二项式系数机动 目录 上页 下页 返回 结束 定理1.4.1(二项式定理二项式定理)设n为一正整数，则对任意的x和y，有第17页，本讲稿共26页机动 目录 上页 下页 返回 结束 定理1.4.2对一切实数和x(|x|1),有当=-n时：第18页，本讲稿共26页机动 目录 上页 下页 返回 结束 当=1/2时：第19页，本讲稿共26页机动 目录 上页 下页 返回 结束 二项式系数的基本性质：二项式系数的基本性质：当n,r为非负整数，且n r时：（1）对称关系：（2）递推关系：第20页，本讲稿共26页（3）单峰性：当n为偶数时

8、，有当n为奇数时，有机动 目录 上页 下页 返回 结束 第21页，本讲稿共26页机动 目录 上页 下页 返回 结束 组合恒等式：组合恒等式：等式1：等式2：等式3：第22页，本讲稿共26页机动 目录 上页 下页 返回 结束 等式4：等式5：等式6：第23页，本讲稿共26页机动 目录 上页 下页 返回 结束 定理1.4.3(多项式定理多项式定理)设n为一正整数，则其中：多项式系数求和号是对所有满足的非负整数序列求和。第24页，本讲稿共26页机动 目录 上页 下页 返回 结束 例1：展开问的系数是多少？例2：展开问的系数是多少？第25页，本讲稿共26页机动 目录 上页 下页 返回 结束 多项式系数的基本性质：多项式系数的基本性质：1.若端求和号中所包含的项数是方程：的非负整数解的数目，2.在多项式定理中，令则有的n 排列数第26页，本讲稿共26页