组合数学基本计数问题省公共课一等奖全国赛课获奖课件.pptx

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