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

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