组合数学第一章基本计数问题

组合数学第一章基本计数问题第一页，共二十六页，2022年，8月28日一、基本计数问题1.3多重集合的排列与组合1.1加法原则与乘法原则1.2排列与组合1.4二项式系数1.5集合的分划与第二类Stirling数1.6正整数的分拆1.7分配问题第二页，共二十六页，2022年，8月28日1.1加法原则与乘法原则加法原则:设事件A有m种选取方式,事件B有n种选取方式,则选A或B共有m+n种方式.设A,B为有限集，则设n个有限集合满足则机动目录上页下页返回结束第三页，共二十六页，2022年，8月28日例1：在所有六位二进制数中，至少有连续4位是1的有多少个？机动目录上页下页返回结束第四页，共二十六页，2022年，8月28日乘法原则:设事件A有m种选取方式,事件B有n种选取方式,则选取A以后再选取B共有m·n种方式.设A,B为有限集，则设n个有限集合则则机动目录上页下页返回结束第五页，共二十六页，2022年，8月28日例2：从5位先生、6位女士、2位男孩和4位女孩中选取1位先生、1位女士、1位男孩和1位女孩，有多少种方式？从中选取一个人的方式有多少种？例3：从1000到9999之间有多少个各位数字不同的奇数？机动目录上页下页返回结束第六页，共二十六页，2022年，8月28日1.2排列与组合

n元集合S的一个r排列是指从S中选出r个元素,然后

将其按次序排列。

记为P(n,r)。

当r=n时，称为全排列。设n，r为正整数，则机动目录上页下页返回结束第七页，共二十六页，2022年，8月28日例1：将a,b,c,d,e,f进行排列，问：（1）使得字母b正好在字母e的左邻的排列有多少种？（2）使得字母b在字母e的左边的排列有多少种？例2：从{1,2,…,9}中选出不同的7个数字组成七位数，要求5与6不相邻，问有多少种方法？机动目录上页下页返回结束第八页，共二十六页，2022年，8月28日n元集合的r圆排列数为：例如：集合S={1,2,3,4}有6个4圆排列。例3：10个男生和5个女生聚餐，围坐在圆桌旁，任意两个女生不相邻的坐法有多少种？机动目录上页下页返回结束第九页，共二十六页，2022年，8月28日

n元集合S的一个r组合是指从S中选出r个元素的一种无序选择。

其组合数记为则则机动目录上页下页返回结束第十页，共二十六页，2022年，8月28日例4：系里欲将6名保送研究生推荐给3个单位，每个单位2名，问有多少种方案？例5：在一个凸n(n>3)边形C的内部，如果没有三条对角线共点，求其全部对角线在C内部的交点的个数。对任意正整数n，有机动目录上页下页返回结束第十一页，共二十六页，2022年，8月28日例6：单射函数的个数等于P(m,n)，其中，例7：求至少出现一个6且能被3整除的五位数的个数。例8：某车站有6个入口，每个入口每次只能进一个人，问9人小组共有多少种进站方案？机动目录上页下页返回结束第十二页，共二十六页，2022年，8月28日1.3多重集合的排列与组合机动目录上页下页返回结束多重集合表示为：其中为M中所有的互不相同的元素，M中有是正整数，也可以是∞。多重集合的r排列例1：用26个英文字母可以构造出多少个包含4个元音字母、长度为8的字符串。第十三页，共二十六页，2022年，8月28日多重集合的全排列数为：机动目录上页下页返回结束例2：(0,0)(m,n)从(0,0)点沿水平和垂直道路可以走到(m,n)点，例3：将6个蓝球，5个红球，4个白球，3个黄球排成一行，要求黄球不挨着，问有多少种排列方式？问有多少种走法？第十四页，共二十六页，2022年，8月28日多重集合的r组合机动目录上页下页返回结束例4：从M={1,2,…,n}中能够取出多少个长为r的递增序列使得多重集合要求至少出现一次的r组合数为第十五页，共二十六页，2022年，8月28日设集合是一个全序集，那么由X中的n个字母构成的字符串只要就称其为X上长度为n的增字。例如若M={a,b,c,d},且有顺序a<b<c<d,则acc是一个增字.机动目录上页下页返回结束设集合是一全序集，则X上长度为n的增字共有第十六页，共二十六页，2022年，8月28日1.4二项式系数机动目录上页下页返回结束(二项式定理)设n为一正整数，则对任意的x和y，有第十七页，共二十六页，2022年，8月28日机动目录上页下页返回结束对一切实数α和x(|x|<1),有当α=-n时：第十八页，共二十六页，2022年，8月28日机动目录上页下页返回结束当α=1/2时：第十九页，共二十六页，2022年，8月28日机动目录上页下页返回结束二项式系数的基本性质：当n,r为非负整数，且n≥

r时：（1）对称关系：（2）递推关系：第二十页，共二十六页，2022年，8月28日（3）单峰性：当n为偶数时，有当n为奇数时，有机动目录上页下页返回结束第二十一页，共二十六页，2022年，8月28日机动目录上页下页返回结束组合恒等式：等式1：等式2：等式3：第二十二页，共二十六页，2022年，8月28日机动目录上页下页返回结束等式4：等式5：等式6：第二十三页，共二十六页，2022年，8月28日机动目录上页下页返回结束(多项式定理)设n为一正整数，则其中：多项式系数求和号是对所有满足的非负整数序列求和。第二十四页，共二十六页，2022年，8月28日机动目录上页下页返回结束例1：展开问的系数是多少