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

1、三、排列型 分配问题的生成函数一、生成函数的性质二、组合型 分配问题的生成函数四、正整数的分拆第四章第四章 生成函数生成函数中心思想：对于一个有限或无限数列,210aaa用幂级数2210)(xaxaaxA使之成为一个整体，然后通过研究幂级数,)(xA机动 目录 上页 下页 返回 结束 导出数列,210aaa的构造和性质。我们称)(xA为序列,210aaa的生成函数，并记为 naG引例:投掷一次骰子，出现点数1,2,6的概率相同，问连续投掷两次，出现的点数之各为10的概率是多少？机动 目录 上页 下页 返回 结束 问连续投掷10次，出现的点数之各为30的概率是多少？4.1 4.1 生成函数的性质

2、生成函数的性质生成函数与数列之间是一一对应的，因此，若两个生成函数之间存在某种关系，那么相应的两个数列之间也 必然存在一定的关系；机动 目录 上页 下页 返回 结束 反之亦然。设数列,210aaa的生成函数为0)(kkkxaxA设数列,210bbb的生成函数为0)(kkkxbxB则生成函数有如下的一些性质：性质1.若,)()(0lkalkblkk则)()(xAxxBl性质2.机动 目录 上页 下页 返回 结束 若,lkkab则10)(1)(lkkklxaxAxxB性质3.若,0kiikab则xxAxB1)()(性质4.若,kiikab则xxxAAxB1)()1()(性质5.若,kkkab 则)

3、()(xAxxB性质6.机动 目录 上页 下页 返回 结束 若,1kabkk则xdttAxxB0)(1)(性质7.若,kkkbac则)()()(xBxAxc性质8.若,0110bababackkkk则)()()(0 xBxAxcxckkk常见数列的生成函数：xG111)1(机动 目录 上页 下页 返回 结束 xaaGk11)2(21)3(xxkG312)1()4(xxkkG 321)1()5(xxxkGxekG!1)6()1()7(xkG111)8(nxkknG4162)(1()9(xxkkkG例1：已知 na的生成函数为,21632)(2xxxxA求.na机动 目录 上页 下页 返回 结束

4、例2.计算级数22221n的和。4.2 4.2 组合型分配问题的生成函数组合型分配问题的生成函数机动 目录 上页 下页 返回 结束(1)求naaa,21的k 组合数。(2)求naaa,21的k 组合数。(3)求cba5,4,3的10 组合数。生成函数：(1)nx)1(2)组nxxxxxx)1()1)(1(222(3)1)(1)(1(543243232xxxxxxxxxxxx定理4.2.1 设从n元集合naaaS,21中取k个元素机动 目录 上页 下页 返回 结束 的组合数,kb若限定元素ia出现的次数集合为niMi1则该组合数序列的生成函数为 niMmmix1例3.从cnbnan,中取出n个字

5、母，要求a的个数为偶数，问有多少种取法？(假设n是偶数)定理4.2.2 把k个相同的球放入n个不同的盒子机动 目录 上页 下页 返回 结束 naa,1中，限定盒子ia的容量集合为,)1(niMi则其分配方案数的生成函数为 niMmmix1例4.求不定方程2054321xxxxx满足0,6,4,2,354321xxxxx的整数解的个数。4.3 4.3 排列型分配问题的指数型生成函数排列型分配问题的指数型生成函数机动 目录 上页 下页 返回 结束 定义：数列,210aaa的指数型生成函数为0!kkkkxa定理4.3.1 从多重集合naaaM,21排列中，若限定元素ia出现的次数集合为niMi1则排

6、列数的指数型生成函数为 niMmmimx1!的k机动 目录 上页 下页 返回 结束 特别地：特别地：数列1,1,的指数型生成函数0!)(nnnxxe具有与指数函数相似的性质：)()()(yxeyexe,1)0()()(exexe)(1)(xexe例5：多重集合aaaM,21的k排列序列 kb的指数型生成函数为nixx12!2!11机动 目录 上页 下页 返回 结束)(xen)(nxe0!kkkkxn从而kknb 例6.由数字0,1,2,3组成的长为k的序列中，要求含有偶数个0，问这样的序列有多少个？机动 目录 上页 下页 返回 结束 例7.由数字1,2,3,4能组成多少个五位数？要求这些五位数

7、中1出现2次或3次，2最多出现1次，4出现偶数次。例8.求aaaM,21的k排列中每个ia至少一次的排列数kP的指数型生成函数。定理4.3.2 把k个不同的球放入n个不同的盒子机动 目录 上页 下页 返回 结束 naa,1中，限定盒子ia的容量集合为,)1(niMi则其分配方案数的生成函数为 niMmmimx1!例9.用红、白、蓝3种颜色给1n棋盘着色，要求白色方格数是偶数，问有多少种着色方案？4.4 4.4 正整数的分拆正整数的分拆机动 目录 上页 下页 返回 结束 定义4.4.1 正整数n的一个k分拆是把n表示成k个正整数的和)1(21knnnnk的一种表示法，其中)1(0kiniin叫做

8、该分拆的分部量。有序分拆无序分拆例如：4有三个有序3分拆，但只有一个无序3分拆。定理4.4.1 正整数n的有序k分拆的个数为.11kn机动 目录 上页 下页 返回 结束 定理4.4.2(1)正整数n的有序k分拆，要求第i个分部量大于等于p,其个数为：;111kpknkii(2)正整数2n的有序k分拆，各分部量都是正偶数的有序分拆个数为;11kn(3)正整数n的有序k分拆，若n与k同为奇数或同为偶数，则n的各分部量都是奇数的有序分拆数为;112kkn记号：用B(n,k)表示n的无序k分拆的个数，用B(n)表示n的所有分拆的个数，则显然有);(0),()1(nkknB.),()()2(1nkknB

9、nB定理4.4.3),()2,()1,(),(knBnBnBkknB1),(,1)1,(nnBnB且例10：?)2,(nB机动 目录 上页 下页 返回 结束 机动 目录 上页 下页 返回 结束 定义：分拆的Ferrers图共轭的Ferrers图自共轭的Ferrers图定理4.4.4n 的k 分拆的个数等于n 的最大分部量为k 的分拆数。定理4.4.5 n 的自共轭分拆的个数等于n 的各分部量都是奇数且两两不等的分拆的个数。机动 目录 上页 下页 返回 结束 定理4.4.6 n 的分部量两两不等的分拆的个数等于n 的各分部量都是奇数的分拆的个数。例11n 的最小分部量为1的k 分拆数等于n-1的

10、k-1分拆数。机动 目录 上页 下页 返回 结束 记号：用B(n)表示n的所有无序分拆数用Br(n)表示各分部量不超过r 的无序分拆数用BH(n)表示n的各分部量都属于集合H的无序分拆数定理4.4.7)1()1)(1(1)()1(20rnnrxxxxnBHjjnnHxxnB)1(1)()2(010)1(1)()3(jjnnxxnB推论4.4.1n 的r 分拆数的生成函数为)1()1)(1(2rrxxxx推论4.4.2 n 的分部量两两不等的分拆的个数等于n 的各分部量都是奇数的分拆的个数。机动 目录 上页 下页 返回 结束 补充例题:设多重集合,4321eeeeSan 表示集合S 满足下列条件的n 组合数，机动 目录 上页 下页 返回 结束 分别求数列an的生成函数：出现奇数次每个ie)1(的倍数次出现每个3)2(ie次至多出现不出现1)3(21e，e次或出现次或出现54211,3,1)4(21，e，e次至少出现每个10)5(ie