组合数学基本计数问题公开课一等奖优质课大赛微课获奖课件.pptx

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