第4章 组合数学2.ppt

§4.3 母函数 母函数又称发生函数或生成函数，是组合论中求解计数问题的重要工具之一。如有限制条件的组合或排列个数，解递推关系等等。 母函数的类型较多，在组合论常用的是两种： 1、普通母函数 2、指数母函数 一、普通母函数 例如 是1,1,…的母函数 母函数 二、指数母函数 * * § 4.1　排列、组合 一、加法规则和乘法规则 1、加法规则 也可叙述为：设事件A有m种产生方式，事件B有n种产生方式，则“事件A或事件B”有m+n种产生方式。 2、乘法规则 也可表述为：若事件A有m种产生方式，事件B有n种产生方式，则“事件A与事件B”有mn种产生方式。 例1 求比10000小的正整数中含有数字1的数的个数。 二、排列与组合 按照元素的排列方式，排列分：线排列、圆排列和重排列三类。 1、线排列 例2 将具有9个字母的单词FRAGMENTS进行排列，要求字母A总是紧跟在字母R的右边，问有多少种这样的排法？ 解：A紧跟在字母R的右边，可以把这样的排列看作是8个元素的集合{F，RA，G，M，E，N，T，S}的全排列。所以个数为：P(8,8)=8!=40320。 2、圆排列 例3 4男4女围圆桌交替就座有多少种方式？ 三、 组 合 按照选择元素可否重复，组合可分为非重组合和重组合。 1、非重组合 几个等式 例4 数510510能被多少个不同的奇数整除？ §4.2 鸽笼原理与容斥原理 一、 鸽笼原理 鸽巢原理是组合数学中最简单也是最基本的原理，也叫抽屉原理。即 定理 如果有n+1个物体放到n个盒子中，则至少有一个盒子中放有两个或更多的物体。 例1 367人中至少有２人的生日相同。 例2 10双手套中任取11只，其中至少有两只是完整配对的。 例3 把5个点放到边长为2的正方形中，至少存在两个点之间的距离小于等于 DeMorgan定理 二、 容 斥 原 理 设A,B为两个有限集合，易知A与B的元素的个数为 定理1 设 为有限集合，则 例4 求从1到1000的整数中不能被5,6,和8中任何一个整除的整数个数. 三、 错 排 问 题 四、有限制的排列 1、棋子多项式 例6 计算R( )与R( ). x1 x2 x3 x4 1 2 3 4 y1 y2 y3 y4 1 2 3 4 例7 四对夫妇前来参加宴会，围圆桌而坐，男女相间，夫妇不相邻，问有多少种入座方式？ * * *