组合数学第四章生成函数2课件

三、排列型分配问题的生成函数一、生成函数的性质二、组合型分配问题的生成函数四、正整数的分拆第四章生成函数三、排列型分配问题的生成函数一、生成函数的性质二、组合型1中心思想：对于一个有限或无限数列用幂级数使之成为一个整体，然后通过研究幂级数机动目录上页下页返回结束导出数列的构造和性质。我们称为序列的生成函数，并记为中心思想：对于一个有限或无限数列用幂级数使之成为一个整体，然2引例:投掷一次骰子，出现点数1,2,…,6的概率相同，问连续投掷两次，出现的点数之各为10的概率是多少？机动目录上页下页返回结束问连续投掷10次，出现的点数之各为30的概率是多少？引例:投掷一次骰子，出现点数1,2,…,6的概率相同，问连34.1生成函数的性质生成函数与数列之间是一一对应的，因此，若两个生成函数之间存在某种关系，那么相应的两个数列之间也必然存在一定的关系；机动目录上页下页返回结束反之亦然。设数列的生成函数为设数列的生成函数为则生成函数有如下的一些性质：4.1生成函数的性质生成函数与数列之间是一一对应的，因此，4性质1.若则性质2.机动目录上页下页返回结束若则性质3.若则性质4.若则性质1.若则性质2.机动目录上页下页5性质5.若则性质6.机动目录上页下页返回结束若则性质7.若则性质8.若则性质5.若则性质6.机动目录上页下页6常见数列的生成函数：机动目录上页下页返回结束常见数列的生成函数：机动目录上页下页7例1：已知的生成函数为求机动目录上页下页返回结束例2.计算级数的和。例1：已知的生成函数为求机动目录上页下页84.2组合型分配问题的生成函数机动目录上页下页返回结束(1)求的k组合数。(2)求的k组合数。(3)求的10

组合数。生成函数：(1)(2)(3)4.2组合型分配问题的生成函数机动目录上页9定理4.2.1设从n元集合中取k个元素机动目录上页下页返回结束的组合数若限定元素出现的次数集合为则该组合数序列的生成函数为例3.从中取出n个字母，要求a的个数为偶数，问有多少种取法？(假设n是偶数)定理4.2.1设从n元集合中取k个元素机动目录上10定理4.2.2把k个相同的球放入n个不同的盒子机动目录上页下页返回结束中，限定盒子的容量集合为则其分配方案数的生成函数为例4.求不定方程满足的整数解的个数。定理4.2.2把k个相同的球放入n个不同的盒子机动目录114.3排列型分配问题的指数型生成函数机动目录上页下页返回结束定义：数列的指数型生成函数为定理4.3.1从多重集合排列中，若限定元素出现的次数集合为则排列数的指数型生成函数为的k4.3排列型分配问题的指数型生成函数机动目录上12机动目录上页下页返回结束特别地：数列{1,1,…}的指数型生成函数具有与指数函数相似的性质：机动目录上页下页返回结束特别13例5：多重集合的k排列序列的指数型生成函数为机动目录上页下页返回结束从而例6.由数字0,1,2,3组成的长为k的序列中，要求含有偶数个0，问这样的序列有多少个？例5：多重集合的k排列序列的指数型生成函数为机动目录14机动目录上页下页返回结束例7.由数字1,2,3,4能组成多少个五位数？要求这些五位数中1出现2次或3次，2最多出现1次，4出现偶数次。例8.求的k排列中每个至少一次的排列数的指数型生成函数。机动目录上页下页返回结束例715定理4.3.2把k个不同的球放入n个不同的盒子机动目录上页下页返回结束中，限定盒子的容量集合为则其分配方案数的生成函数为例9.用红、白、蓝3种颜色给1×n棋盘着色，要求白色方格数是偶数，问有多少种着色方案？定理4.3.2把k个不同的球放入n个不同的盒子机动目录164.4正整数的分拆机动目录上页下页返回结束定义4.4.1正整数n的一个k分拆是把n表示成k个正整数的和的一种表示法，其中叫做该分拆的分部量。有序分拆无序分拆例如：4有三个有序3分拆，但只有一个无序3分拆。定理4.4.1正整数n的有序k分拆的个数为4.4正整数的分拆机动目录上页下页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：机动目录上页下页返回结束记号：用B(n,k)表示n的无序k分拆的个数，用B(n)表示19机动目录上页下页返回结束定义：分拆的Ferrers图共轭的Ferrers图自共轭的Ferrers图定理4.4.4n的k分拆的个数等于n的最大分部量为k的分拆数。定理4.4.5n的自共轭分拆的个数等于n的各分部量都是奇数且两两不等的分拆的个数。机动目录上页下页返回结束定义20机动目录上页下页返回结束定理4.4.6n的分部量两两不等的分拆的个数等于n的各分部量都是奇数的分拆的个数。例11n的最小分部量为1的k分拆数等于n-1的k-1分拆数。机动目录上页下页返回结束定理21机动目录上页下页返回结束记号：用B(n)表示n的所有无序分拆数用Br(n)表示各分部量不超过r的无序分拆数用BH(n)表示n的各分部量都属于集合H的无序分拆数定理4.4.7机动目录上页下页返回结束记号22推论4.4.1n的r分拆数的生成函数为推论4.4.2n的分部量两两不等的分拆的个数等于n的各分部量都是奇数的分拆的个数。机动目录上页下页返回结束推论4.4.1n的r分拆数的生成函数为推论4.4.2n23补充例题:设多重集合an

表示集合S满足下列条件的n组合数，机动目录上页下页返回结束分别求数列｛an｝的生成函数：补充例题:设多重集合an表示集合S满足下列条件的n组合24三、排列型分配问题的生成函数一、生成函数的性质二、组合型分配问题的生成函数四、正整数的分拆第四章生成函数三、排列型分配问题的生成函数一、生成函数的性质二、组合型25中心思想：对于一个有限或无限数列用幂级数使之成为一个整体，然后通过研究幂级数机动目录上页下页返回结束导出数列的构造和性质。我们称为序列的生成函数，并记为中心思想：对于一个有限或无限数列用幂级数使之成为一个整体，然26引例:投掷一次骰子，出现点数1,2,…,6的概率相同，问连续投掷两次，出现的点数之各为10的概率是多少？机动目录上页下页返回结束问连续投掷10次，出现的点数之各为30的概率是多少？引例:投掷一次骰子，出现点数1,2,…,6的概率相同，问连274.1生成函数的性质生成函数与数列之间是一一对应的，因此，若两个生成函数之间存在某种关系，那么相应的两个数列之间也必然存在一定的关系；机动目录上页下页返回结束反之亦然。设数列的生成函数为设数列的生成函数为则生成函数有如下的一些性质：4.1生成函数的性质生成函数与数列之间是一一对应的，因此，28性质1.若则性质2.机动目录上页下页返回结束若则性质3.若则性质4.若则性质1.若则性质2.机动目录上页下页29性质5.若则性质6.机动目录上页下页返回结束若则性质7.若则性质8.若则性质5.若则性质6.机动目录上页下页30常见数列的生成函数：机动目录上页下页返回结束常见数列的生成函数：机动目录上页下页31例1：已知的生成函数为求机动目录上页下页返回结束例2.计算级数的和。例1：已知的生成函数为求机动目录上页下页324.2组合型分配问题的生成函数机动目录上页下页返回结束(1)求的k组合数。(2)求的k组合数。(3)求的10

组合数。生成函数：(1)(2)(3)4.2组合型分配问题的生成函数机动目录上页33定理4.2.1设从n元集合中取k个元素机动目录上页下页返回结束的组合数若限定元素出现的次数集合为则该组合数序列的生成函数为例3.从中取出n个字母，要求a的个数为偶数，问有多少种取法？(假设n是偶数)定理4.2.1设从n元集合中取k个元素机动目录上34定理4.2.2把k个相同的球放入n个不同的盒子机动目录上页下页返回结束中，限定盒子的容量集合为则其分配方案数的生成函数为例4.求不定方程满足的整数解的个数。定理4.2.2把k个相同的球放入n个不同的盒子机动目录354.3排列型分配问题的指数型生成函数机动目录上页下页返回结束定义：数列的指数型生成函数为定理4.3.1从多重集合排列中，若限定元素出现的次数集合为则排列数的指数型生成函数为的k4.3排列型分配问题的指数型生成函数机动目录上36机动目录上页下页返回结束特别地：数列{1,1,…}的指数型生成函数具有与指数函数相似的性质：机动目录上页下页返回结束特别37例5：多重集合的k排列序列的指数型生成函数为机动目录上页下页返回结束从而例6.由数字0,1,2,3组成的长为k的序列中，要求含有偶数个0，问这样的序列有多少个？例5：多重集合的k排列序列的指数型生成函数为机动目录38机动目录上页下页返回结束例7.由数字1,2,3,4能组成多少个五位数？要求这些五位数中1出现2次或3次，2最多出现1次，4出现偶数次。例8.求的k排列中每个至少一次的排列数的指数型生成函数。机动目录上页下页返回结束例739定理4.3.2把k个不同的球放入n个不同的盒子机动目录上页下页返回结束中，限定盒子的容量集合为则其分配方案数的生成函数为例9.用红、白、蓝3种颜色给1×n棋盘着色，要求白色方格数是偶数，问有多少种着色方案？定理4.3.2把k个不同的球放入n个不同的盒子机动目录404.4正整数的分拆机动目录上页下页返回结束定义4.4.1正整数n的一个k分拆是把n表示成k个正整数的和的一种表示法，其中叫做该分拆的分部量。有序分拆无序分拆例如：4有三个有序3分拆，但只有一个无序3分拆。定理4.4.1正整数n的有序k分拆的个数为4.4正整数的分拆机动目录上页下页41机动目录上页下页返回结束定理4.4.2(1)正整数n的有序k分拆，要求第i个分部量大于等于p,其个数为：(2)正整数2n的有序k分拆，各分部量都是正偶数的有序分拆个数为(3)正整数n的有序k分拆，若n与k同为奇数或同为偶数，则n的各分部量都是奇数的有序分拆数为机动目录上页下页返回结束定理42记号：用B(n,k)表示n的无序k分拆的个数，用B(n)表示n的所有分拆的个数，则显然有定理4.4.3例10：机动目录上页下页返回结束记号：用B(n,k)表示n的无序k分拆的个数，用B(n)表示43机动目录上页下页返回结束定义：分拆的Ferrers图共轭的Ferrers图自共轭的Ferrers图定理4.4.4n的k分拆