组合数学生成函数.ppt

* * 三、排列型 分配问题的生成函数 一、生成函数的性质 二、组合型 分配问题的生成函数 四、正整数的分拆 第四章 生成函数 中心思想： 对于一个有限或无限数列 用幂级数 使之成为一个整体， 然后通过研究幂级数 机动 目录 上页 下页 返回 结束 导出数列 的构造和性质。 我们称 为序列 的生成 函数， 并记为 引例: 投掷一次骰子，出现点数1,2, …,6的概率相同， 问连续投掷两次，出现的点数之各为10的概率是多少？ 机动 目录 上页 下页 返回 结束 问连续投掷10次，出现的点数之各为30的概率是多少？ 4.1 生成函数的性质 生成函数与数列之间是一一对应的， 因此，若两个生 成函数之间存在某种关系， 那么相应的两个数列之间也 必然存在一定的关系； 机动 目录 上页 下页 返回 结束 反之亦然。 设数列 的生成函数为 设数列 的生成函数为 则生成函数有如下的一些性质： 性质1. 若 则 性质2. 机动 目录 上页 下页 返回 结束 若 则 性质3. 若 则 性质4. 若 则 性质5. 若 则 性质6. 机动 目录 上页 下页 返回 结束 若 则 性质7. 若 则 性质8. 若 则 常见数列的生成函数： 机动 目录 上页 下页 返回 结束 例1： 已知 的生成函数为 求 机动 目录 上页 下页 返回 结束 例2. 计算级数 的和。 4.2 组合型分配问题的生成函数 机动 目录 上页 下页 返回 结束 (1) 求 的k 组合数。 (2) 求 的k 组合数。 (3) 求 的10 组合数。 生成函数： (1) (2) (3) 定理4.2.1 设从n元集合 中取k个元素 机动 目录 上页 下页 返回 结束 的组合数 若限定元素 出现的次数集合为 则该组合数序列的生成函数为 例3. 从 中取出n个字母， 要求a的个数为 偶数， 问有多少种取法？ (假设n是偶数) 定理4.2.2 把k个相同的球放入n个不同的盒子 机动 目录 上页 下页 返回 结束 中， 限定盒子 的容量集合为 则其分配 方案数的生成函数为 例4. 求不定方程 满足 的整数解的个数。 4.3 排列型分配问题的指数型生成函数 机动 目录 上页 下页 返回 结束 定义： 数列 的指数型生成函数为 定理4.3.1 从多重集合 排列中， 若限定元素 出现的次数集合为 则排列数的指数型生成函数为 的k 机动 目录 上页 下页 返回 结束 特别地： 数列{1,1,…}的指数型生成函数 具有与指数函数相似的性质： 例5： 多重集合 的k排列序列 的指数型生成函数为 机动 目录 上页 下页 返回 结束 从而 例6. 由数字0,1,2,3组成的长为k的序列中， 要求含有偶数 个0， 问这样的序列有多少个？ 机动 目录 上页 下页 返回 结束 例7. 由数字1,2,3,4能组成多少个五位数？ 要求这些五位 数中1出现2次或3次， 2最多出现1次， 4出现偶数次。 例8. 求 的k排列中每个 至少 一次的排列数 的指数型生成函数。 定理4.3.2 把k个不同的球放入n个不同的盒子 机动 目录 上页 下页 返回 结束 中， 限定盒子 的容量集合为 则其分配 方案数的生成函数为 例9. 用红、白、蓝3种颜色给1×n棋盘着色， 要求白色 方格数是偶数， 问有多少种着色方案？ 4.4 正整数的分拆 机动 目录 上页 下页 返回 结束 定义4.4.1 正整数n的一个k分拆 是把n表示成k个正 整数的和 的一种表示法， 其中 叫做该分拆的分部量。 有序分拆 无序分拆 例如：4有三个有序3分拆， 但只有一个无序3分拆。 定理4.4.1 正整数n的有序k分拆的个数为 *