组合数学生成函数省公共课一等奖全国赛课获奖课件.pptx

三、排列型 分配问题生成函数一、生成函数性质二、组合型 分配问题生成函数四、正整数分拆第四章第四章 生成函数生成函数第1页中心思想：对于一个有限或无限数列用幂级数使之成为一个整体，然后经过研究幂级数机动 目录 上页 下页 返回 结束 导出数列结构和性质。我们称为序列生成函数，并记为第2页引例:投掷一次骰子，出现点数1,2,6概率相同，问连续投掷两次，出现点数之各为10概率是多少？机动 目录 上页 下页 返回 结束 问连续投掷10次，出现点数之各为30概率是多少？第3页4.1 4.1 生成函数性质生成函数性质生成函数与数列之间是一一对应，所以，若两个生成函数之间存在某种关系，那么对应两个数列之间也 必定存在一定关系；机动 目录 上页 下页 返回 结束 反之亦然。设数列生成函数为设数列生成函数为则生成函数有以下一些性质：第4页性质1.若则性质2.机动 目录 上页 下页 返回 结束 若则性质3.若则性质4.若则第5页性质5.若则性质6.机动 目录 上页 下页 返回 结束 若则性质7.若则性质8.若则第6页常见数列生成函数：机动 目录 上页 下页 返回 结束 第7页例1：已知生成函数为求机动 目录 上页 下页 返回 结束 例2.计算级数和。第8页4.2 4.2 组合型分配问题生成函数组合型分配问题生成函数机动 目录 上页 下页 返回 结束(1)求k 组合数。(2)求k 组合数。(3)求10 组合数。生成函数：(1)(2)(3)第9页定理4.2.1 设从n元集合中取k个元素机动 目录 上页 下页 返回 结束 组合数若限定元素出现次数集合为则该组合数序列生成函数为例3.从中取出n个字母，要求a个数为偶数，问有多少种取法？(假设n是偶数)第10页定理4.2.2 把k个相同球放入n个不一样盒子机动 目录 上页 下页 返回 结束 中，限定盒子容量集合为则其分配方案数生成函数为例4.求不定方程满足整数解个数。第11页4.3 4.3 排列型分配问题指数型生成函数排列型分配问题指数型生成函数机动 目录 上页 下页 返回 结束 定义：数列指数型生成函数为定理4.3.1 从多重集合排列中，若限定元素出现次数集合为则排列数指数型生成函数为k第12页机动 目录 上页 下页 返回 结束 尤其地：尤其地：数列1,1,指数型生成函数含有与指数函数相同性质：第13页例5：多重集合k排列序列指数型生成函数为机动 目录 上页 下页 返回 结束 从而例6.由数字0,1,2,3组成长为k序列中，要求含有偶数个0，问这么序列有多少个？第14页机动 目录 上页 下页 返回 结束 例7.由数字1,2,3,4能组成多少个五位数？要求这些五位数中1出现2次或3次，2最多出现1次，4出现偶数次。例8.求k排列中每个最少一次排列数指数型生成函数。第15页定理4.3.2 把k个不一样球放入n个不一样盒子机动 目录 上页 下页 返回 结束 中，限定盒子容量集合为则其分配方案数生成函数为例9.用红、白、蓝3种颜色给1n棋盘着色，要求白色方格数是偶数，问有多少种着色方案？第16页4.4 4.4 正整数分拆正整数分拆机动 目录 上页 下页 返回 结束 定义4.4.1 正整数n一个k分拆是把n表示成k个正整数和一个表示法，其中叫做该分拆分部量。有序分拆无序分拆比如：4有三个有序3分拆，但只有一个无序3分拆。定理4.4.1 正整数n有序k分拆个数为第17页机动 目录 上页 下页 返回 结束 定理4.4.2(1)正整数n有序k分拆，要求第i个分部量大于等于p,其个数为：(2)正整数2n有序k分拆，各分部量都是正偶数有序分拆个数为(3)正整数n有序k分拆，若n与k同为奇数或同为偶数，则n各分部量都是奇数有序分拆数为第18页记号：用B(n,k)表示n无序k分拆个数，用B(n)表示n全部分拆个数，则显然有定理4.4.3例10：机动 目录 上页 下页 返回 结束 第19页机动 目录 上页 下页 返回 结束 定义：分拆Ferrers图共轭Ferrers图自共轭Ferrers图定理4.4.4n k 分拆个数等于n 最大分部量为k 分拆数。定理4.4.5 n 自共轭分拆个数等于n 各分部量都是奇数且两两不等分拆个数。第20页机动 目录 上页 下页 返回 结束 定理4.4.6 n 分部量两两不等分拆个数等于n 各分部量都是奇数分拆个数。例11n 最小分部量为1k 分拆数等于n-1k-1分拆数。第21页机动 目录 上页 下页 返回 结束 记号：用B(n)表示n全部没有序分拆数用Br(n)表示各分部量不超出r 无序分拆数用BH(n)表示n各分部量都属于集合H无序分拆数定理4.4.7第22页推论4.4.1n r 分拆数生成函数为推论4.4.2 n 分部量两两不等分拆个数等于n 各分部量都是奇数分拆个数。机动 目录 上页 下页 返回 结束 第23页补充例题:设多重集合an 表示集合S 满足以下条件n 组合数，机动 目录 上页 下页 返回 结束 分别求数列an生成函数：第24页