《组合数学第一章基本计数问题幻灯片.ppt》由会员分享，可在线阅读，更多相关《组合数学第一章基本计数问题幻灯片.ppt（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、组合数学第一章基本计数问题第1页，共26页，编辑于2022年，星期一一、基本计数问题一、基本计数问题 1.3 多重集合的排列与组合1.1 加法原则与乘法原则 1.2 排列与组合 1.4 二项式系数1.5 集合的分划与第二类Stirling数1.6 正整数的分拆1.7 分配问题第2页，共26页，编辑于2022年，星期一1.1 1.1 加法原则与乘法原则加法原则与乘法原则 加法原则:设事件A有m种选取方式,事件B有n种选取方式,则选A或B共有m+n种方式.定理1.1.1设A,B为有限集，则 推论1.1.1设n个有限集合 满足 则 机动 目录 上页 下页 返回 结束 第3页，共26页，编辑于2022
2、年，星期一例1：在所有六位二进制数中，至少有连续4位是1的有多少个？机动 目录 上页 下页 返回 结束 第4页，共26页，编辑于2022年，星期一乘法原则:设事件A有m种选取方式,事件B有n种选取方式,则选取A以后再选取B共有mn种方式.定理1.1.2设A,B为有限集，则 推论1.1.2 设n个有限集合 则则 机动 目录 上页 下页 返回 结束 第5页，共26页，编辑于2022年，星期一例2：从5位先生、6位女士、2位男孩和4位女孩中选取 1位先生、1位女士、1位男孩和1位女孩，有多少种方式？从中选取一个人的方式有多少种？例3：从1000到9999之间有多少个各位数字不同的奇数？机动 目录 上
3、页 下页 返回 结束 第6页，共26页，编辑于2022年，星期一1.2 1.2 排列与组合排列与组合 n元集合S的一个r 排列是指从S中选出r个元素,然后 将其按次序排列。记为P(n,r)。当r=n时，称为全排列。定理1.2.1设n，r为正整数，则 机动 目录 上页 下页 返回 结束 第7页，共26页，编辑于2022年，星期一例1：将a,b,c,d,e,f 进行排列，问：（1）使得字母b正好在字母e的左邻的排列有多少种？（2）使得字母b在字母e的左边的排列有多少种？例2：从1,2,9中选出不同的7个数字组成七位数，要求5与6不相邻，问有多少种方法？机动 目录 上页 下页 返回 结束 第8页，共
4、26页，编辑于2022年，星期一定理1.2.2n元集合的r圆排列数为：例如：集合S=1,2,3,4有6个4圆排列。例3：10个男生和5个女生聚餐，围坐在圆桌旁，任意两个女生不相邻的坐法有多少种？机动 目录 上页 下页 返回 结束 第9页，共26页，编辑于2022年，星期一 n元集合S的一个r组合是指从S中选出r个元素的一种 无序选择。其组合数记为定理1.2.3则 推论1.2.1则 机动 目录 上页 下页 返回 结束 第10页，共26页，编辑于2022年，星期一例4：系里欲将6名保送研究生推荐给3个单位，每个单位2名，问有多少种方案？例5：在一个凸n(n3)边形C的内部，如果没有三条对角线共点，
5、求其全部对角线在C内部的交点的个数。定理1.2.4对任意正整数n，有机动 目录 上页 下页 返回 结束 第11页，共26页，编辑于2022年，星期一例6：单射函数的个数等于P(m,n)，其中，例7：求至少出现一个6且能被3整除的五位数的个数。例8：某车站有6个入口，每个入口每次只能进一个人，问9人小组共有多少种进站方案？机动 目录 上页 下页 返回 结束 第12页，共26页，编辑于2022年，星期一1.3 1.3 多重集合的排列与组合多重集合的排列与组合机动 目录 上页 下页 返回 结束 多重集合表示为：其中为M中所有的互不相同的元素，M中有是正整数，也可以是。定理1.3.1多重集合 的r排列
6、 例1：用26个英文字母可以构造出多少个包含4个元音字母、长度为8的字符串。第13页，共26页，编辑于2022年，星期一定理1.3.2多重集合 的全排列数为：机动 目录 上页 下页 返回 结束 例2：(0,0)(m,n)从(0,0)点沿水平和垂直道路可以走到(m,n)点，例3：将6个蓝球，5个红球，4个白球，3个黄球排成一行，要求黄球不挨着，问有多少种排列方式？问有多少种走法？第14页，共26页，编辑于2022年，星期一定理1.3.3多重集合 的r组合机动 目录 上页 下页 返回 结束 例4：从M=1,2,n中能够取出多少个长为r的递增序列使得定理1.3.4多重集合 要求至少出现一次的r组合数
7、为第15页，共26页，编辑于2022年，星期一定义1.3.1 设集合 是一个全序集，那么由X 中的n个字母构成的字符串 只要 就称其为X上长度为 n的增字。例如例如若M=a,b,c,d,且有顺序abcd,则acc是一个增字.机动 目录 上页 下页 返回 结束 定理1.3.5设集合 是一全序集，则X上长度为n的增字共有第16页，共26页，编辑于2022年，星期一1.4 1.4 二项式系数二项式系数机动 目录 上页 下页 返回 结束 定理1.4.1(二项式定理二项式定理)设n为一正整数，则对任意的x和y，有第17页，共26页，编辑于2022年，星期一机动 目录 上页 下页 返回 结束 定理1.4.
8、2对一切实数和x(|x|1),有当=-n时：第18页，共26页，编辑于2022年，星期一机动 目录 上页 下页 返回 结束 当=1/2时：第19页，共26页，编辑于2022年，星期一机动 目录 上页 下页 返回 结束 二项式系数的基本性质：二项式系数的基本性质：当n,r为非负整数，且n r时：（1）对称关系：（2）递推关系：第20页，共26页，编辑于2022年，星期一（3）单峰性：当n为偶数时，有当n为奇数时，有机动 目录 上页 下页 返回 结束 第21页，共26页，编辑于2022年，星期一机动 目录 上页 下页 返回 结束 组合恒等式：组合恒等式：等式1：等式2：等式3：第22页，共26页，
9、编辑于2022年，星期一机动 目录 上页 下页 返回 结束 等式4：等式5：等式6：第23页，共26页，编辑于2022年，星期一机动 目录 上页 下页 返回 结束 定理1.4.3(多项式定理多项式定理)设n为一正整数，则其中：多项式系数求和号是对所有满足的非负整数序列求和。第24页，共26页，编辑于2022年，星期一机动 目录 上页 下页 返回 结束 例1：展开问的系数是多少？例2：展开问的系数是多少？第25页，共26页，编辑于2022年，星期一机动 目录 上页 下页 返回 结束 多项式系数的基本性质：多项式系数的基本性质：1.若端求和号中所包含的项数是方程：的非负整数解的数目，2.在多项式定理中，令则有的n 排列数第26页，共26页，编辑于2022年，星期一