当前位置：文档之家 › 组合数学课件(第七章 生成函数)

组合数学课件(第七章 生成函数)

  • 格式：ppt
  • 大小：989.00 KB
  • 文档页数：85

下载文档原格式

  / 85

合集下载

组合数学课件(第七章 生成函数)

组合数学课件(第七章 生成函数)
• • • • • 7.1生成函数的定义和性质 7.2多重集的r-组合数 7.3正整数的划分 7.4指数生成函数与多重集的排列问题 7.5Catalan数和Stiring
§7.1 生成函数概念
§4.1 生成函数的基本概念
4.1.1 生成函数
定义 4.1
给定一无穷序列(a0,a1,…an,…)(简记为{an})，称函
e
1! 2! 1 4 7 ... (3n 1) n x n! n0 4 7 ... 3n 1 3 3 3n x n 1 3 n! n 1 4 4 1 ... 4 n 1 3 3 3 1 ( 3 x )n n! n 1 4 1 3 ( 3 x )n n n 1
§7.1 生成函数的基本概念 7.1.2 指数生成函数
定义 7.2 给定一无穷序列(a0,a1,…an,…)（简记为{an}），称函 xi 数 f e ( x ) ai 为序列{an}的指数生成函数。 i! i 0 注： fe(x)也是形式幂函数。 经常可结合以下公式运算： 2 n x x x e x 1 2 ... n ... 1! 2! n! n x x2 x n x e 1 ... ( 1) ... 1! 2! n! x x3 x 2 n 1 e x e x sin x ... ... 1! 3! (2n 1)! 2
********************** 课程总结
第7章 生成函数
本章重点介绍生成函数（生成函数、指数生成函 数）的基本概念及其在排列组合中的应用 ： 生成函数的基本概念 生成函数的基本运算 生成函数在排列、组合中的应用 整数拆分 生成函数在组合恒等式中的应用

组合数学课件(第七章 生成函数)

组合数学课件(第七章 生成函数)



§ 7.1 生成函数例6 § 7.1指数 生成函数的基本概念
7.1.2 指数生成函数
例 题
例6、求序列(p(0,0), p(2,1), p(4,2),…, p(2n,n),…)的指数生成函数fe(x)。
解：由定义7.2及公式P(n,r)=r!C(n,r)，以及例3的结论，有 x x2 xn f e ( x ) p(0, 0) p(2,1) p(4, 2) ... p(2n, n) ... 1! 2! n! 0 2 x 4 x 2 ... 2n x n ... 0 1 2 n (1 4 x )1 2


§7.1 指数生成函数例7 §7.1 生成函数的基本概念
7.1.2 指数生成函数
例 题
例7、求序列{1,α,α2,…,αn,…}的指数生成函 数fe(x)。其中α是实数。
2 n x x x fe ( x ) 1 2 ... n ... e x 1! 2! n!
组合数学课件
制作讲授：王继顺
目录（1）
目
第1章 什么是组合数学 1.1引例 1.2组合数学研究对象、内容和方法 第2章 鸽巢原理 2.1 鸽巢原理：简单形式 2.2 鸽巢原理：加强形式 2.3 Ramsey定理 2.4 鸽巢原理与Ramsey定理的应用 本章小结 习题 第3章 排列与组合 3.1 两个基本的计数原理 3.2 集合的排列与组合 3.3 多重集的排列与组合 本章小结 习题
例 题
例2、求序列(C(n-1,0), -C(n,1), C(n+1,2), …, (1)kC(n+k-1,k), … )的生成函数。
§7.1 生成函数例2
解：由定义7.1及二项式定理的推论3.10.2有

[数学]组合数学第7章[递推关系与生成函数]

[数学]组合数学第7章[递推关系与生成函数]

递推（递归）关系是计数的一个强有力 的工具，特别是在做算法分析时是必需的， 有大量的递归算法的时间特性体现出递推 关系。递推关系的求解的主要方法包括递 推、母函数、特征方程等方法。
递推关系与求解
§7.1 递推关系与递推求解
[例1]确定平面一般位置上的n个互相交叠的 圆所形成的区域数。所谓互相交叠是指每 两个圆相交在不同的两个点上。
q a1q
n k
n 1
a2 q
n2
... ak q
nk
0
q a1q
k 1
a2 q
k 2
... ak 0
即第一个结论成立。
特征方程解法
由于qi互异，qin都是递推关系的不同解，故 n n n hn c1q1 c2 q2 ... ck qk 也是递推关系的解。对任意的初始值，有 n 0， c1 c2 ... ck b0 n 1， c1q1 c2 q2 ... ck qk b1 2 2 2 n 2， c1q1 c2 q2 ... ck qk b2
特征方程解法
2. 非齐次递推关系 定义1中的bn非零时，形成的非齐次递推关 系的求解可分为几步： (1)求齐次通解； (2)求非齐次关系的一个特解； (3)通解与特解结合。 但求特解没有一般的公式，一些特殊形式 下可以进行如下尝试。
特征方程解法
(1)若bn是n的k次多项式，hn为特解，可尝试： a)hn=r（常数），若bn为d（常数） b)hn=rn+s，若bn=dn+c c)hn=rn2+sn+t，若bn=fn2+dn+c (2)若bn是指数形式，则尝试 hn=多项式dn，若bn=dn

组合数学(第7章7.6)

组合数学(第7章7.6)

其中，0m1n1, 0m2n2,…, 0mknk。
令n=m1+m2+…+mk, 则上式可写成：
n! xn m1!m2! mk ! n!
因此，7-57式中xn/n!的系数是： n! m1!m2! mk ! 上式对满足n=m1+m2+…+mk和0m1n1, 0m2n2,…, 0mknk所有整数m1,m2,…,mk求和。
作业
7.8习题 第4版：37，40，42

nk n1 2 2 x x x x g (e) ( x) (1 x ) (1 x ) 2! n1! 2! nk !
那么，每项形式为：
m1 m2 mk x x x x m1! m2! mK ! m1!m2!mk !
m1 m2 mK

x2 x4 f1 ( x) 1 ... 2! 4!
对应2的因子为：
x3 x 4 x5 f 2 ( x) ... 3! 4! 5!
对应3的因子为：
x 2 x3 x 4 f 3 ( x) 1 x 2! 3! 4!
那么序列的指数生成函数是：
g (e) ( x) f1 ( x) f 2 ( x) f3 ( x)

1 2n 2 hn n n 1
证明：（1）求递推关系。 验证n=1和n=2时，递推关系成立。 令n3, 考虑n+1条边的凸多边形区域K。 选取K的一条边称为基边，对每一种分法，基 边所在的三角形区域将K分成两个部分K1,和K2， 其中K1有k+1条边，而K2有n-k+1条边. 因此，包 含这个三角形的分法有hkhnk种。 那么，包含该基边的每一个不同三角形确定了 hkhnk种不同的分法。 n 1 共有 K2 K1 hn= hk hnk

组合数学(18)

组合数学(18)
1 j G( x) x m ( 1 x ) j 0
m
m k 1 其组合数ck k 推论2 无0≤ki≤ri, i=1, 2, …, m限制，由书中(见
为G(x)展开式中xk的系数
P44定理3.5.1) 即知：
m k 1 ck k
通项hn为： hn = n+1, 仅仅通过代数运算得到。 25
例：确定方程： e1+e2+…+ek＝n的非负奇整数 解 e1,e2,…,ek的个数hn的生成函数。
取8,9。
解:设不定方程
k
i 1
m
i
k 的解组数目为 ck ，本例
中m=4, k=20。注意到对ki(i=1,2,3,4)的限制，序 列{ck}对应的生成函数为: G(x)=(1+x2+x4)(x+x3+x5)(x6+x7)(x8+x9)
18
G(x)=(1+x2+x4)(x+x3+x5)(x6+x7)(x8+x9) = (1+x2+x4) (1+x2+x4)x(1+x)x6(1+x)x8
12
推论 3 设S={∞·e1, ∞·e2, …, ∞·em}，则S的每 个元素至少取一次的 k( 无限 ) 可重复组合数
ck(k≥m)对应序列{ck}的生成函数为： m x G( x ) ( x j )m m ( 1 x ) j 1 m 1 其组合数ck为G(x)展开式中xk的系数 。 k 1 这是由于:
中取出k个元素的组合数ck对应序列{ck}的生成

组合数学_第7章7.1_ (1)

组合数学_第7章7.1_ (1)
称该数列为斐波那契（Fibonacci）数列，这个数列 的项称为斐波那契数。
斐波那契螺旋线
设有数列f0, f1, f2,…, fn, …。如果 f0=0, f1=1, 且满足递推关系fn= fn-1+fn-2，n≥2
称该数列为斐波那契（Fibonacci）数列，这个数列 的项称为斐波那契数。
性质： (1) 斐波那契数列的部分和为
n元集合的子集数: hn=2n , n ≥0 (2) h0=5, q=3: 5, 3*5, 32*5,…, 3n*5,…
hn= 3n*5, n ≥0
主要内容
求递推式 斐波那契（Fibonacci）序列
例: 考虑1行n列棋盘。假设用红和蓝两种颜色给这
个棋盘的每一个方格色。设hn是使得没有两个着成 红色的方格相邻的着色方法数。求hn满足的递推关 系。
(2) Dn=nDn1+(1)n ，
(n=2,3,…)
数列
设 h0, h1, …, hn, …表示一个数列， 其中hn叫做数列的一般项或通项
算术数列(等差数列):
h0, h0+q, h0+2q, …, h0+nq,… 递推关系：hn= hn-1+q 一般项： hn= h0+nq 前n+1项和：sn= (n+1)h0+q(n)(n+1)/2
h2=2
h3=3 … hn-1
…
hn
… hn-2
hn=hn-1+ hn2 满足斐波那契递推关系。hn是斐波那契数。
例：确定用单牌和多米诺牌完美覆盖1×n棋盘的方法 数bn。 2×n棋盘用多米诺牌的完美覆盖与 1×n棋盘用单牌和多米诺牌的完美覆盖的一一对应

组合数学_第7章7.2-7.3_ (1)

组合数学_第7章7.2-7.3_ (1)

例：什么样的数列的生成函数是如下式子？
(1+x+x2+x3+x4+x5)(1+x+x2)(1+x+x2+x3+x4)
5
2
4
= ( ෍ ������������1)( ෍ ������������2)( ෍ ������������3)
������1=0
������2=0
������3=0
多重集合{∞∙a1, ∞∙a2,∞∙a3}的n组 合数：a1最多出现5次，a2最多 出现2次，a3最多出现4次
因此乘积中xn的系数hn是e1+e2+e3=n的非负整数解的 个数, 其中0≤ e1 ≤ 5, 0≤ e2 ≤ 2, 0 ≤ e3 ≤ 4。
注意：若n>5+2+4=11，则hn=0。
例：求装有苹果、香蕉、桔子和梨的果篮的数量 hn, 其中每个果篮中, 苹果的个数是偶数,香蕉的个数 是5的倍数, 桔子不超过4个,而且至多只有一个梨.
= σ���∞���������+⋯+������������=������=������
������������������ ������������������
… ������ ������1=0 ������������
������2=0
������������=0
ei是一个n组合
其中，xn前的系数即为 hn
得 ������������ + ������������=1， ������������ = −������, 解得 ������������ = −������， ������������ = ������.

chap7递推关系生成函数

chap7递推关系生成函数
2
-------(1) -------(2)
指数生成函数(EGF)
序列h0,h1,h2,…的指数生成函数定义为
g
(e )
( x ) h0 h1
x 1!
h2
x
2
2!
hk
x
k

k!
例. 排列数序列 P(n,0), P(n,1), …, P(n,n)的EGF是 g(e)(x) = ( 1+x )n . 对比组合数序列C(n,0), C(n,1), …, C(n,n)的GF是 g(x) = ( 1+x )n . 注: hk = 指数生成函数的k次项系数k!
除多项式外,经常用到的函数还有:
1 1 x
1 (1 x ) 1
2
1 x x
2
( 1 x )( 1 x ) 1 2 x 3 x
2
n k 1 n (1 x ) x k (1 x ) k 1 n0
第一部分小结
Fibonacci数列 线性常系数齐次递推关系的求解 线性常系数非齐次关系的求解
转移矩阵
对于线性齐次常系数递推关系, 以4阶为例 hn - a1 hn-1 - a2 hn-2 - a3 hn-3 … - a4 hn-4 = 0 我们有如下计算的hn方法,
hn a 1 hn 1 1 h 0 n2 hn 3 0 a2 0 1 0 a3 0 0 1 a 4 hn 1 a 1 0 hn 2 1 h 0 0 n3 0 hn 4 0
5b
4 r 0
x ) (
r

组合数学 第7章

组合数学 第7章
设 x e1 是(1 + x + x 2 + x3 + x 4 + x 5 )的典型项
x e2 是(1 + x + x 2 )的典型项 x e3 是(1 + x + x 2 + x3 + x 4 )的典型项 0 ≤ e1 ≤ 5 0 ≤ e1 ≤ 2 0 ≤ e1 ≤ 4
是什么样的序列的生成函数?
7.4
7 4 生 成 函 .
生成函数
如果一个函数g(x)的无穷级数是
h0 + h1 x + h2 x 2 + ... + hn x n + ...
则称函数g(x)是无穷数列 h0, h1, h2, …, hn, … 的生成函数. 研究生成函数的目标是:对于给定的无穷数列 h0, h1, h2, …, hn, … 我们期望求出该数列的生成函数的有限表示形式,从而 将一个无穷数列所包含的全部信息浓缩在一个有限的代 数函数之中.
(q ≠ 1) (q=1) q n+1 1 n n h0 i sn = ∑ h i =∑ q h 0 = q 1 i=0 i=0 (n+1) h 0
n≥
例 7 1 某 些 数 .
确定平面一般位置上的n个互相交叠的圆所形成 的区域数?
[分析]
设hn是由n个
互相交叠的圆所形成 的区域数. 分析hn与hn-1 的关系,我们发现 hn=hn-1+2(n-1) 因此 hn=n2 – n + 2 n≥ 1
c1 + c2 + c3 = 1 c1 c2 + 2c3 = 2 c + c + 4c = 0 3 1 2
解得其唯一解 c1=2, c2=-2/3 ,c3=-1/3,因此求得特定递推关 系的解

《排列组合的生成》课件

《排列组合的生成》课件
详细描述
通过具体的实例，如排队、物品的排列组合等，深入解析排列的概念，以及其在日常生活和工 作中的应用。
组合实例解析
总结词
通过实例解析组合的概念和应用
详细描述
通过具体的实例，如抽屉原理、彩票中奖概率等，深入解析组合的概念，以及 其在数学和实际生活中的应用。
排列与组合的综合实例解析
总结词
通过实例解析排列与组合的综合 应用
统计推断
排列组合在统计推断中也 有应用，例如在贝叶斯推 断和马尔科夫链蒙特卡洛 方法中。
数据分析
排列组合在数据分析中也 有应用，例如在处理离散 数据和分类数据时。
04
排列组合的数学原理
排列的数学原理
1 2
排列的定义
从n个不同元素中取出m个元素（m≤n），按照 一定的顺序排成一列，称为从n个不同元素中取 出m个元素的排列。
机器学习和数据挖掘
排列组合在计算机科学的数据结构和 算法中广泛应用，如动态规划、回溯 算法等。
排列组合在机器学习和数据挖掘中也 有应用，例如在特征选择和分类算法 中。
离散概率模型
排列组合可用于构建离散概率模型， 用于模拟和研究随机事件和系统行为 。
统计学中的应用
01
02
03
概率分布
排列组合可用于研究概率 分布，如二项分布、泊松 分布等，以及它们的性质 和计算方法。
排列与组合的联系与区别
01
联系
当m=n时，排列转化为组合，即P(n,n)=C(n,n)。
02
区别
当m<n时，排列与组合的公式不同，排列与组合 的顺序有关，而组合与顺序无关。
02
排列组合的生成方法
排列的生成方法
定义
按照一定顺序取出n个元素所组成的排列 。

组合数学(第7章7.2)

组合数学(第7章7.2)

线性齐次递推关系的定义
定义: 令h0, h1, h2,…, hn,…是一个数列, 若存 在量 a1, a2,…,ak 和 bn(ak≠0, 每个量是常数或 依赖于n的数)使得: hn=a1hn-1+a2hn-2+…+akhn-k+bn (n≥k) 则称序列满足k阶线性递推关系. 若bn=0, 称齐次的; 若a1, a2, …,ak取常数,称常 系数的.

证明： 1. hn=qn满足递推关系当且仅当
qn−a1qn−1−a2qn−2−…−akqn−k=0 即q是方程 xk−a1xk−1−a2xk−2−…−ak=0的根。 2. 设q1, q2,..., qk是方程的k个不同的根。那么， 是递推关系的不同的解，可以验证
hn=q1n, hn=q2n,…, hn=qkn hn=c1q1n+ c2q2n+…+ ckqkn
常系数线性齐次递推关系的解
定理7.2.1 令q为一个非零数,则hn=qn是常系数线性齐次递 推关系： hn=a1hn-1+a2hn-2+…+akhn-k (ak≠0, n≥k) (1) 的解, 当且仅当q是多项式方程 xk-a1xk-1- a2xk-2-…- ak=0 (2) 的一个根. 若多项式方程有k个不同的根q1, q2,…, qk,则 hn=c1q1n+ c2q2n+…+ ckqkn (3) 是下述意义下(1)的一般解: 任意给定初始值h0, h1, …,hk-1, 都 存在c1, c2,…, ck使得(3)式是满足(1)式和初始条件的唯一的 序列.
也满足递推关系（1），然后证明它是一般解。
3. 设 h0=b0, h1=b1,…, hk-1=bk-1是初始值，那么满足初 始条件的c1, c2,..., ck是下面线性方程组的解： c1+c2+...+ck=b0 c1q1+c2q2+...+ckqk=b1 方程组的系数矩阵是范德蒙矩阵，因此，方程组 存在唯一解。

组合数学(第7章7.5)

组合数学(第7章7.5)

设相应特征方程r(x)=0，其中q(x)=xkr(1/x). 若r(x)=0的根为q1, q2,…, qk, 那么 r(x)=(x−q1)(x−q2)…(x−qk) q(x)=(1−q1x)(1−q2x)…(1−qkx) 另一方面，任意给出k次多项式 q(x)=b0+b1x+…+bkxk (b0≠0) 和小于k次多项式： p(x)=d0+d1x+…+bk-1xk-1 可以用部分分式法求出幂级数展开式： p(x)/q(x)= h0+h1x+…+hnxn+… 得到d0+d1x+…+bk-1xk-1=(b0+b1x+…+bkxk)× (h0+h1x+…+hnxn+…)
g(x)=h0+h1x+h2x2 +h3x3+… +hnxn+… xg(x)= h0x+h1x2 +h2x3+… +hn-1xn+… −16x2g(x)= −16h0x2−16h1x3−…−16hn-2xn+… 20x3g(x)= 20h0x3+…+20hn-3xn+…
+)
得到： (1+x−16x2+20x3)g(x)=h0+(h1+h0)x+(h2+h1−16h0)x2+ (h3+h2−16h1+20h0)x3+…+ (hn+hn-1−16hn-2+20hn-3)xn+… 代入递推关系和初始条件得到： (1+x−16x2+20x3)g(x)=x 因此 g(x)=x/(1+x−16x2+20x3) (将g(x)表示代数分式和 表示代数分式和) 将 表示代数分式和 (1+x−16x2+20x3)=(1−2x)2(1+5x), (等价于求解多项 式方程)。则：

组合数学(第7章7.1)

组合数学(第7章7.1)

斐波那契螺旋
应用
例：确定2×n棋盘用多米诺牌完美覆盖的方 法数hn。 规定h0=1. 容易看到h1=1， h2=2， h3=3。 hn= hn−1+ hn−2 满足斐波那契递推关系。hn是 斐波那契数。
… …
应用
定理7.1.2 沿Pascal三角形左边向上对角线 定理 上的二项式系数和是Fibonacci数, 即
定理7.1.1 斐波那契数满足公式
1 1+ 5 n 1 1− 5 n fn = ( ) − ( ) 2 2 5 5
n≥0
观察递推关系： fn− fn−1−fn−2=0
(1) 设q≠0， fn=qn满足斐波那契递推关系 ⇔ q2−q−1=0 设fn=qn, 因为fn− fn−1−fn−2=qn−qn−1−qn−2= qn−2(q2−q−1)=0, 注意 q≠0， 因此fn−fn−1−fn−2=0 当且仅当q2−q−1=0.
第七章 递推关系和生 成函数
讲授内容
7.1 某些数列 本章主要讨论涉及一个整数参数的计数问 题的代数求解方法。
错位排列计数公式的递推关系
1 1 1 n 1 Dn=n! (1 − 1! − 1) n!)
递推关系 (1) Dn=(n−1)( Dn−2+Dn−1), (n=3,4,…) (2) Dn=nDn−1+(−1)n (n=2,3,…)
迭代计算得到：
f13=233
定义1：设f0=0, f1=1, 那么满足递推关系fn= fn-1+fn-2的序列叫斐波那契（Fibonacci）序列， 项称为斐波那契数。 由归纳法原理可得：Fibonacci序列的部分 和为 sn=f0+f1+…+fn= fn+2−1 证明： f0+f1+…+fn+fn+1= (fn+2−1)+fn+1 = (fn+2+fn+1)−1 = fn+3−1 斐波那契数是偶数当且仅当n被3整除。

第七章(Chapter 7)递推关系和生成函数(Recurrence Relations and Generating Functions)

第七章(Chapter 7)递推关系和生成函数(Recurrence Relations and Generating Functions)

[注]：由以上例题可以归结得到如下的一个重要 结论： 若 ar为拆分为由 n1个 a1， 2 个 a，…， m个 am 组成 n n 2 的集合中元素的和的拆分数，则序列 {ar }的生成 函数为： G (x) = (1 x a x 2 a x n a )(1 x a x 2 a x n a )
第七章（Chapter 7） 递推关系和生成函数
(Recurrence Relations and Generating Functions)
许多组合数学计数问题依赖于一个整数参数 n，这个整数参数n常常表示问题中某个基本集 （笛卡尔集）或多重集的大小、组合的大小、排 列中的位置数等等。因此一个计数问题常常不是 一个孤立的问题，而是一系列单个问题的综合。 本章中，我们将讨论涉及一个整数参数的某些计 数问题的代数求解方法。这些方法类似于上一章 所介绍的棋盘多项式方法一样，通过引入一个函 数（称为生成函数，它实质上是一个幂级数，其 各项系数对应于相应计数问题的解）结合递推关 系来求解相应的计数问题。
1
2
3
二、指数型生成函数 定义7.3.1：对于序列 a0 , a1 , a2 ,, ak , ，定义函 数： x x2 xk ak Ge (x)= a0 a1 a 2 1! 2! k! 为该序列的指数型生成函数。 例如， ⑴序列 {1,1,,1,} 的指数型生成函数为：
1 1 1 1 2 2 2 2
(1 x am x 2 am x nm am )
其中 r 和 a1，2 ，…，m 以及 n1 ，2 ，…， m 都是正 a n n a n n n 整数，1 ，2 ，…， m可以是无穷大。G (x)的幂级数 x r 项的系数即为 ar 。 展开式中

组合数学 生成函数的概念PPT资料(正式版)

组合数学 生成函数的概念PPT资料(正式版)

并约定，若某个ai＝0 (i＝0,1,2,…)，则项aixi可以略去，且x0可简记为1。
{1·a1,1·a2,4·a3,1·a4}
x1 x1 x4 x1＝x7
S＝{2·a1,1·a2,∞·a3,9·a4} (1)求{a1,a2,…,an}的r组合数
设x是一个抽象符号，an(n＝0,1,2,…)为实数列，若函数F(x)可表示成 (2)求{∞·a1,∞·a2,…,∞
x1＋x2＋…＋x9)
{2·a1,2·a3,3·a4}
x2 x0 x2 x3＝x7
{1·a1,1·a2,4·a3,1·a4}
x1 x1 x4 x1＝x7
{7·a4}
x0 x0 x0 x7＝x7
题意分配方案 F(x)右边展开式中x7项(未合并同类)
b7＝F(x)右边展开式中x7项的系数
2.1.2 重集的组合
11 n
22 n
nn n
F(x)＝(x1＋x3＋x5＋…)(x0＋x2＋x4＋…)(x2＋x3＋x4＋x5)(x0＋x1＋x2＋x3＋…)(x0＋x1＋x2＋x3＋…)
解 用xk表示k个球，圆括号表示盒子，做
试讨论S的7组合的个数b7
无穷序列1,1,1,…的生成函数为 题意分配方案 F(x)右边展开式中x7项(未合并同类)
x4＋x5)(x0＋x1＋x2＋x3＋…)(x0＋x1＋x2＋x3＋…) 盒1 盒2 盒3 盒4 盒5
球的个数 (3) (0) (2) (2) (2) x3 x0 x2 x2 x2＝x9 球的个数 (3) (2) (3) (0) (1) x3 x2 x3 x0 x1＝x9 题意分配方案 F(x)右边展开式中x9项(未合并同类) a9＝F(x)右边展开式中x9项的系数
2.1.2 重集的组合

第七章、生成函数

第七章、生成函数

中 x30 的系数。而
(x + x2 + x3 + x4 + x5 + x6 )10 = x10 (1 + x + x2 + x3 + x4 + x5 )10
=
x10
(1 +
x
+
x2
+
x3 + (1 −
x4 + x)10
x5 )10 (1 −
x)10
= x10 (1 − x6 )10 (1 − x)10
从两个括号中分别取出 xm 和 xn ，使
xm ⋅ xn = x10
即是两次投掷分别出现点数 m, n ，且 m + n = 10 。由此得出，展开式中 x10 的系数就是满足条 件的方法数。
同理，连续投掷 10 次，其和为 30 的方法数为 (x + x2 + x3 + x4 + x5 + x6 )10
组合数学讲义(内部资料，严禁商用)
第七章、生成函数
第七章、生成函数
本章目次 7.1、引论 7.2、形式幂级数 7.3 生成函数的性质 7.4 用生成函数求解递推关系
7.4.1 用生成函数求解常系数线性齐次递推关系 7.4.2 用生成函数求解常系数线性非齐次递推关系 7.5 生成函数在计数问题中的应用 7.5.1 组合数的生成函数 7.5.2 排列数的指数型生成函数 7.5.3 分拆数的生成函数 7.5.4 组合型分配问题的生成函数 7.5.5 排列型分配问题的生成函数 7.5.6 有限制位置的排列及棋子多项式
2008-2009 学年第二学期
制作人 陈勇
的生成函数为
由二项式定理知

组合数学(第7章7.3 & 4)

组合数学(第7章7.3 & 4)

α 是实数
生成函数的定义
定义1: 令序列h0, h1,…,hn…为一无穷序 列, 其生成函数定义为: g(x)=h0+h1x+h2x2+…+hnxn+… 例：序列1, 1, 1,…的生成函数是 g(x)=1+x+x2+…+xn+… =1/(1x) （|x|<1）
序列与生成函数的关系
例3: 设k是正整数,求序列h0, h1,…, hn…的 生成函数,其中hn 等于方程e1+e2+…+ek=n 的非负整数解个数.
1 1 1 1 = × × × 3 4 2 1 x 1 x 1 x 1 x5
小结
生成函数提供了另一种组合计数方法： 将组合计数转化为代数问题。
用于组合计数时，通常代数方法要更为困难。 代数方法用于计算某些序列的生成函数较为 方便。
生成函数方法可以用于解决一般具有重 复的组合计数问题。但往往较为困难。
第七章 递推关系和生成函数 7.3 非齐次递推关系 7.4 生成函数
回顾：齐次递推关系求解
常系数线性齐次递推关系求解步骤： hn=a1hn-1+a2hn-2+…+akhn-k （1）解特征多项式方程xk-a1xk-1- a2xk-2-…- ak=0 （2）若特征方程有k个不同的根，则直接给出递 推关系的一般解，然后根据初始条件确定相应 系数； 若特征方程有重根，则先给出关于每个重 根的一般解，再求出递推关系一般解。
例1
求解hn= 2hn-1+ 3n (n≥1), 初始值h0=2 . 解：首先解对应齐次关系 hn= 2hn-1，特征 首先解对应齐次关系 方程x2=0，特征根x=2, 得到一般解： hn= c2n 求非齐次递推关系的一个特解，尝试： 求非齐次递推关系的一个特解 hn= p3n ，代入得p3n =2p3n-1 +3n 解得：p=3 hn= 3n+1是一个特解。

生成函数与排列组合

生成函数与排列组合

S 的5组合数=1：2ab2c
例3
用n个水果组成一只个果篮。果篮中可以装 4种水果：苹果为偶数，香蕉为5 的倍数， 至多有4个桔子，至多有一个西瓜。可以有 多少种装法？
设共有 hn 种装法。 hn 是方程 r1 r2 r3 r4 n 的非负整数解的个数。 其生成函数为
g( x ) (1 x 2 ...)(1 x 5 ...)(1 x ... x 4 )(1 x ) 1 1 1 1 x5 (1 x ) 2 5 (1 x )2 1 x 1 x 1 x
C
n 0 n n1
解
x ( n 1) x n
n n 0

所以 hn n 1
例4
用n个水果组成一只个果篮。果篮中可以装 4种水果：苹果为偶数，香蕉为奇数，至多 有4个桔子，至少有一个西瓜。可以有多少 种装法？
解
设共有 hn 种装法。 生成函数为
g( x ) (1 x 2 x 4 ...)(x x 3 ...) (1 x ... x 4 )( x x 2 ...) x 2 (1 x 5 ) 1 x 1 x5 x 2 2 2 2 2 ( 1 x ) ( 1 x ) 1 x 1 x 1 x 1 x 2 3 4 5 6 7 8 x 2 x 5 x 8 x 14x 19x 28x ...
等同于求不允许空盒共有多少个有标志的盒子个完全相同的球放入拆分数问题把n拆分成m个正整数之和共有多少种拆分方法
§5 生成函数求解组合问题
例1 解
g( x ) (1 x ... x 5 )(1 x x 2 )(1 x ... x 4 )
是什么数列的生成函数？
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
习题
第四章 二项式系数
4.1 二项式定理 4.2组合恒等式 4.3非降路径问题 4.4牛顿二项式定理 4.5多项式定理 4.6 基本组合计数的应用 本章小结
习题
第五章 包含排斥原理
5.1 包含排斥原理 5.2 多重集的r-组合数 5.3错位排列 5.4 有限制条件的排列问题 5.5有禁区的排列问题 本章小结
组合数学课件
制作讲授：王继顺
B
1
目录（1）
目录
第1章 什么是组合数学 1.1引例 1.2组合数学研究对象、内容和方法 第2章 鸽巢原理 2.1 鸽巢原理：简单形式 2.2 鸽巢原理：加强形式 2.3 Ramsey定理 2.4 鸽巢原理与Ramsey定理的应用 本章小结
习题
第3章 排列与组合 3.1 两个基本的计数原理 3.2 集合的排列与组合 3.3 多重集的排列与组合 本章小结
个
证明： Qb0 b1 ...bl1 0
推
bl a0,bl1 a1,...,bk akl,...
论
B(x)b0 b1x...bl1xl1 blxl bl1xl1 ...
00...0a0xl a1xl1 ...
xl(a0 a1xa2x2 ...)
xl A(x)
B
20
§§77.2.2生生成函成数函运算数推的论基2 本运算
特别地：若 =1，则序列(1,1,…,1,…)的指数生成函数为ex 。
B
14
§§7.71.1指数生生成成函函数数的例8基本概念
7.1.2 指数生成函数
解：由定义7.2和二例1×项84、式×求定7×序理…列，×(有1,(31n×+41,),1…×)4的×指7,数…生, 成函
例
fe ( x)
题
1
(1 4)
的生成函数。
B
9
§7.1§生7.1成生函成数函的数基例4本概念
7.1.1 生成函数
例题
例4、求序列(0, 1×2×3, 2×3×4,…, n(n+1)(n+2),…)的生成函数。
解：由牛顿二项式定理的推论1.10.4，有
1
xn1 x n0将上式两源自同时微分两次得2 (1 x)3
n(n 1)xn2
a0 a1 ... an , ...)的普通母函数。
B
18
解 ： 先 求 序 列 ( 0 2 , 1 2 , §..., r42§.,2.7...)2生的生普成成通函函母数数运函的算数例基。2 本运算
由 牛 顿 二 项 式 定 理 知 (1 - x ) 1 r x i ,
例将
上题式
...,
n(n
1)(n
2),
...)
的普通母函数。
B
10
§7.1§7生.1 成指数函生数成函的数基概本念 概念
7.1.2 指数生成函数
定义 7.2
给定一无穷序列(a0,a1,…an,…)（简记为{an}），称函
数
fe(x) ai
i0
xi i!
为序列{an}的指数生成函数。
注： fe(x)也是形式幂函数。 经常可结合以下公式运算：
4.1.1
例 题
生成k 函1 1数2 1 2 1 1 2 2 ... 1 2 k 1
1+ 1+
kk11例C4(4k3,、21),证…32明k,..C.(k1(2-(!42nxk,n)-)1,/1…2k)是!)的x序k 生列成(C函(0数,0)。,
C(2(,1)4,
x
)
k
1 2k k !1 3 ... (2k 1) x k
n2
将上式两端再微分得
6 (1 x)4
n(n 1)(n 2)xn3
n3
两边同乘以x得
6x
n(n 1)(n 2)xn
(1 x)4 n0
0 1 2 3x 2 3 4x2 ... n(n 1)(n 2)xn ...
因此
f
(
x)
(1
6x x)4
是序列(0，1
2
3，2
3
4,
0 01 2x4 2x2...2nnxn...
(14x)12
B
13
§7§.17.生1 成指数函生数成的函基数例本7 概念
7.1.2 指数生成函数
例题
例7、求序列{1,α,α2,…,αn,…}的指数生成函 数fe(x)。其中α是实数。
解：由定义7.2，有
fe (x ) 1 1 x !2x 2 2 ! ...nx n n ! ... e x
令B( x) 1 (1 x) ,根据上述定理有
c0 a0 1 a0 c1 a0 1 a1 1 a0 a1 ......
故
cn A( x
a0 1 a1 ) (1 x) A(
1 x
... ) B(
xa)n是 1序列a0(
a1 a0 , a
... an 0 a1 , ...,
例题
例5、设n是整数，求序列(p(n,0), p(n,1), …, p(n,n))的指数生成函数fe(x)。
解：由定义7.2及公式P(n,r)=r!C(n,r),以及例1的
结论，有
fe(x)
p(n,0)p(n,1) x...p(n,n) 1!
xn n!
n 0
n 1
x...
n n
xn
(1x)n
fe(sx) an
n0
n!
将上式两边同乘以e-s并从0到积分得
由分部0 e 积 s 分f e 法( s x 有) d s 0 n e 0 se s ns da sn s n n nx ! !n d s n 0 a n x n n !0 e s s n d s
故
0
0 esfe(sx)dsanxnf(x)
r1 r
(r 2)(r 1)r (r 1)r(r 1) r(r 1)(2r 1)
3!
3!
6
故 c r
r
i2
i1
r(r
1)(2r 1)
6
B
19
§7§.27.2生生成成函函数数运的算推基论本1 运算
六
推论7.2.1：若 b k a 0 k l k k l l， 则 B (x ) x lA (x )
解：由定义7.1及二项式定理的推论3.10.2有
f(x)n01n 1xn21x2...(1)k
nk1 k
xk...
= (1)k
nk 1 k
xk
k0
=
knxk (1x)n
k0
B
8
证(1明 4：x )由1牛2 顿1二§项 4式.1定1k 生2§理(成7有.14函x生)数k 成的函基数例本3概念
k 1
k !k !
1 2 4 ... (2k ) 1 3 ... (2k 1) x k
k 1
k !k !
1 (2k )! x k 1
k1 k !k !
k 1
2k k
xk
0 0
2 1
x
4 2
x 2 ...
2k k
x k ...
由定义知，(1-4x)-1/2是序列(C(0,0), C(2,1), C(4,2), … , C(2n,n),…)
两
端
对
x
微
例2、求和 分 再 乘 以 x 得i
i 0i 的2 值。 （x0 1 x ） 2
ix i
i0
再 将 上 式 两 端 对 x 微 分 再 乘 以 x 得 x (1 x（) 1 x）3 i 2 x i
i0
故 x (1 x（) 1 x）3是 序 列 ( 0 2 , 1 2 , ..., r 2 , ...)的 普 通 母 函 数 。
B
12
§§77.1.1指生数生成成函函数数的例6基本概念
7.1.2 指数生成函数
例题
例6、求序列(p(0,0), p(2,1), p(4,2),…, p(2n,n),…)的指数生成函数fe(x)。
解：由定义7.2及公式P(n,r)=r!C(n,r)，以及例3的结论，有
fe(x)p(0,0)p(2,1)1x!p(4,2)x 22 !...p(2n,n)x nn !...
B
17
例题
§7.§2 7生.2 成生函成函数数的运基算本例运1 算
例1、设A(x)是序列{an}的生成函数，则 A(x)/(1-x)是序列{a0,a0+a1,…,a0+a1 +…+an,…} 的生成函数。
证明：由牛顿二项式定理知
1 1 x x2 ... xn ... 1- x 故 1 (1 x)是序列(1,1, ...,1, ...)的普通母函数。
x数。(1 4 7)
1!
x2 2!
...
1 4 7 ... (3n
1)
xn n!
...
1 4 7 ... (3n 1) x n
n0
n!
1
4 3
7 3
...
3n 1 3
3n xn
n1
n!
1
4 3 4 3 1 ... 4 3 n 1 (3 x)n
习题
B
2
目录（2）
第六章 递推关系 6.1 Fibonacci数列 6.2 常系数线性齐次递推关系的求解 6.3 常系数线性非齐次递推关系的求 解 6.4 用迭代和归纳法求解递推关系 本章小结
习题 第七章 生成函数 7.1生成函数的定义和性质 7.2多重集的r-组合数 7.3正整数的划分 7.4指数生成函数与多重集的排列问 题 7.5 Catalan数和Stiring数 本章小结
故 c r
r i1
i
2的
普