组合数学课件 第二章母函数与递推关系 357页PPT文档

来源:互联网 编辑: 张倩 手机版

www.07swz.com防采集请勿采集本网。

因转码可能存在排版等问题,敬请谅解!以下文字仅供您参考:组合数学

第二章 母函数与递推关系 §2.1 母函数

递推关系是计数的一个强有力的工具, 特别是在做算法分析时是必需的。

递推关 系的求解主要是利用母函数。

当然母函数 尚有其他用处,但这主要是介绍解递推关 系上的应用。例如(1?a1x)1(?a2x)???(1?anx)?1?(a1?a2?????an)x?(a1a2?a1a3?????an?1an)x2?????a1a2???anxn(2 -1-1) §2.1 母函数x 2 项的系数 a 1 a 2 ? a 1 a 3 ? ? ? ? ? a n ? 1 a n

中所有的项包括n个元素a1,a2, …an中

取两个组合的全体;同理项系数包含了从n个元素a1,a2,… an中取3个元素组合的全体。

以此类推。 §2.1 母函数

若令a1=a2= …=an=1,在(2-1-1)式

中x项2 系数: a 1 a 2 ? a 1 a 3 ? ? ? 中? ? 每a 一n ? 个1 a 组n 合有1个贡献,其他各项以此类推。故有:(1?x)n?1?C (n,1 )x?C (n,2)x2?? ?C (n,n)xn (2 -1-2) §2.1 母函数

另一方面: ? (1 ? x )m (1 ? x )n? (1 ? x )m ? n ?[C(n,0)?C(n,1)x???C(n,n)xn]?[C(m,0)?C(m,1)x?1???C(m,m)x?m] ?x?m[C(m?n,0)?C(m?n,1)x???C(m?n,m?n)xm?n §2.1 母函数

比较等号两端项对应系数,可得一等式C (m ? n ,r)? C (m ,0 )C (n ,r)? C (m ,1 )C (n ,r? 1 )? ? ? C (m ,r)C (n ,0 ) §2.1 母函数

同样对于(1?x)n(1?1/x)m, n?m(设

),用类似的方法可得等式:C (m ? n ,m )? C (n ,0 )C (m ,0 )? C (n ,0 )C (m ,0 )? ? ? C (n ,0 )C (m ,0 )(-2 1 -3)

正法如下:? ( 1 ? x ) n ( 1 ? 1 /x ) m ? x ? m ( 1 ? x ) m ? n §2.1 母函数?[C(n,0)?C(n,1)x???C(n,n)xn] ?[C(m,0)?C(m,1)x?1???C(m,m)x?m]?x?m[C(m?n,0)?C(m?n,1)x?C(m?n,2)x2 ???C(m?n,m?n)xm?n

比较等式两端的常数项,即得公式(2-1-3) §2.1 母函数

又如等式: (1?x)?C(n,0)?C(n,1)x?C(n,2)x2 ?? ?C(n,n)xn令x=1 可得C (n,0)?C (n,1)?C (n,2)?? ?C (n,n)?2n (2 -1-4) §2.1 母函数(2-1-2)式等号的两端对x求导可得:C (n ,1 )? 2 C (n ,2 )? 3 C (n ,3 )? ? ? n(n C ,n ) ?n 2 n ? 1 (-2 1 -5)

等式(2-1-5)两端令x=1,得:C (n ,1 )?2 C (n ,2 )?3 C (n ,3 )? ? ?n(n C ,n )?n 2 n? 1(-2 1-5) §2.1 母函数用类似的方法还可以得到:?C (n,1)x?2C (n,2)x2?3C (n,3)x3 ?? ?n(C n,n)xn?n(1 x?x)n?1? C (n,1)?22C (n,2)?32C (n,3)?? ?n2C (n,n)?n(n?1)2n?2(2 -1-7 §2.1 母函数

还可以类似地推出一些等式,但通过上面 一些例子已可见函数 (1?在x研)n 究序列 C (n ,0 )C ,(n ,1 )? ,,C (n ,n ) 关系时所起的作用。

对其他序列也有同样的 结果。

现引进母函数概念如下:

定义:对于序列 a0,a1构,a造2,? 一函, 数:

G (x)?a0?a1x?a2x2?? ,称函数G(x)是序列 a0,a1,a的2,? 母函数 §2.1 母函数(1? x)n例如C (n ,0 )C ,(n ,1 )? ,,C (n ,n )如若已知序列 a0,a1,则a2对,? 应,的母函数G(x)

便可根据定义给出。

反之,如若以求得序列的 母函数G(x),则该序列也随之确定。

序列 a0,a1,a可2,? 记为, 。 { a n } §2.2 递推关系

利用递推关系进行计数这个方法在算法分 析中经常用到,举例说明如下:

例一.Hanoi问题:这是个组合数学中的 著名问题。

N个圆盘依其半径大小,从下 而上套在A柱上,如下图示。

每次只允许 取一个移到柱B或C上,而且不允许大盘放 在小盘上方。

若要求把柱A上的n个盘移到 C柱上请设计一种方法来,并估计要移动 几个盘次。

现在只有A、B、C三根柱子可 用。 §2.2 递推关系

Hanoi问题是个典型的问题,第一步要设 计算法,进而估计它的复杂性,集估计工作量。

算法: N=2时 ?第最第一后二步把步先B把上把下的最面圆上的盘面一移的个到一圆C个上盘圆移盘到套C在上B上 到此转移完毕ABC §2.2 递推关系? 假定n-1个盘子的转移算法已经确定。

? 对于一般n个圆盘的问题, ? 先把上面的n-1个圆盘经过C转移到B。

? 第二步把A下面一个圆盘移到C上 ? 最后再把B上的n-1个圆盘经过A转移到C上??????ABC §2.2 递推关系

上述算法是递归的运用。n=2时已给出 算法;n=3时,第一步便利用算法把上面 两个盘移到B上,第二步再把第三个圆盘转 移到柱C上;最后把柱B上两个圆盘转移到 柱C上。

N=4,5,…以此类推。 §2.2 递推关系

算法分析:令h(n)表示n个圆盘所需要 的转移盘次。

根据算法先把前面n-1个盘子 转移到B上;

然后把第n个盘子转到C上;最 后再一次将B上的n-1个盘子转移到C上。n=2时,算法是对的,因此,n=3是算 法是对的。

以此类推。于是有 §2.2 递推关系

算法复杂度为: h ( n )? 2 h ( n ? 1 )? 1 ,h ( 1 )? 1 (- 2 - 1

H (x )? h (1 )x? h (2 )x 2? h (3 )x 3? ? ,

H(x)是序列 h(1),h(2),h(3)? , 的母函数。

给定了序列,对应的母函数也确定了。

反过来 也一样,求得了母函数,对应的序列也就可得 而知了。

当然,利用递推关系(2-2-1)式也可以

依次求得 h(2),h(3),?,这样的连锁反应关系,

叫做递推关系。 §2.2 递推关系

下面介绍如何从(2-2-1)式求得母函数 H(x)的一种形式算法。

所谓形式算法说的 是假定这些幂级数在作四则运算时,一如 有限项的代数式一样。

H (x )? h (1 )x? h (2 )x 2? h (3 )x 3? ? , _ ? )? 2 x( x _ _ ) H ? - 2 _ _ h _ ( 1 ) x ? 2 h ( 2 _ _ ) _ _ x ? ? ,(1?2x)H(x)?h(1)x?[h(2)?2h(1)x]2?[h(3)?2h(2)x]3?? §2.2 递推关系

根据(2-2-1),? h ( 1 ) ? 1 ,h ( 2 ) ? 2 h ( 1 ) ? 1 ,h ( 3 ) ? 2 h ( 2 ) ? 1 , ?? ( 1 ? 2 x ) H ( x ) ? x ? x 2 ? x 3 ? ? ? x /1 ? ( x )

或利用递推关系(2-2-1)有x2:h(2)?2h(1)?1 x3:h(3)?2h(2)?1

_ ?) _ _ ? ? _ _ _ ? ? _ _ _ _ _ _ _ _ _ _ _ _? H (x )? x ? 2 x(x H )? x 2 /1 ( ? x ) §2.2 递推关系

上式左端为: h ( 2 ) x 2 ? h ( 3 ) x 3 ? ? ? H ( x ) ? h ( 1 ) x ? H ( x ) ? x 右端第一项为: 2h(1 )x2?2h(2)x3?? ?2x[h(1 )x?h(2)x2?? ]?2H x (x) 右端第二项为:x2?x3?? ?x2/1 (?x) §2.2 递推关系整理得(1?2x)H(x)?x2 ?x? x 1?x 1?x

这两种做法得到的结果是一样的。即:

H(x)?x(1?x)1(?2x) §2.2 递推关系如何从母函数得到序列h(1),h(2),??下

面介绍一种化为部分分数的算法。 令

H(x)? A ? B ?A(1?2x)?B(1?x) 1?x 1?2x (1?x(1?2x)?(A?B)-2(A?B)x (1?x)1(?2x)? (A ? B )? (2 A ? B )x ? x §2.2 递推关系由上式可得:

{ ?A 2A ?? BB ?? 01? A??1, B?1.即:H(x) ? 1 ? 1 1?2x 1?x?(1?2x?22 x2 ?23x3 ??)?(1? x? x2 ??) ? (2?1)x ?(2?1)x ?(2?1)x ???? ? (2k ?1)xk k?1 §2.2 递推关系因为:?

H(x) ??h(k)xk k?1?h(k)?2k ?1 §2.2 递推关系

例2. 求n位十进制数中出现偶数个5的数 的个数。

先从分析n位十进制数出现偶数个5的数的

结构入手 p1p2?pn?1是n-1位十进制数,若含 有偶数个5,则 p n ?1 取5以外的0,1,2,3,4, 6,7,8,9九个数中的一个,若 p1p2?pn?1 只有奇数个5,则取 pn ? 5 ,使 p1p2?pn?1pn

成为出现偶数个5的十进制数。 §2.2 递推关系解法1:令 an ? n 位十进制数中出现5的数的个数,bn ? n 位十进制数中出现奇数个5的数的个数。 故有:

{ a bn n? ?9 9b ann? ?11? ?a bn n? ?1 1?a1?8, b1?1(2?2?2) §2.2 递推关系(2-2-2)式中的 an?9an? 表1? 达b了n?含1有偶数

个5的n位十进制数的两个组成部分。

p91apn2?? 1表达p,n?由1令含有取偶p5n 以数外个的5的0,n-11,位2十,进3制,数4,6,7当,8,9p九1是p个2含? 数有p中n奇?的1数一个个5数的构n-成1位的十。

进b制项n ?数表1 ,示令 而得pn ? 5 是含p1偶p2数?个pn5的n位十进制数。bn?9bn?1?an?1也有类似解释。 §2.2 递推关系(2-2-2)是关于序列{ a 和n } {的bn连} 立关系。设序列{ a n }的母函数为 A(x) ,序列{bn }的母

函数为B( x) 。即:A(x) ? a1 ?a2x?a3x2 ??B(x) ?b1 ?b2x?b3x2 ???9xA(x) ? ?9a1x?9a2x2 ??

_ ?) ?_ xB_ (x) ??_ b1x_ ?b_ 2x2_ ??_ _ _ _ _ _(1 ? 9 x )A (x )? x(x B )? 8 §2.2 递推关系承前页:x : a2 ? 9a1 ? b1x 2 : a3 ? 9a2 ? b2

____________ x3 : a4 ? 9a3 ? b3?) ???????A (x )? 8 ? 9 x(x A )? x(x B )? ( 1 ? 9 x )A (x )? x(x B )? 8 §2.2 递推关系又:B(x)?b1x?b2x?b3x2 ???9xB(x)??9b1x?9b2x2 ??

_ ?) ?x_ A(x)?_ ?a_ 1x?a2_ x2_ ??_ _ _ _ _(1 ? 9 x)B (x)? x(x A )? 1故得关于母函数 A(x) 和 B(x) 得连立方程组:

{ (1?9x)A(x)?xB (x)?8 ?xA (x)?(1?9x)B(x)?1 §2.2 递推关系1?9x ?D??x?(1?9x)?x? 1? 1x8 ? 8x2 0?x 1?9x? (1 ? 8 x)1 ( ? 1x)0A (x )? 1 ? 1x 1 ? 8 8x 2 0 1 81 ? ? 9 x x? (1 ? ? 8 7 x )x 1 ? ? ( 1 1 8x )0B (x )?11 ? 9 x8 ?1 ? x( 1 ? 8 x )1 ? (1x )0 ? x1( 1 ? 8 x )1 ? (1x )0 §2.2 递推关系? ? A ( x )? 1 (7?9)? 1 ? ( 7 ?8 k? 9 ?1 k ) x 0 k2 1 ? 8 x1 ? 1 x0 2 k ? 0?ak?7 28k?1?9 21k0?1 §2.2 递推关系

解法二: n-1位的十进制数的全体共 9?10n?2从中 去掉含有偶数个5的数,余下的便是n-1位 中含有奇数个5的数。故有:an ?9an?1?bn?1 bn?1 ?9?10n?2 ?an?1 ? a n ? 8 a n ? 1 ? 9 ? 1 n ? 2 ,0a 1 ? 8 §2.2 递推关系令A(x)?a1?a2x?a3x2??

___ __ _ _ _ _ _ ?) ?8x(A x)??8a1x?8a2x2??( 1 ? 8 x ) A ( x ) ? 8 ? ( a 2 ? 8 a 1 ) x ? ( a 3 ? 8 a 2 ) x 2 ? ? §2.2 递推关系?(1?8x)A(x)?8?9x?9?10 x2???8? 9x ?8?7x1 1?10 x 1?10 x?A(x)? 8?7x1 ?1( 7 ? 9 ) (1?10x)1(?10x) 21?8x 1?10x? ?1?(7?8k ?9?10k)xk2k?0 ?a?7?8k?1?9?1k0 ?122 §2.2 递推关系

例三:从n个元素a1,a2,? ,an中取r个进 行允许重复的组合。

假定允许重复的组合 数用C(n,r) 表示,其结果可能有以下两种 情况。1)不出现某特定元素设为 ,a 1 其组合数 为 C(n,?1相,r当) 于排除 后从 a 1 中取ra个2,做?,an 允许重复的组合。 §2.2 递推关系2)至少出现一个 a 1 ,取组合数为 C(n,r?1) 相当于从 a1,a2,? ,an中取r-1个做允许重复 的组合,然后再加上一个 a 1 得从n个元素中 取r个允许重复的组合。

依据加法原则可得: C ( n ,r ) ? C ( n ,r ? 1 ) ? C ( n ? 1 ,r )

因 C (n ,1 )? n ,C (n ? 1 ,1 )? n ? 1 ,故令 C(n,0)?1 §2.2 递推关系

递推关系(2-2-3)带有两个参数n和r。

Gn(x)?C(n,0)?C(n,1)x?C(n,2)x2??

___ __ _ _ _ _ ?xG n(x)? ?C(n,0)x?C(n,1)x2???) ?Gn?1(x)??C(n?1,0)x?C(n?1,1)x?? ( 1 ? x ) G n ( x ) ? G n ? 1 ( x ) ? 0 ( 2 ? 2 ? 3 ) §2.2 递推关系(2-2-3)式是关于Gn (x) 的递推关系,但 系数 (1?x)不是常数。但 ?G 1(x)?C(1,0)?C(1,1)x?C(1,2)x2???1?x?x2?? ? 1 1?x? Gn(x)?1?1xGn?1(x)?(1?1x)2Gn?2(x)???(1-1x)n-1G1(x)?(1-1x)n §2.2 递推关系由二项式定理( 1 ? x )? 1 ? n ? n x ( n ? 1 ) x 2 ? n ( n ? 1 )n ? (2 ) x 3 ? ?2 !3 !可得C(n,r)?n(n?1)? (n?r?1)?(n?r?1)!r!(n?1)!?C(n?r?1,r) §2.3 母函数的性质 §2.3 母函数的性质

一个序列和它的母函数一一对应。

给了序 列便得知它的母函数;

反之,求得母函数序列 也随之而定。

这种关系颇像数学中的积分变换, 特别酷似离散序列的Z变换。如§2的例子所示 的那样,为了求满足某种第推关系的序列,可

把它转换为求对应的母函数G(,x) G可(x能) 满足

一代数方程,或代数方程组,甚至于是微分方 程。 §2.3 母函数的性质最后求逆变换,即从已求得的母函数 G(x) 得到序列{an。

} 关键在于要搭起从序列到母函

数,从母函数到序列这两座桥。

这一节便是以

此为目的的。

不特别说明下面假设 {ak、} {b两k } 个序列对应的母函数分别为 A、(x) B(x) §2.3 母函数的性质性质1:{ 若bk ?

0 k?l ak?l k?l则 B(x)?xlA(x)

证:B(x)?0?0???0?blxl ?bl?1xl?1???a0xl ?a1xl?1???xlA(x) §2.3 母函数的性质

例. 已知 A ?x??x?x2?x3?? ?ex?11 ! 2! 3!则 B (x )? x m ? x m ? 1 ? x m ? 2? ? ? x m ? 1 (e x? 1 ) 1 ! 2 ! 3 ! §2.3 母函数的性质

性质2:若 bk ?ak?l,l?1? 则 B(x)?[A(x)? akxk]/xl k?0 §2.3 母函数的性质

证:? B (x )? b 0 ? b 1 x ? b 2 x 2 ? ?? B(x) ?al ?al?1x?al?2x2 ???1 xl(al xl?al?1xl?1?al?2xl?2??)?[A(x)?a0 ?a1x?a2x2 ???al?1xl?1]/ xll?1? ?[A(x)? akxk]/ xl k?0 §2.3 母函数的性质

例. A(x)?sixn?x?x3?x5?? 3! 5!B(x)?1x?1x3 ?? 7! 9!?[sinx?x?1x3 ?1x5]/x6 3! 5! §2.3 母函数的性质? 性质2:若bk?k i?0a i ,则B(x) ? A(x) 1?x

证: 1 : b0 ? a 0x : b1 ? a 0 ? a1x 2 : b1 ? a 0 ? a1 ? a 2???????x n : b ? a0 ? a1 ? a2 ? ? ? an ?) ???????? §2.3 母函数的性质 1 : b0 ? a0 x : b1 ? a 0 ? a1 x 2 : b1 ? a 0 ? a1 ? a 2 ???????

_ _ _ _ _ _ x n : b ? a0 ? a1 ? a2 ? ? ? an ?) ????????B (x )? a 0/1 (? x )? a 1 x/1 (? x )? a 2 x 2/1 (? x )? ? ? [a 0? a 1 x? a 2 x 2? ? ]/1 (? x )? A (x )/1 (? x ) §2.3 母函数的性质

例. 已知 A (x )? 1 ? x? x 2? ? ? x n? ? ?1 1 ? xB (x )? 1 ? 2 x? 3 x2? 4 x3? ? ? (1 ? 1 x )2? ?(k?1)xkk?0?(1?1x)2 §2.3 母函数的性质

类似可得:C(x) ? (1? 2x ? 3x2 ? 4x3 ??)?(1? x ? x2 ? x3 ??)?1? 3x ? 6x2 ? ?10x3 ??? ?? k?01 (k 2?1)(k?2)xk?1 (1? x)3 §2.3 母函数的性质? 性质2:若 ? a k 收敛,则 B(x)?A(1)?xA (x)1:b0k?0?a0?a1?a2???A(1)1?xx:b1? a1?a2???A(1)?a0

_ _ _ _ _ _ x2:b1?a2 ???A(1)?a0 ?a1?) ????????B (x )?A (1 )1 [ ? x? x2? ? ]? a 0 x (1 ? x? x2? ? ) ? a 1 x2(1 ? x? x2? ? )? ? §2.3 母函数的性质?B(x)?1A?(1x)?(a0?a1x?? )x/1(?x)?A(1)?xA (x) 1?x §2.3 母函数的性质

性质5. 若 bk,?则kak B ?x 。??x'A ?x? 例. A ?x??1?x?x2?? ?11?x则 x? 2 x2? 3 x3? ? ?x? ? ?1 ? 1x? ? ???1 ? x x?2 §2.3 母函数的性质

性质6. 若bk?,则ak 1? kB?x??1x?0xA?x?dx

性质5和性质6的结论是显而易见的。 §2.3 母函数的性质

性质7. 若

c k ? a 0 b k ? a 1 b k ? 1 ? a 2 b k ? 2 ? ? ? a k b 0k? ? aibk?i i?0则 C ? x ? ? c 0 ? c 1 x ? c 2 x 2 ? ? ? A ? x ? B ? x ? §2.3 母函数的性质证:1:c0?a0b0,2 :c 1? a 0 b 1? a 1 b 0 ,

__ __ _ __ _ _ ?)?3 :c 2 ? a 0 b 2 ? a 1 b 1 ? a 2 b 0 ,? ? C ? x ? ? a 0 b 0 ? b 1 x ? b 2 x 2 ? ? ? ? ? a 1 x b 0 ? b 1 x ? b 2 x 2 ? ? ? ? ? a 2 x 2 b 0 ? b 1 x ? b 2 x 2 ? ? ? ?? ? ? ? ? a 0 ? a 1 x ? a 2 x 2 ? ? b 0 ? b 1 x ? b 2 x 2 ? ?? C ?x ?? A ?x ?B ?x ? 。 §2.3 母函数的性质

例. 已知 A?x? ? 1? x ? x2 ?? ? 1 ,1? xB?x??x?2x2?3x3????1x? x?2,Ck?1?2?3??? k?k?k ?1?,2则C?x??x?1?x?3 §2.4 Fibonacci数列 §2.4.1 递推关系

Fibonacci数列是递推关系的又一个典型问 题,数列的本身有着许多应用。

问题:有雌雄兔子一对,假定过两月便可 繁殖雌雄各一的一对小兔。

问过了n个月后共 有多少对兔子?设满n个月时兔子对数为F n 其中当月新生 兔数目设为N n 对。

第n-1个月留下的兔子数目 设为O n 对。?F n?N n?O n §2.4.1 递推关系但

O n ? F n ? 1 , N n ? O n ? 1 ? F n ? 2即第n-2个月的所偶兔子到第n个月都有繁殖能力了。? F n ? F n ? 1 ? F n ? 2 ,F 1 ? F 2 ? 1 ( 2 ? 3 ? 1 ) 由递推关系(2-3-1)式可依次得到

F 3?F 1?F 2?2, F 4?F 2?F 3?3 , F 5?F 3?F 4?3?2?5,? §2.4.2 问题的求解设 G (x)?F 1x?F 2x2? ? x3 : F3 ? F2 ? F1 x4 : F4 ? F3 ? F2

_ ?) ????? __

G ( x ) ? x 2 ? x ? x ( G ( x ) ? x ) ? x 2 G ( x )? (1 ? x? x 2 )G (x )? x §2.4.2 问题的求解承前页?G( x)?1?xx?x2? (1?1?x 5x)(1?1?5x)22? A?B1?1? 5x 1?1? 5x22 §2.4.2 问题的求解承前页

{ A? B ? 0 5 (A ? B) ?1 2A? B ?0

{A?B? 2 5A?1 , B??155 §2.4.2 问题的求解承前页? G(x)? 1 [ 1 ? 1 ]5 1?1? 5x 1?1? 5x22? 1 [(???)x?(?2 ??2)x2 ??]5?Fn?(?n??n) 5 §2.4.2 问题的求解其中??? 2? 1 ?5 ,??2? 1 ?5 1 ?5 2 1 ?5 2?? F n?1 5 (n?n )?1 5 (1 ? 25 )n (-2 3 -2)Fn ?1? 5?1.618Fn?12 §2.4.3 若干等式1) F 1 ? F 2 ? ? ? F n ? F n ? 2 ? ? 1(- 3 2 - 3证明:

F1 ? F3 ? F2

F2 ? F4 ? F3??

__ __ _ __ _ _ Fn?1 ? Fn?1 ? Fn ? ) Fn ? Fn?2 ? Fn?1? F 1 ? F 2 ? ? 1 ? F n ? F n ? 2 ? F 2 ? F n ? 2 ? 1 §2.4.3 若干等式2) F 1 ? F 3 ? F 5 ? ? ? F 2 n ? 1 ? F 2 n (- 3 2 - 4证明:

F1 ? F2

F3 ? F4 ? F2

F5 ? F6 ? F4??

__ __ _ __ _ _ ? ) F2n?1 ? F2n ? F2n?2? F 1 ? F 3 ? F 5 ? ? ? F 2 n ? 1 ? F 2 n §2.4.3 若干等式

证3)明:F 1 2 F? 12F ?2 F2 2? F? 1 ? F n 2 ? F n F n ? 1 (- 3 2 - 5 F22 ? F2(F3 ?F1) ? F2F3 ?F2F1 F32 ? F3(F4 ?F2) ? F3F4 ?F2F3 ??

__ _ _ _ _ ?) Fn2 ? Fn(Fn?1 ?Fn?1) ? FnFn?1 ?Fn?1Fn? F 1 2 ? F 2 2 ? ? ? F n 2 ? F n F n ? 1 §2.4.4 在选优法上的应用设函数 y?f(x)在区间 (a,b) 上有一单峰

极值点,假定为极大点。

所谓单峰极值,即只有一个极值点? ,而且

当x与? 偏离越大,偏差 f(x)?f(?) 也越大。如下图:y

0 a? b x §2.4.4 在选优法上的应用设函数 f (x) 在 x??点取得极大值。要求 用若干次试验找到 ? 点准确到一定的程度。最

简单的方法,把 (a,b)三等分,令: 如下图x 1 :? a ? 1 3 (b ? ya )y?,x 2 f? (xa )? 3 2 (b ? a )

f (x1) f (x21)

0 ax1 x2 b x §2.4.4 在选优法上的应用

依据 f(x1),f(x2)的大小分别讨论如下:

当 f(x1)?f(x2),则极大点? 必在 (a, x2)区间

上,区间 (x2,b)可以舍去。y y?f(x)y

f (x1) f (x21)

0 ax1 x2 b x 0 a x1 x2x

f(x1)?f(x2) §2.4.4 在选优法上的应用

当 f(x1)?f(x2),则极大点? 必在 (x1,b) 区间

上,区间 (a, x1) 可以舍去。y y?f(x)y

f (x1)f (x2)

0 ax1 x2 bx 0 x1 x2 bx

f(x1)?f(x2) §2.4.4 在选优法上的应用

当 f(x1)?f(x2),则极大点? 必在(x1,x2)区间

上,区间 (a, x1) 和 (x2,b)均可以舍去。y y?f(x)y

f (x1) f (x21)

0 ax1 x2 b x 0 x1 x2x

f(x1)?f(x2) §2.4.4 在选优法上的应用

可见做两次试验,至少可把区间缩至原来 区间的2/3,比如 f(x1)? ,f进(x 一2)步在 (a, x2)区间上找极值点。

若继续用三等分法, 将面对着这一实事,即其中 x 1点的试验没发挥其作用。

为此设想在 (0区,1间) 的两个对称点 分别x,l做?试x验。

0 l?x x 1 §2.4.4 在选优法上的应用设保留(0, x)区间,继续在 (0, x) 区间的下面

两个点 x2,(1?x)x处做试验,若x 2? ( 1 ? x )x(-2 3 -6则前一次 1?x的点的试验,这一次可继续使用可节省一次试验。由(2-3-6)式有x2?x?1?0? x??1? 5?0.618 20 0.38?2(0.61)28 0.618 1 §2.4.4 在选优法上的应用

这就是所谓的0.618优选法。即若在(0,1)区

间上找单峰极大值时,可在 x 1 ? 0 .6,1 x 2 ? 1 8 ? 0 ,6? 1 0 .3 8 832

点做试验。

比如保留区间 (0,0.61)8,由于 (0.61)28?0.32,8故只要在

0 .6? 1 0 .38 ? 2 0 .28 36 点作一次试验。 §2.4.4 在选优法上的应用

优选法中可利用Fibonacci数列,和0.618法 不同之点在于它预先确定试验次数,分两种情 况介绍其方法。(a) 所有可能试验数正好是某个 F n 。01Fn?2Fn ?1Fn §2.4.4 在选优法上的应用

这时两个试验点放在 和Fn?1 两F个n?2分点上,如 果 分点比Fn?较1 好,则舍去小于 的部分F;n?如2 果 点更好,则舍Fn去?2 大于 的部分。

在留F下n?的1 部 分共 个分点,其中第Fn?1 和第 二试验点F,n?2恰 好F有n?一3 个是刚才留下来的试验可以利用。

可见在 F n 个可能试验中,最多用n-1次试

验便可得到所求的极值点 §2.4.4 在选优法上的应用(b)利用Fibonacci数列进行优选不同于 0.618法之点,还在于它适合于参数只能取整

数数值的情况.如若可能试验的数目比F n 小, 但比 Fn?1 大时,可以虚加几个点凑成 F n 个点,但新增加的点的试验不必真做,可认定比 其他点都差的点来处理。 §2.4.4 在选优法上的应用

下面给出两个定理作为这一节的结束。

定理:测试n次可将包含单峰极值点的区间

缩小到原区间的 1/Fn?1??,其中?是任意小的

正整数,n?2 §2.4.4 在选优法上的应用

证:对n用数学归纳法。n=2时,将区间 (a,b) 平分成 F2?1?2段。

在 分点(包括端点a,b)分别标上 0,1,2。在1点

的两侧取 ?,在1??与1??两点上测试,无论哪 一点较优,保留下来的区间长度均为 1??,命题成立。 §2.4.4 在选优法上的应用

假设对于n-1,命题成立

对于n,将 (a,b) 平分成 Fn?1 段,对分点(包 括端点a,b)依次标上 0,1,? ,Fn?1。

先在 Fn?1 点 与 F n 点测试,无论哪一点较优,保留下来的区 间均为 F n 段。

根据归纳假设,再做n-1次测试

(内含前两次测试之一)可将含极值点的区间

缩小到 1??段,即原区间 (a,b)的1/Fn?1??。 §2.4.4 在选优法上的应用

因 F n/F n ? 1? (5 ? 1 )/2 ? 0 .6,1 当n8 较大 时,可将相继的两个测试点取在待测区间的 0.618及1-0.618处。由(5? 1 )n?1?(5? 1 )n? 1, n?2, 2 F n 2可知,0.618法比F n 法最多多测试一次。0.618 §2.4.4 在选优法上的应用

定理:设在给定区间内有单峰极值点。如

果包含极值点在内的可测点为Fn?2 ?1个,则 测试n次必可找到极值点,n?2。

证:对n用数学归纳法。

n=2时,F2?2?1?2,命题成立 §2.4.4 在选优法上的应用

假设对于n-1,命题成立 下面证明对n命题成立。设可测试点的标号

依次是1 , 2 , ? ,F n ? ,F n ? 1 , ? ,F n ? 2 ? 1 。

先在 F n 点 及 Fn?1点测试。

无论哪一点较优,保留下来的可 测点都为 Fn?1 ?1个。

根据归纳假设,再测试n-1 必可找到极值点。

而在保留的 Fn?1 ?1个可测试 点中,有一点(F n 或 Fn?1)的测试结果下一次比

较好时正好用上,这样总测试次数为n。 §2.5 线性常系数递推关系 §2.5 线性常系数递推关系

定义 如果序列?an?满足a n ? C 1 a n ? 1 ? C 2 a n ? 2 ? ? ? C k a n ? k ? 0 ,?2?5?1?a 0 ? d 0 , a 1 ? d 1 , ? , a k ? 1 ? d k ? 1 ,?2?5?2?C1,C2,? Ck及 d0,d1,? dk?1是常数,Ck ?0,则?2?5?1?称为 ?an ?的k阶常系数线性递推关系,?2?5?2?称为?an ? 的初始条件,C ( x ) ? x k ? C 1 x k ? 1 ? ? ? C k ? 1 x ? C k称为?an?的特征多项式 §2.5 线性常系数递推关系设G(x)为{an } 的母函数 G (x )? a 0 ? a 1 x ? ? ? a n x n ? ?

根据(2-5-1),有 xk (ak ?C1ak?1 ?C2ak?2 ???Cka0) ?0 xk?1(ak?1 ?C1ak ?C2ak?1 ???Cka1) ?0 ??xn(an ?C1an?1 ?C2an?2 ???Ckan?k ) ?0 ?? §2.5 线性常系数递推关系

将这些式子两边分别相加,得到? ? k?1

G?x?? aixii?0?C1x???G?x??ki??02aixi ??????CkxkG?x??0即? ? ?? k ? 1 k ? 1 ? j1 ? C 1 x ? C 2 x 2? ? ? C kx kG ?x ??C jx j a ix ij? 0i? 0其中 C0 ?1 §2.5 线性常系数递推关系k?1k?1?j令 ? ? P?x?? Cjxj aixi,多项式 P?x? 的次j?0i?0

数不大于 k?1 。

特征多项式C ?x ?? x k ? C 1 x k ? 1 ? ? ? C k §2.5 线性常系数递推关系

因此, xkC ???1 x????1?C 1x?? ?C kxk

是 k次多项式,我们知道 C?x??0在复数域中有 k个根。设C ?x???x?a 1?k1?x?a2?k2? ?x?ai?kik1?k2?? ?ki?k §2.5 线性常系数递推关系则 xkC???1 x????1?C1x?? ?Ckxk??1?a1x?k1?1?a2x?k2? ?1?aix?ki

于是 ? 1 ? C 1 x ? ? ? C k x k ? G ? x ? ? P ? x ?

G ?x???1?C 1xP ??? x??C kxk?? ?1 ? a 1 x ?k 1 ?1 ? a P 2 ?x x ?? k 2 ? ?1 ? a ix ?k i( 2 ? 5 ? 4 ) §2.5 线性常系数递推关系(2-5-3)式是有理式,且分子的次数低于分母的

次数,有分项表示,即:G(x)?A111 ? ?1x?A12(1 ? ?1x)2???A1k1(1 ? ?1x)k1? A211??2x?A22(1 ? ?2 x)2???A2 k2(1 ? ?2 x)k2??? At11??t x?At 2(1 ? ?t x)2???Atkt(1 ? ?t x)kt §2.5 线性常系数递推关系? ?? 承上页: G(x) ?i? t1jk ? i1(1?A iijx)j( 2?5?4)?? x n的系数是数。tan?i?1

jk?i1Aij???j?n n?1???ain。Aij是常 §2.5 线性常系数递推关系

定理:设 P ( x ) 是有理分式,多项式的P(x) Q (x) P (x)

次数低于Q(x)的次数。则 Q ( x ) 有分项表示,

且表示唯一 §2.5 线性常系数递推关系证明:设 Q( x)的次数为n,对n用数学归纳 法。n=1时, P(x)是常数,命题成立。

假设对小于n的正整数,命题成立。

下面证明对正整数n命题成立。设?是 Q(x)

的 k 重根,? Q ( x ) ? ( x ? ) k Q 1 ( x )Q ,1 ( x ) ? 0 §2.5 线性常系数递推关系

不妨设 P(x)与 Q(x) 互素,设

Q P ((x x))?(x? A ?)k?(x?? P 1)(k xQ )1(x)A1Q (x)?(x??)P 1(x)?P(x) A?P(?)/Q 1(x)?0? P 1 ( x ) ? [ P ( x ) ? A 1 ( x ) / Q x ] ? () §2.5 线性常系数递推关系P(x)的次数低于Q(x) 。

根据归纳假设, P1(x)(x ??)k Q1(x)

可分项表示。

因此, P (x) Q (x)

可分项表示。由(2-5-6)式及(2-5-7)式可知表示 是唯一的。 §2.5 线性常系数递推关系

以下分别各种情况讨论具体计算的问题。

(1)特征多项式C?x?无重根设 C ? x ? ? ? x ? a 1 ? ? x ? a 2 ? ? ? x ? a k ? ?2?5?4?可见化为

G?x?? A1 ? A21 ??? Ak1?a1x 1?a2x1?akx?k?Aii?1 1?ai x?2?5?8? §2.5 线性常系数递推关系x n 的系数是 k ? an ? Aiain i?1A1,A2,? ,Ak可由线性方程组?2?5?9??A1 ? A2 ??? Ak ?d0??A1a1 ? A2a2 ??? Akak ?d1 ?????2?5?1?0??A1a1k?1 ? A2a2k?1 ??? Akakk?1 ?d 解出。 §2.5 线性常系数递推关系?2?5?1?0的系数矩阵的行列式是Vander

mond 行列式 1 1 ? 1a1 a2 ? ak ???2?5?1?1a k ?1 1a k ?1 2?a k ?1 k???ai ?ai??0 i?j

不难看出 ?2?5?1?0有唯一解。 §2.5 线性常系数递推关系

(2)特征多项式 C?x有? 共轭复根 设 a1, a是2 的C?一x?对共轭复根。??? ??? a 1 ? ? c ? i o s? , a i 2 s ? a n 1 ? (c ? i s) o iA1 ? A2 1?a1x 1?a2x

中 x n 的系数是 §2.5 线性常系数递推关系A1?1n ?A2?2n ?A1?n(co?s ?isin?)n1 ?A2?n(co?s ?isin?)n ? A1?n(cons? ?isinn?)?A2?n(cons? ?isinn?) ?(A1 ?A2)?n cosn??i(A1 ?A2)?nsinn? ?A?n cosn??B?nsinn? §2.5 线性常系数递推关系其中 A ? A 1 ? A 2 , B ? i ( A 1 ? A 2 )

在具体计算时,可先求出各对共轭复根,再 求待定系数A,B,避免中间过程的复数运算。

(3)特征多项式 C( x) 有重根设?是C(x) 的k重根,则(2-5-4)可简化为?kAii?1 (1??x)i §2.5 线性常系数递推关系? x n的系数 an?jk?1Aj???j?nn?1???an。其中??j?n?1?????j?n?1?? ? n ? ? j?1 ?

是n的j-1次多项式。

因此,a n 是? n 与n的k-1次

多项式的乘积。 §2.5 线性常系数递推关系

为了简化计算,下面引入一些记号,介绍 几个命题。设x是任意变量,n是非负整数,令

{ ?? x ?? ??n?1, 当 n?0是 , x(x? 1 )? (x? n? 1 ), 当 n? 1 时 ,n ! §2.5 线性常系数递推关系

不难证明,多项式 f( x ) ? a n x n ? a n ? 1 x n ? 1 ? ? ? a 1 x ? a 0

可用 ??x??,??x??,???x?? 唯一线性表示。其中 a k ?0? ?1? ?n?(k?0? n)是常数 §2.5 线性常系数递推关系设{an }是给定序列,令 ? a n ? a n ? 1 ? a n ,? k a n ? ? ( ? k ? 1 a n )?k an 称为 a n 的 k 阶差分。

不难证明,如果对任意的n有 ?ran ?0,则有?ri?0(?1)i???ri???an?r?i?0因而序列{an } 的特征多项式为C(x)?(x?1)r §2.5 线性常系数递推关系

不难证明,如果 ?an 是n的r次多项式,则 a n 是n的r+1次多项式。

以上几个命题作为习题,请读者自己证明。 §2.5 线性常系数递推关系

总之: (1)若特征多项式 C(x) 有n个不同零点 a1,a1,? ,an, 则递推关系(2-5-1)的解a k? l1 a 1 k? l2 a 2 k? ? ? ln a n k 其中 l1,l1,?,ln, 是待定系数,有初始条件 (2-5-2)来确定。 §2.5 线性常系数递推关系(2)若特征多项式 C( x) 有不同的复根, 可依照(1)的办法处理。

不过任意复数 a?bi

可写为 ?e i? 形式,设? 1 ? ?e i?? ?(c ?? o is? s i)n

是 C(x)的一个零点,其共轭复根为?? ?? ? 2 ?e ? i??(c? o isi s )n §2.5 线性常系数递推关系? l1k 1?l2?2k?l1?k(cok?s?isink?)?l2?k(cok?s?isink?)??k(l1?l2)coks??i?k(l1?l2)sink?

l1 ?l2 和 i(l1?l2)仍然是待定常数。即C(x)?0有一对共轭复根?1 ??ei? 和?2 ??e?i?时,递

推关系(2-5-1)的解有对应的项A ?kco k ?? sB ?ksik ?n其中A,B是待定常数。 §2.5 线性常系数递推关系(3)若C(x) k重根。

不妨设 ? 1是k的重根。则递推关系(2-5-1)的解对应于的项为? (A 0 ? A 1 n ? ? ? A k ? 1 n k ? 1 )1 n其中 A 0,A 1,? ,A k?1是k个待定常数。 §2.5 线性常系数递推关系

例1:求下列n阶行列式 的d n值。2 1 0 0 ?01 2 1 0 ?0dn ? 0 1 2 1 ? 0???

0???? 2 §2.5 线性常系数递推关系

根据行列式性质 d n ? 2 d n ? 1 ? d n ? 2 ? 0 ,d 1 ? 2 ,d 2 ? 3

对应的特征方程为 m2?2m?1?(m?1)2?0 m1?m2?1故 m?1是二重根 ? d n? (A ? B )1 ) n ( n? A ? Bn §2.5 线性常系数递推关系n?1时有 d1?A?B?2 n?2时有 d2?A ?2B?3?? ? ?A A? ?2B B? ?23?A?B?1 即 dn?n?1 §2.5 线性常系数递推关系例2:求n

Sn ? ? k k ?0 Sn?1?2?3?? ?n?1?n

Sn?1?1?2?3?? ?n?1? Sn?Sn? 1?n同理

S n ? 1? S n ? 2? n? 1

相减得 S n? 2 S n ? 1? S n ? 2? 1 §2.5 线性常系数递推关系同理 S n ? 1 ? 2 S n ? 2 ? S n ? 3? 1 ?Sn?3Sn?1?3Sn?2?Sn?3?0 S0?0, S1?1, S2?3

对应的特征方程为 m 3 ? 3 m 2 ? 3 m ? 1 ? ( m ? 1 ) 3 ? 0 §2.5 线性常系数递推关系

m?1是三重根 ? S n ? ( A ? B ? C 2 n ) 1 ) n ( n ? A ? B ? C 2 n

S 0?0 ,? A ?0 S 1? 1 , B ? C ? 0 S 2 ? 3 ,2 B ? 4 C ? 3 ,? B ? C ? 0 即 Sn?1 2n?1 2n2?1 2n(n?1) 这就证明了 1?2?3?? ?n?1n(n?1)2 §2.5 线性常系数递推关系例2:求n? Sn ? k 2 k ?0

Sn?1?22?32?? ?(n?1)2?n2

Sn? 1?1?22?32?? ?(n?1)2?Sn?Sn? 1?n2同理

S n ? 1? S n ? 2? (n? 1 )2

相减得 S n ? 2 S n ? 1 ? S n ? 2 ? 2 n ? 1 §2.5 线性常系数递推关系同理 S n ? 1 ? 2 S n ? 2 ? S n ? 3 ? 2 ( n ? 1 ) ? 1 相减得 S n ? 3 S n ? 1 ? 3 S n ? 2 ? S n ? 3 ? 2 同理 S n ? 1 ? 3 S n ? 2 ? 3 S n ? 3 ? S n ? 4 ? 2? S n? 4 S n ? 1? 6 S n ? 2? 4 S n ? 3?S n ? 4?0 S 0?0 , S 1? 1 , S 2? 5 , S 3? 14

对应的特征方程为 m 4?4m 3?6m 2?4m?1?0r4?4r3?6r2?4r?1?(r?1)4?0 §2.5 线性常系数递推关系r?1是四重根 ? S n ? ( A ? B ? C n 2 ? D n 3 )1 ) n ( n

依据 S 0 ? 0 ,S 1 ? 1 ,S 2 ? 5 ,S 3 ? 1得4 关于A、B、 C、D的连立方程组:?A ? 0 ??B ? C ? D ? 1 ??2 B ? 4C ? 8D ? 5 ??3B ? 9C ? 27 D ? 14 §2.5 线性常系数递推关系11 1 2 4 8 ? 12 3 9 27111B?1 5 4 8 ?12614 9 27 §2.5 线性常系数递推关系

已知 S n 是n的3次式,故不妨令 S n ? A ? B ? 2 1 ! n C ( n ? 1 n )? 3 1 ! D ( n ? 1 n )n ? (2 ) 确定待定系数时,比较方便,无需解一联立 方程组。例如 n ? 0 时 ,S 0? A ? 0 n ? 1 时 ,S 1 ? A ? B ? 1 ,? B ? 1 n ? 2 时 ,S 2 ? 2 B ? C ? 5 ,? C ? 3 n ? 3 时 ,S 3 ? 3 B ? 3 C ? D ? 1 , ? D 4 ? 2 §2.5 线性常系数递推关系?Sn?n?3n(n?1)?1n(n?1)(n?2)23?1n(n?1)(2n?1) 6 §2.5 线性常系数递推关系

例4:求 S n? 1 3? 2 3? ? ? n 3 解: ? S n? S n ? 1 ? 是S n n? 的( 3n 次? 1 多)3 项式,因此 是满足递推S n关系: S n ? 5 S n ? 1 ? 1 S n ? 2 ? 1 0 S n ? 3 ? 5 S 0 n ? 4 ? S n ? 5 ? 0设 Sn?A 1? ? ?1 n? ? ??A 2? ? ?n 2? ? ??A 3? ? ?n 3? ? ??A 4? ? ?n 4? ? ? §2.5 线性常系数递推关系

S1 ? 1 ? A1S2? 13?23?9?1? ?? 2?? ?1??A2 ,A2 ? 7S3?9?33?36?1?3?7? ?? 3?? ?2??A3 ,A3 ? 12

S4 ? 36 ? 43 ? 100 ? 1? 4 ? 7 ? 6 ? 12 ? 4 ? A4 , A4 ? 6 §2.5 线性常系数递推关系?Sn?? ? ?1 n? ? ??7? ? ?n 2? ? ??1? ? ?2 n 3? ? ??6? ? ?n 4? ? ? 以n=5对上面的结果验证一下

S5?10?5 03?225 ??5???7??5???12??5???6??5?? ?1? ?2? ?3? ?4? ?5?70?120?30?255 §2.5 线性常系数递推关系

例5:求 G (x)?(1?x)3(1? 1x2)1 (?x3) 中 x的n a系n 数。

解:{ a n } 的特征多项式是 (x? 1 )3 (x? 1 )x ( 2? x? 1 ) §2.5 线性常系数递推关系x?1是3重根 x??1是1重根x2?x?1?0的根是?1?3i?e?3 2?i,??1,??2?23 §2.5 线性常系数递推关系因此可设an?A?Bn?C??n?? ? D(?1)n ?2??Ecos2? ?Fsinn2?33 §2.5 线性常系数递推关系

通过做长除法,求得G(x)?(1?x)3(11 ? x2)(1?x3)?1?x?x21 ? x4?x5?x6?1? x ? 2x2 ? 3x3 ? 4x4 ? 5x5? 7x6 ? 8x7 ?10x8 ? ? §2.5 线性常系数递推关系可知a 0? 1 ,a 1? 1 ,a 2? 1 ,a 3? 1 ,a 4? 1 ,a 5? 1 ,a 6? 1 ,a 7? 1 ,a 8? 1 ,?

利用 a 0,a 1 ,a 2,a 3,a 4,a 5的值解得。A ,B ,C ,D ,E ,F 故an?A?Bn?C??n???D(?1)n ?2??Eco2s?3?Fsinn2?3 §2.5 线性常系数递推关系

通过上式,计算得 a 6? 7 ,a 7? 8 ,a 8? 1,与0 用长除法得到的结果相同。 §2.6 整数的拆分和Ferrers图像 §2.6.1 问题举例

所谓整数拆分即把整数分解成若干整数的 和,相当于把n个无区别的球放到n个无标 志的盒子,盒子允许空着,也允许放多于 一个球。

整数拆分成若干整数的和,办法 不一,不同拆分法的总数叫做拆分数。 §2.6.1 问题举例

例1:若有1克、2克、3克、4克的砝 码各一枚,问能称出那几种重量?有几种 可能方案?(1? x)(1? x2)(1? x3)(1? x4) ?(1?x?x2 ?x3)(1?x3 ?x4 ?x7) ?1?x?x2 ?x3 ?x4 ?x5 ?x6?x7 ?x8 ?x9 ?x10 §2.6.1 问题举例

从右端的母函数知可称出从1克到10克, 系数便是方案数。例如右端有 2x5项,即称 出5克的方案有25 ? 2 ? 3 ? 1 ? 4 同样, 6?1?2?3?4?210?1?2?3?4 故称出6克的方案有2,称出10克的方案有1 §2.6.1 问题举例例2:求用1分、2分、3分的邮票贴出不 同数值的方案数。

因邮票允许重复,故母函数为

G (x)?(1?x?x2?? )1 (?x2?x4?? )?(1?x3?x6?? )

以其中为例,其系数为4,即4拆分成1、 2、3之和的拆分数为4,即4 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 2 ? 1 ? 3 ? 2 ? 2 §2.6.1 问题举例

例3:若有1克砝码3枚、2克砝码4枚、4 克砝码2枚的砝码各一枚,问能称出那几种 重量?各有几种方案? §2.6.1 问题举例G(x) ? (1 ? x ? x2 ? x3 )(1 ? x2 ? x4 ? x6 ? x8 ) ? (1 ? x4 ? x8 )? (1 ? x ? 2x2 ? 2x3 ? 2x4 ? 2x5 ? 2x6 ? 2x7 ? 2x8 ? 2x9 ? x10 ? x11)(1 ? x4 ? x8 )?1? x ? 2x2 ? 2x3 ? 3x4 ? 3x5 ? 4x6 ? 4x7 ? 5x8 ? 5x9 ? 5x10 ? 5x11 ? 4x12 ? 4x13 ? 3x14 ? 3x15 ? 2x16 ? 2x17 ? x18 ? x19 §2.6.1 问题举例

例4: 整数n拆分成1,2,3,…,m的和, 并允许重复,求其母函数。如若其中m至少 出现一次,其母函数如何?

若整数n拆分成1,2,3,…,m的和, 并允许重复,其母函数为:

G 1(x)?(1?x?x2?? )1 (?x2?x4?? )? ? (1?xm?x2m?? ) §2.6.1 问题举例

G1(x) ? (1? x ? x2 ??)(1? x2 ? x4 ??)? ?(1? xm ? x2m ??)?11 ?x11 ? x2?1 1? xm?(1?x)(1?1 x2 )?(1?xm) §2.6.1 问题举例

若拆分中m至少出现一次,其母函数为: G2(x)?(1?x?x2 ??)(1?x2 ?x4 ??)? ?(xm?x2m??) ?(1?x)(1?xx2m)?(1?xm) §2.6.1 问题举例显然有 G2(x)?(1?x)1(?x12)?(1?xm) ?(1?x)1(?x21)?(1?xm?1) (2?6?1)

等式(2-6-1)的组合意义:即整数n拆分成1到 m的和的拆分数减去拆分成1到m-1的和的拆 分数,即为至少出现一个m的拆分数。 §2.6.1 问题举例

例1:若有1、2、4、8、16、32克的砝码

各一枚,问能称出那几种重量?有几种可

能方案? G(x) ? (1? x)(1? x2)(1? x4)(1? x8)(1? x16)?(1? x32)?1? x2 1? x1? 1?x4 x21? 1?x8 x41? x16 1? x81? 1?x32 x161? 1?x64 x32? ?1? x64 ? (1? x ? x2 ??? x63) ? 63 xk1? xk?0 §2.6.1 问题举例

从母函数可以得知,用这些砝码可以称 出从1克到63克的重量,而且办法都是唯一 的。

这问题可以推广到证明任一十进制数n, 可表示为? n ?a k2 k, 0 ? a k? 1 ,k? 0 k ? 0

而且是唯一的。 §2.6.2 拆分数估计式

定理:设 p n 为整数n的拆分数,则20 n

pn ? e 3 证:令 G (x )? p 0? p 1 x ? p 2 x 2? ?

一个整数n拆分成若干整数的和,在拆分 中每个整数允许重复出现。故1 G(x)?(1?x)1(?x2)1(?x3)? §2.6.2 拆分数估计式?ln G (x)??ln1? (x)?ln1? (x2) ?ln1? (x3)??

ln 1?(x)??x?1x2?1x3?? 23

ln 1?(x2)??x2?1x4?1x6?? 23 §2.6.2 拆分数估计式? ln G ( x) ? ( x ? 1 x 2 ? 1 x 3 ? ?) 23? (x2 ? 1 x4 ? 1 x6 ? ?) 23? (x2 ? 1 x4 ? 1 x6 ? ?) ? ? 23?x 1?x?1 x2 21? x2?1 31x3 ? x3??(2 ? 6 ? 2) §2.6.2 拆分数估计式xn xxn ? 11 ? xn? 1 ? x?1 ? x? x2? ? ? xn ? 1由于 1 ? x ? x 2? x 3? ? ? x n ,? 1 ? x ? x 2 ? x 3 ? ? ? x n ? 1 ? n n ? 1xx n 1x ? 1 ? x n? n ?1 ? x( 2 ? 6 ? 3 ) §2.6.2 拆分数估计式

把(2-6-3)式代入(2-6-2)式得

lnG(x)?1?xx?212?1?xx?312?1?xx???1?xx(1?212 ?312 ??)由于 1 1 1 1n2? n21? 1? 1 ? n? n?4 22 §2.6.2 拆分数估计式因而1 n2?(n1 ? 1)2???n1 ?121?1 22?1 32???1?21 ?1?5 325x ln G ( x) ? 3 ?1 ? x(2 ? 6 ? 4) §2.6.2 拆分数估计式设 x?(0,1),有G(x) ? p0 ? p1x? p2x2 ??? pnxn ??? pnxn

lnG(x) ?lnpn ?nlnx1lnpn?lnG(x)?nln x(2?6?5) §2.6.2 拆分数估计式

把(2-6-4)式代入(2-6-5)式得2 x 1 ln p n? 1 ? x ? n lx n( 2 ? 6 ? 6 )

曲线 z?lny是上凸,故曲线位于曲线z?lny

的切线下方,点(1,0)的切线为

z?y?1故有

lny?y?1 x y

§2.6.2 拆分数估计式

z?lny 0 (1,0)

图 (2-6-1) §2.6.2 拆分数估计式11 ln ? -1xx

以上式代入(2-6-5)式得:5x 1 lnpn ?3(1?x)?n(x?1)5x n(1?x)??3(1?x) x(2?6?7) §2.6.2 拆分数估计式

不等式(2-6-7)的左端 lnpn 是常数,右端 是 x的函数 ,即不等式对于 x?(0,1)成立。

右端函数取极小值时将给出较好的上界值。令5x n(1?x)y??3(1?x) x求导得5ny??3(1?x)2 ?x2 §2.6.2 拆分数估计式令 y? ?0,得(3 n ? 5 )x 2? 6 n? x 3 n ? 0

解方程,得3n? 15nx?3n?53 n ?1n53 nx 1?3 n ? 5? 1 ,x 2?3 n ?5 ? (0 ,1 ) §2.6.2 拆分数估计式因为101 2ny????3(x?1)3?x3,y?? ?0 x2

所以 x 2 是极小值。

以 x 2 的值代入 y,得 20y? n 320 n? pn ?e 3 §2.6.2 拆分数估计式

利用 1?212?212????62,上式可改进为20n?

pn ? e 3 §2.6.3 Ferrers图像

一个从上而下的n层格子, 为m 第i 层的i 格 子数,当 m i? m i ? 1 ,( ,i? 即1 ,上2 ,? 层n 的? 格1 ) 子数

不少于下层的格子数时,称之为Ferrers图 像,如图(2-6-2)示。

图 2-6-2 §2.6.3 Ferrers图像

Ferrers图像具有如下性质: 1.每一层至少有一个格子。

2.第一行与第一列互换,第二行于第二列 互换,…,即图(2-6-3)绕虚线轴旋转所得 的图仍然是Ferrers图像。

两个Ferrers 图像称为一对共轭的Ferrers图像。 §2.6.3 Ferrers图像

利用Ferrers图像可得关于整数拆分的十 分有趣的结果。(a)整数n拆分成k个数的和的拆分数, 和数n拆分成个数的和的拆分数相等。

因整数n拆分成k个数的和的拆分可用一 k行的图像表示。

所得的Ferrers图像的共 轭图像最上面一行有k个格子。例如: §2.6.3 Ferrers图像24=6+6+5+4+3 5个数,最大数为624=5+5+5+4+3+2 6个数,最大数为5

图(2-6-3) §2.6.3 Ferrers图像(b)整数n拆分成最多不超过m个数的和的 拆分数,和n拆分成最大不超过m的拆分数 相等。

理由和(a)相类似。

因此,拆分成最多不超过m个数的和的拆 分数的母函数是1 (1?x)1(?x2)? (1?xm) §2.6.3 Ferrers图像

拆分成最多不超过m-1个数的和的拆分数 的母函数是1 (1?x)1(?x2)? (1?xm?1)

所以正好拆分成m个数的和的拆分数的 母函数为 §2.6.3 Ferrers图像

所以正好拆分成m个数的和的拆分数的 母函数为1(1 ? x )(1 ? x 2 )? (1 ? x m )?(1?x )(1?1 x 2 )?(1?xm ?1 )?(1?x )(1?xm x 2 )?(1?xm) §2.6.3 Ferrers图像(c)整数n拆分成互不相同的若干奇数的和 的的拆分数,和n拆分成自共轭的Ferrers图 像的拆分数相等.设 n ? ( 2 n 1 ? 1 ) ? ( 2 n 2 ? 1 ) ? ? ? ( 2 n k ? 1 ) , 其中 n 1?n 2? ? 。 ?n k

构造一个Ferrers图像,其第一行,第

一列都是 n1 ?格1,对应于 2n,1 ?第1二行,第 二列各 n格2 ?,1对应于 。2n以2 ?此1类推。由

此得到的Ferres图像是共轭的。

反过来也 一样。 §2.6.3 Ferrers图像例如1? 9 7 ? 5 ? 3

对应为Ferrers图像为? ??9+5+3=17 图(2-6-4) §2.7 指数型母函数 §2.7.1 问题提出设有n个元素,其中元素a 1 重复了n 1 次, 元素a 2 重复了n 2 次,…,a k 重复了n k 次,n ? n 1? n 2? ? ? n k 从中取r个排列,求不同的排列数如果 n 1? n 2? ? ? n k? 1 ,则是一般的排 列问题。 §2.7.1 问题提出

现在由于出现重复,故不同的排列计 数便比较复杂。

先考虑 n个元素的全排列,

若n个元素没有完全一样的元素,则应有n! 种排列。

若考虑n i 个元素a i 的全排列数为 n i ! ,则真正不同的排列数为n! n1!n2!? nk ! §2.7.2 解的分析

先讨论一个具体问题:若有8个元素,其

中设 重a 复1 3次, 重a复2 2次, 重复a 3 3次。

从 中取r个组合,其组合数为 ,c则r 序列 c 0 ,c 1 ,c 2 ,c 3 ,c 的4 ,c 母5 ,函c 6 ,数c 7 为 G (x)?(1?x?x2?x3)1 (?x?x2)1 (?x?x2?x3) ?(1?2x?3x2?3x3?2x4?x5)?(1?x?x2?x3) ?1?3x?6x2?9x3?1x0 4?9x5?6x6?3x7?x8 §2.7.2 解的分析

从 x的4 系数可知,这8个元素中取4个组 合,其组合数为10。

这10个组合可从下面 展开式中得到(1?x1?x12 ?x13)(1?x2 ?x22)(1?x3?x32 ?x33) ?[1?(x1?x2)?(x12 ?x1x2 ?x22)?(x13?x12x2 ?x1x22)?(x13x2 ?x12x22)?x13x22] ?(1?x3?x32 ?x33) §2.7.2 解的分析承前页?1?(1?x1 ?x2 ?x3)?(x12 ?x1x2 ?x22 ?x1x3 ?x2x3 ?x33)?(x13 ?x12x2 ?x1x22 ?x12x3 ?x1x2x3 ?x22x3 ?x1x32 ?x2x32 ?x33)?(x1x33 ?x2x33 ?x12x32 ?x1x2x32 ?x22x32 ?x13x3 ?x12x2x3 ?x1x22x3 ?x13x3 ?x12x22) ?? §2.7.2 解的分析其中4次方项有 x 1 x 3 3? x 2 x 3 3? x 1 2 x 3 2? x 1 x 2 x 3 2? x 2 2 x 3 2? x 1 3 x 3 ? x 1 2 x 2 x 3? x 1 x 2 2 x 3? x 1 3 x 3? x 1 2 x 2 2 (2 ? 7 ? 2 )(2-7-2)表达了从8个元素( a1,各a33个, a 2 2个)中取4个的组合。例如 x1 x为33 一个 ,a 13个 的组a合3 , 为两x12个x32 ,两个a 1 的组合,a 3以此类推。 §2.7.2 解的分析

若研究从中取4个的不同排列总数,以 x12 x32 对应的两个两个的不同排列为例,其 不同排列数为4! ? 6 2!2! 即 a1a1a3a3, a1a3a1a3, a3a1a3a1, a1a3a3a1, a3a3a1a1, a3a1a1a3, 六种。

同样,1个a 1 3个 a 3 的不同排列数为4! ? 4 3! §2.7.2 解的分析即a1a3a3a3, a3a1a3a3, a3a3a1a3, a3a3a3a以1,此 类推。故从(2-7-2)式可得问题的解,其不 同的排列数为4!( 1 ? 1 ? 1 ? 1 ? 1 ? 1 1!3! 1!3! 2!2! 1!1!2! 2!2! 3!1!? 1 ? 1 ?1? 1) 2!1!1! 1!2!1! 3!1! 2!2!? 4!(4 ? 3 ? 3) ? 4!4? 2!?2!?3?3!?3? 2!?3!3! 2!2! 2!2!2!3!?16 ?18 ? 36 ? 70 §2.7.3 指数型母函数

为了便于计算,利用上述特点,形式地引进函数Ge(x)?(1?1x!?x22!?x3)(1?x?x2) 3! 1! 2!?(1?x?x2 ?x3) 1! 2! 3! §2.7.3 指数型母函数承上页Ge(x)?(1 ?2x?2x2?7 6x3?5 12x4?1 12x5)? (1? x ? 1 x2 ? 1 x3) 26?1? 3x ? 9 x2 ?14 x3 ? 35 x4 ?17 x5 2 3 12 12? 35 x6 ? 8 x7 ? 1 x8 72 72 72(2 ? 7 ? 3) §2.7.3 指数型母函数

从(2-7-3)式计算结果可以得出:取一个的

排列数为3,取两个的排列数为 2?9/取2? 3个9,

的排列数为3 !? ,1 取/43 4 个? 的2排8 列数

为 4 !? 3 ,/如1 5 此? 等2 7 等。

0把(2-7-3)式改写成

下面形式便一目了然了。Ge(x)?1?!13x!?29!x2?23!8x3?74!0x4?15!7x05?35x06?56x07?56x0 8 (2?7?4) 6! 7! 8! §2.7.3 指数型母函数

定义:对于序列 a0,a1,a2,?,函数Ge(x)?a0?a1 x?a2 1! 2!x2?a3 3!x3???ak xk ?? k!称为是序列 a0,a1,a2,?得指数型母函数 §2.7.3 指数型母函数

综合上述可得如下两个结论:(a) 若元素 a 1有 n 1个,元素 a 2有 n 2个, ……,元素a k 有n k 个,由此;

组成的n个元素

的排列,不同的排列总数为n! n1!n2!? nk !其中 n ? n 1? n 2? ? ? n k §2.7.3 指数型母函数(b) 若元素 a 1有 n 1个,元素 a 2有 n 2个, ……,元素a k 有n k 个,由此;

组成的n个元素 中取r个排列,设其不同的排列数为 p r。则 序列 p0,p1,? pn的指数型母函数为Ge(x)?(1?1x!?x22!???xn1n1!)?(1?x?x2 ???xn2)?(1?x?x2 ???xnk )1! 2!n2!1! 2!nk! §2.7.3 指数型母函数

与(2)中所用的方法相比,可以看出指数 型母函数在解决有重复元素的排列时的优 越性。 §2.7.4 举例

例1:求由两个a,1个b,2个c组成的

不同排列总数。

根据结论一,不同的排列总数为n? 5! ?30 2!2!1! §2.7.4 举例

例2:由1,2,3,4四个数字组成的五 位数中,要求数1出现次数不超过2次,但 不能不出现;

2出现次数不超过1次;

3出 现次数可达3次,也可以不出现;4出现次 数为偶数。

求满足上述条件的数的个数。 §2.7.4 举例设满足上述条件的r位数为 ,a序r 列a1,a2,? 的a1指0 数型母函数为Ge ( x)?(x 1!?x 2 )(1 ? 2!x)(1 ?x 1!?x2 2!?x3 ) 3!? (1 ? x 2 ? x 4 ) 2! 4!? ( x ? 3 x 2 ? 1 x 3 )(1 ? x ? x 2 ? 2 x 3223? 7 x4 ? 1 x5 ? x6 ? x7 ) 24 8 48 144 §2.7.4 举例?x?5x2 ?3x3 ?8x4 ?43x5 ?43x623 24 48?17x7? 1 x8?1 x9? 1 x10 48 288 48 288?x?5x2 ?18x3 ?64x4 ?21x55 ?64x56 1! 2! 3! 4! 5! 6!?178x75?14x08?765x90?1260x1007! 8!9!10!由此可见满足条件的5位数共215个。 §2.7.4 举例

例3: 求1,3,5,7,9五个数字组成的n位数 的个数,要求其中3,7出现的次数为偶数, 其他1,5,9出现次数不加限制。

设满足条件的r位的个数为 a r ,则序列 a1,a2,a3,?对应的指数型母函数为

G e (x )? ( 1 ? x 2 2 !? x 4 4 !? ? )2 ( 1 ? x ? x 2 2 !? x 3 ! 3? ? ) §2.7.4 举例由于e?x?1?x?x2?x3?? ), 2! 3!? 1 ?x2?x4? ? ?1(ex? e? x). 2 ! 4 ! 2Ge(x)?1(ex 4?e?x)2e3x? 1(e2x ?2?e?2x)e3x 4 §2.7.4 举例? 1 (e5x ? 2e3x ? e x ) 4? ? ? ? 1 ( ?5n xn ? 2 ?3n xn ??xn )4 n?0 n!n?0 n! n?0 n!? ? 1 ? ( 5 n ? 2 ?3 n ? 1) x n .4 n?0n!?an?1 4(5 n?2?3n?1 ). §2.8 母函数和递推关系应用举例 §2.8 母函数和递推关系应用举例

例1:下图是一逻辑回路,符号D是一延 迟装置,即在时间t输入一个信号给延迟装 置D,在t+1时刻D将输出同样的信号,符 号? 表示加法装置D输入uDD?

图 2-8-1? 输出v §2.8 母函数和递推关系应用举例

若在 t?0,1,2,? 时刻,输入信号u0,u1,?, 求相同时刻的输出信号 v0,v1,?。

显然,v 0 ? u 0 , v 1 ? u 1 ? u 0 , v 2 ? u 2 ? u 1 , v3?u 3?u 2?u 0,? 。

一般的有 v n ? u n ? u n ? 1 ? u n ? 3 ,n ? 3 . §2.8 母函数和递推关系应用举例

若信号输入的序列 u0,u1,的?母, 函数为 , 输出U(的x)信号序列 的母函v0数,v1为,?, ,则V (x)

V ( x ) ? ( 1 ? x ? x 3 ) U ( x ) ? P ( x ) U ( x )其中P(x)?1?x?x3

被装置(图 2-8-1)的特性所确定,可以 看作是该装置的传递函数,如图2-8-2U ( x)P(x)V (x) §2.8 母函数和递推关系应用举例

例2:由红球两个,白球、黄球各一个, 试求有多少种不同的组合方案。设r,w,y分别代表红球,白球,黄球。(1?r?r2)(1?w)(1? y) ?(1?r?r2)(1? y?w? yw) ?1?(r? y?w)?(r2 ?ry?rw? yw)?(r2y?r2w?ryw)?r2yw §2.8 母函数和递推关系应用举例由此可见,出一个球也不取的情况外,有: (a)取一个球的组合数为三,即分别取

红,白,黄,三种。

(b)取两个球的组合数为四,即两个红

的,一红一黄,一红一白,一白一黄。

(c)取三个球的组合数为三,即两红一

黄,两红一白,一红一黄一白。

(d)取四个球的组合数为一,即两红一黄一白。 §2.8 母函数和递推关系应用举例令取r的组合数为c,r 则序列 c0,c1,c2,c3,c4

的母函数为 G (x)?(1?x?x2)1 (?x)2 ?1?3x?4x2?3x3?x4

共有1+3+4+3+1=12种组合方式。 §2.8 母函数和递推关系应用举例

例3:n个完全一样的球放到m个有标 志的盒子中,不允许有空盒,问共有多少 种不同的方案?其中n?m由于不允许有空盒,令n个球放到m个有 标志的盒子的方案数为a n,序列 {a对n }应的母函数为 。

G则(x) G(x)?(x?x2?? )x(?x2?? )? (x?x2?? )?(1? xm x)m §2.8 母函数和递推关系应用举例

因 (1?x)m?1?mx?m(m?1)x2 2!?m(m?1)(m?2)x3 ?? 3!故二项式 (1?x)?m中 xn?m 项系数为

m (m ? 1 )? (m ? n ? m ? 1 )? m (m ? 1 )? (n ? 1 )(n ? m )!(n ? m )! §2.8 母函数和递推关系应用举例即 C (m ? (n ? m )? 1 ,n ? m )? C (n ? 1 ,n ? m ) ? C (n ? 1 ,m ? 1 ) §2.8 母函数和递推关系应用举例

例4:某单位有8个男同志,5个女同志, 现要组织一个有数目为偶数的男同志和数 目不少于2的女同志组成的小组,试求有多 少种组成方式。令 为a n 从8位男同志中抽取出n个的允许组 合数。由于要男同志的数目必须是偶数, 故 a 1 ? a 3 ? a 5 ? a 7 ? 0 , a 0 ? 1 , a 2 ? C ( 8 , 2 ) ? 2 , a 4 ? C ( 8 , 4 ) ? 7 , a 6 ? C 0 ( 8 。

, 6 ) ? 2 , a 8 ? 1 8 §2.8 母函数和递推关系应用举例故数列 a0,a1,a2,对? 应,a8 一母函数 A ( x ) ? 1 ? 2 x 2 ? 8 7 x 4 ? 0 2 x 6 ? 8 x 8

类似的方法可得女同志的允许组合数对应的 母函数位B ( x )? 1 x 2 ? 0 1 x 3 ? 0 5 x 4 ? x 5 §2.8 母函数和递推关系应用举例C(x) ? A(x)B(x) ? (1? 28x2 ? 70x4 ? 28x6 ? x8) ?(10x2 ?10x3 ?5x4 ? x5) ?10x2 ?10x3 ? 285x4 ? 281x5 ?840x6 ? 728x7 ? 630x8 ?350x9 ?150x10 ? 38x11 ? 5x12 ? x13 §2.8 母函数和递推关系应用举例C中(x)项的x k系数 为符c合k 要求的 个人组k成 的小组的数目,总的组成方式数目为1? 0 1? 0 28 ? 25? 8814 ? 702 ? 6830 ? 35 ? 105 ? 30 ? 8 5? 1? 3328 §2.8 母函数和递推关系应用举例

例5:10个数字(0到9)和4个四则运算

符 (?,?,?组,?)成的14个元素。

求由其中的n个

元素的排列构成一算术表达式的个数。

因所求的n个元素的排列是算术表达式,故从左向右的最后一个符号必然是数字。

而 第n-1位有两种可能,一是数字,一是运算 符。如若第n-1位是十个数字之一,则前n1位必然构成一算术表达式。 §2.8 母函数和递推关系应用举例如若不然,即第 n?1位是4个运算符之一, 则前 n?2位必然是算术表达式。

根据以上 分析,令a n 表 n个元素排列成算术表达式的个数。则an?1a 0 n? 1?4a 0 n? 2,(-2 8-1)a 1?1,0a2?12 . 0a2 ?120指的是从0到99的100个数,以及 ? 0, ?1,? ,?9. §2.8 母函数和递推关系应用举例

利用递推关系(2?8?1),得a0?1. 2

特征多项式 x2?1x0?4。

0它的根是x?5?6.5an?A(5?6)5 n?B(5?6)5 n,

解方程 ???A?B?12, ??(5? 65)A?(5? 65)B?10, §2.8 母函数和递推关系应用举例得?A?(15? 65)/4 65, ??B??(15? 65)/4 65.?an? 1 [1( 5? 4 6565)(5?65)n?(15? 65)(5? 65)n]. §2.8 母函数和递推关系应用举例

例6:设有n条封闭的曲线,两两相交于两 点,任意三条封闭曲线不相交于一点。

求 这样的n条曲线把平面分割成几个部分?设满足条件的n条封闭

曲线所分割成的域的数目为a,n 其中 n条?封1闭曲线 所分割成的域的数目为 a n?1

图 2-8-3 §2.8 母函数和递推关系应用举例

第n条封闭曲线和这些曲线相交于 2(n?个1)点,

这 个2(点n?把1)第n条封闭曲线截成2(n?条1)弧,每条弧把 2个(n域?1中) 的每个域一分为二。故新增加的域数为2(n?1).a n ? a n ? 1 ? 2 ( n ? 1 ) a 1 , ? 2 . ( - 8 2 - 2)

利用递推关系(2-8-2)得 a0 ?2. §2.8 母函数和递推关系应用举例设an?A0?A1n?A2?? ?n 2?? ?,a0 ? 2 ? A0a1 ? 2 ? 2 ? A1, A1 ? 0,a2 ? 4 ? 2 ? A2, A2 ? 2,?an?2?2 ?? n ?2?? . ? §2.8 母函数和递推关系应用举例

另解:利用欧拉公式 点数+域数-边数=2

点数=2 ?? n ?? , ?2?

边数=2?点数

域数= 4??n???2??n???2?2?2??n??.?2? ?2??2? §2.8 母函数和递推关系应用举例

例7:平面上有一点P,它是n个域D 1,D 2,? ,D n 的共同交界点,见图2?8? 现4

取k种颜色对这n个域进行着色, 要求相邻两个域着的颜色不同。Dn D1

试求着色的方案数。 令a n表示这n个域的着色Dn??1 PD2 D3方案数。

无非有两种情况:

图 2-8-4 §2.8 母函数和递推关系应用举例

(1)D 1 和 Dn?1有相同的颜色;

(2)D 1 和Dn?1所 着颜色不同。

第一种情形, 域有 k?1种颜 色可用,即D1,Dn?1域所用颜色除外;

而且从 D 1 到Dn?2的着色方案,和 n?2个域的着色 方案一一对应。

后一种D n 域有k?2种颜色 可供使用;

而且从 D 1 到 Dn?1的每一个着色 方案和 n?1个域的着色方案一一对应。 §2.8 母函数和递推关系应用举例? a n? (k? 2 )a n ? 1? (k? 1 )a n ? 2 , (-2 8 -3) a 2? k(k? 1 )a ,3? k(k? 1 )k (? 2 ).

利用(2-8-3)得 a1?0,a0?k. (2-8-3)的特征方程为x2 ?(k ?2)x?(k ?1) ?0,x1 ?k ?1, x2 ??1. an ? A(k ?1)n ?B(?1)n. §2.8 母函数和递推关系应用举例

解方程 ?A?B?k, ??(k?1)A?B?0.(2?8?4)得 ?A?1, ??B?k?1. ? an ?(k?1)n ?(k?1)(?1)n, n?2. a1 ?k. §2.8 母函数和递推关系应用举例

例8:求下列行列式(n行n列)1 1 0 0?0 0?1 1 1 0?0 dn ? 0 1 1 1 ? 00 0? ???n行? ? ?? ? ? ? ?0 0 0 0 ? 1 1 ?? §2.8 母函数和递推关系应用举例

利用行列式展开法,沿第一行展开得

d n ? d n ? 1 ? d n ? 2 ,d 1 ? 1 ,d 2 ? 0 . (- 8 2 - 5)

利用(2-8-5)式得 d0 ?1, 特征方程是 x2?x?1?0

解方程,得x?1?3i??i?e 3 .2 §2.8 母函数和递推关系应用举例设 解方程??dn?Aco n3s?Bsinn 3,???Acos0( ??3)?Bsin0( ??3) ?1????A(12)?B(3) ?1 2 §2.8 母函数和递推关系应用举例得??A?1???B?1 3?dn?cosn?? ?31 sinn??,33n?1. §2.8 母函数和递推关系应用举例

例9:求n位2进制最后三位出现010图象的数 的个数。

对于n位2进制数 b1b2? 从bn左而右进行扫 描,一当出现010图象,便从这图象后面一 位从头开始扫描,例如对11位2进制数 00101001010从左而右的扫描结果应该是 2-4,7-9位出现010图象,即

0011001100 §2.8 母函数和递推关系应用举例

而不是4-6,7-9位出现的010图象,即不是

00011000110 为了区别于前者起见,我们说4-6,9-11 位是010,但不是“出现010图象”,这作 为约定。

为了找出关于数列 a的n 第推关系,需对满 足条件的数的结构进行分析。由于n位中除 了最后三位是010已确定,其余n?3位可取0 或1: §2.8 母函数和递推关系应用举例? ? ? 0 1 0 故最后3位是010的n位2进制数的个数是2n?3 。

其中包含最后3位出现010图象的以及在n?4位 到第 n?位2出现010图象,而在最后3位并不出

现010图象的两类数,后一种数为 ? ? ? ? ? 01010 §2.8 母函数和递推关系应用举例故有an?an?2?2n?3, n?5, (2-8-6)a3?1, a4?2. 利用(2-9-6)推得 a2?0, 特征方程为a1?0,a0?1 2.(x ? 2)(x2 ?1) ? 0.?? ix1 ? 2, x2,3 ? e 2 . §2.8 母函数和递推关系应用举例? ? 设 a n? A cn o ?2 )s ? B ( sn i?2 n )? C (?2 n ,解方程组? ?A?C?1, 2? ?B?2C?0,? ??A?4C?0.? §2.8 母函数和递推关系应用举例得? ?A?2 5,?? ?B???1 5,? ??C?1 10.? ? ? a n ? 5 2 cn o ?2 ) ? s 1 5 s( n i ?2 ) n ? 1 1 ? ( 2 n 0 ,n ? 3 . §2.8 母函数和递推关系应用举例

例10:求n位的2进制数中最后三位才第一次 出现010图象的数的个数。

即求对n位2进制数 b1b2? 从左bn而右扫描, 第一次在最后三位出现010图象的数的个数。

自然,最后三位除外任取连续三个都不会 是010的。

设 表a满n 足条件的n位数个数,和前例类似, 最后三位是010的n位2进制数共 个2,n?3 §2.8 母函数和递推关系应用举例

对这 2n?3个数分析如下。

(a)包含了在最后三位第1次出现010图象的

个数,其个数为 a n,排除了在第 (n到?4第) (n?2) 位第1次出现010图象的可能。

(b)包含了在第(n?到4)第 (n位?第2)1次出现 010图象的数,其个数为an?2 .? ? ? 0 1 0 1 0 §2.8 母函数和递推关系应用举例

(c)包含了在第(n?5)位到第 (n?3)位第1 次出现010图象的数,其个数是a n ?3 .? ? ? 0 1 0 0 1 0 §2.8 母函数和递推关系应用举例

(d)包含了在第(n?6)位到第(n?4)位第12an?4

次出n?现3010图象的数,其个数是 ,因在

第 位(打*号的格)可以取0或1两种状态。? ? ? 0 1 0 ? 0 1 0 §2.8 母函数和递推关系应用举例

一般可以归纳为对 k?3,从第(n?k?2)位 到第 n?k位第一次出现010图象的数,其数 目为 2k?3a。n?k从第 位n到?k第 位中n?间3 的 k?位3可以取0,1两种值,故有 2种k?3状态。

0 1 0 ? ? ? 0 1 0 §2.8 母函数和递推关系应用举例故得递推关系如下: a n? a n ? 2? a n ? 3? 2 a n ? 4? ? ? 2 n ? 6 a 3? 2 n ? 3 ,n ? 6a 3? 1 ,a 4? 2 ,a 5? 3 . n?5时有下面几种状态:(-2 8 -7)

0001100 ,01,110 .010

排除了01010,因从左而右扫描时01010属于 前

三位出现010图象的。 §2.8 母函数和递推关系应用举例

请注意,递推关系(2-8-7)式不是常系 数递推关系。a 3 ? 1 ,a 4 ? 2 ,a 5 ? 3 . 故 n?6时有a 6 ? a 4 ? a 3 ? 2 3 , ? a 7 ? 8 ? a 4 ? a 3 ? 5 . n?7时有 a 7 ? a 5 ? a 4 ? 2 a 3 ? 2 4 , a 7 ? 1 ? a 5 ? a 6 4 ? 2 a 3 ? 9 . 其它依此类推。 §2.8 母函数和递推关系应用举例令 A ( x ) ? 1 ? 2 x ? 3 x 2 ? a 6 x 3 ? a 7 x 4 ? ? x3:a6 ?a4 ?a3 ?23 x4:a7 ?a5 ?a4 ?2a3 ?24 x5:a8 ?a6 ?a5 ?2a4 ?22a3 ?25? ) ? ? ? ? ? ? [A (x)? 1?2x? 3 x2]?x2[A (x)? 1 ] ?(x3?2x4?2 2x5? ? )A (x)?2 3x31?2x. §2.8 母函数和递推关系应用举例整理得(1?x2 ? x3 )A(x)? 23x3 ?1?2x?4x2.1?2x1?2x1?2x?x2 ?2x3 ?x3 A(x)?23x3 ?1?4x2 ?4x2 ?8x31?2x1?2x? 1. 1?2x §2.8 母函数和递推关系应用举例?A( x)? 1?2x1 ? x2?x3?1?2x?3x2?53?9x4 ?16x5 ?28x6 ?49x7 ??? a3 ?1, a4 ? 2, a5 ?3, a6 ?5, a7 ?9, a8 ?16, a9 ? 28, a10 ? 49, ?? §2.8 母函数和递推关系应用举例

例11:解图2?8? 电5路网络中的 v j , j?0,1 ,2,设? 其,n.中 v(t)?v.

v n 4v n ?1 4vn?2 v j ? 2 4v j ?1 4 v j v 2 4 v 1 4 v 0v(t)2 22 2 22 2 2 §2.8 母函数和递推关系应用举例

v j?2 i j?1 v j?1 i j v j14222

图 2-8-5

图2?8?5根据欧姆定律有 4ij?1 ?vj?2 ?vj?1, 4ij ?vj?1 ?vj. §2.8 母函数和递推关系应用举例?ij?1?14(vj?2?vj?1), ij ?14(vj?1?vj).( 2?8?8)由于各点的电流代数和为零,? ij? 1? ij? 1 2 vj? 1 .(-2 8 -9) §2.8 母函数和递推关系应用举例(2?8?8)代入 (2-8-9)得递推关系1 4 v j? 2? v j? 1? 1 4 v j? 0 ,(2 ? 8 ? 1)0

或 v j ? 2 ? 4 v j ? 1 ? v j? 0 ,j ? 0 , 1 , 2 , ? , n ? 2 .由 v 0 点的电流代数和为零,可得1 4(v1?v0)?1 2v0,? v1 ? 3v0. §2.8 母函数和递推关系应用举例

特征方程是 x2?4 x? 1?0 .x?2? 3设

v n ? A ( 2 ? 3 ) n ? B ( 2 ? 3 ) n ,解方程组?A?B?v0, ? ?(2?3)A?(2?3)B?3v0. §2.8 母函数和递推关系应用举例得? ??A?1 (1 ? 233)v0? ??? B??213(1?3)v0?vn?v0 [(1 ? 233)(2 ?3)n? (1 ? 3)(2 ? 3)n ]. §2.8 母函数和递推关系应用举例

例12:求图2-8-6所示的n级网络的等效电阻 。R n 所谓等效电路,相当于图2-8-6中虚线所

包围的块用一电阻 取R 代n ,使在两端点 和n 之n? 间的效果一样。n RRRRnR RRRR Rn?RRRR

图 2-8-6Rn n? §2.8 母函数和递推关系应用举例R n可以作为由 Rn?1等效电阻如图2?8?7所示

的方式串并联构成的. RRR n ?1R

图 2-8-7 §2.8 母函数和递推关系应用举例? 1 ?1? 1 ?2R?Rn?1?R Rn R 2R?Rn?1 R(2R?Rn?1)? 3R?Rn?1 .得递推关R系(2如R下?Rn?1)Rn?R(2R?Rn?1) 3R?Rn?1(2-8-11)R1 ?R,R2?3R. 4 §2.8 母函数和递推关系应用举例令 因此Rn?a bnn, a1?R, b1?1,an bnR(2R?an?1)?bn?1 3R?an?1?2R2bn?1 ?Ran?1. 3Rbn?1 ?an?1bn?1 §2.8 母函数和递推关系应用举例令 ? ?an?2R 2bn? 1?Rn? a 1, ?bn?3Rn? 1 b?an? 1.(2?8?1)2

将 a n? 1?b n?3 Rn? 1 b代入 a n?2 R 2 b n ? 1?Rn ? 1 a , 得到bn?1?3Rnb?2R2bn?1?R(bn?3Rnb?1), bn?1?4Rnb?R2bn?1?0.b2?4R, b0?0. §2.8 母函数和递推关系应用举例 特征方程是 x 2? 4 R? R x 2? 0x?(2?3)R , b n?[A (2?3)n?B (2?3)n]R n.解方程组?A?B?0, ? ?(2?3)A?(2?3)B?1R. §2.8 母函数和递推关系应用举例得? ??A?21 3R,?? ??B??21 3R.?bn?Rn?1[(2? 233)n?(2?3)n],an ?bn?1?3Rnb §2.8 母函数和递推关系应用举例? Rn [( 3?1)(2? 3)n 23 ?( 3?1)(2? 3)n].an?( bn3?1)2 (? (2?3)n?( 3?1)2 (? 3)n?(2? 3)n3)n?R? n? ?( 3?1)R. §2.8 母函数和递推关系应用举例

例13:设有地址从1到n的单元,用以纪录 一组信息。

这个信息的每个元素都占用两个 单元,而且存放的地址是完全随机的,因而 可能出现两个存放信息单元之间留下 一个空单元无法存放其他信息,求这n各单 元留下空单元的平均数。 §2.8 母函数和递推关系应用举例设这个平均数为 a n 。12

i+1 i+2n-1 n

存储单元如上图,设某一信息占用了第i+1, i+2两个单元,把这组单元分割成两个部分, 一是从1到i,另一从i+3到n。由于用相邻两 个单元的几率相等, §2.8 母函数和递推关系应用举例?an?n1?1[a (0?an?2)?(a1?an?3) ?? ?(an?2?a0)],n ? 2? (n? 1 )a n? 2a k(2? 8 ? 1)3k? 0

(2-8-13)式是变系数递推关系,可改为(n?1)an?(n?2)an? 1?2an?2?0,a0?0,a1?1 ,a2?0. §2.8 母函数和递推关系应用举例设 G (x)?a1?a3x2?a4x3?a5x4?? , G ?(x)?2a3x?3a4x2?4a5x3?? , x : 2a3 ? a2 ? 2a1, x2 : 3a4 ? 2a3 ? 2a2 , x3 : 4a5 ? 3a4 ? 2a3, _ ?) ??_ ?_ ? _ _ _ _ _ _ G ?(x)?xG ??2x.G §2.8 母函数和递推关系应用举例? (1 ?x)G ??2 x,G G ??2x??2?2, G1?x 1?x lG n ? ? 2 x ? l1 n ? x ) ( ? 2? C , G ?k? e 2x(1?x)?2 G x ? 0? a 1? 1 , k? 1 . §2.8 母函数和递推关系应用举例

G ? e?2x (1? x)?2? [1? 2x ? (2x)2 ? (2x)3 ??] 2! 3!?1? x2 ? 2 x3 ? x4 ? 4 x5 ??315 §2.8 母函数和递推关系应用举例一般有an?1?(n?1)?2n?22 2!(n?1)?23 3!(n?2)??? (?1)n 2n n!? ? n (?1)k 2k (n ? k ?1).k?0k! §2.9 排错问题 §2.9 排错问题n个有序的元素应有 n!个不同的排列,如若一个排列使得所有的元素在原来的位 置上,则称这个排列为错排;有的叫重排。

以1,2,3,4四个数的错排为例,分 析其结构,找出规律性的东西来。 §2.9 排错问题1 2的错排是唯一的,即2 1。

1 2 3的错排有3 1 2,2 3 1。这二者

可以看作是1 2错排,3分别与1,2换位而 得的。即23 1 232 13 13 §2.9 排错问题1 2 3 4的错排有 4 3 2 1,4 1 2 3,4 3 1 2, 3 4 1 2,3 4 2 1,2 4 1 3, 2 1 4 3,3 1 4 2,2 3 4 1。

第一列是4分别与1,2,3互换位置,其 余两个元素错排,由此生成的。 §2.9 排错问题

第2列是4分别与3,1,2(123的一个 错排)的每一个数互换而得到的。即34 1 2 433 14 2 413 1 42 24 §2.9 排错问题

第三列则是由另一个错排231和4换位而得 到,即2 4 3 1 4 22 341 432 3 14 14 §2.9 排错问题

上面的分析结果,实际上是给出一种产 生错排的结果。设n个数1,2,…,n错排的数目为D n , 任取其中一数 i,数 i分别与其他的n-1个数 之一互换,其余n-2个数进行错排,共得 (n?1)D 个n? 错2排。

另一部分位数 以外i 的n-1个 数进行错排,然后 与其中i 每个数互换得 个错排(n。?1)Dn?1 §2.9 排错问题

综合以上分析结果得递推关系Dn?(n?1)D (n?1?Dn?2), D1?0,D2?1, (2-9-1)?D0?1. §2.9 排错问题

(2-9-1)是一非常系数的递推关系,下面提

供一种解法。?Dn?nD n?1??[Dn?1?(n?1)Dn?2]?(?1)2[Dn?2?(n?2)Dn?3]???(?1)n?1(D1?D0) 由于 D 1?0,故D 0得?关1,于 得递推D n关系D n ? n n ? 1 D ? ( ? 1 ) n .( 2 ? 9 ? 2 ) §2.9 排错问题令 G e(x )? D 0 ?? D 1 ?x? D 2 ! 2 ?x 2? D 3 ! 3 ?x 3? ? ? D1? ? D 0? ? ( ? 1)1 D 2? ? D1? ? ( ? 1) 2 D 3? ? D 2? ? ( ? 1) 3 ? §2.9 排错问题可得

G e(x )? xe( G x )? e ? xGe(x)?1e??xx?(1?x?x22!` ??)/(1?x).?Dn?(1?1?1???1)?n! 2! n! §2.10 Stirling数 §2.10 Stirling数

前面见到的递推关系都是一个参数的。St

irling数问题则不然。

它导出的递推关系式

是两个参数的。

(1)多项式系数n个有区别的球放到两个有区别的盒子里,

若要求第1个盒子放k个球,第二个盒子放n-k (k?0 ,1 ,2 ,? ,n ),个球

方案数应是(x1?x2)n 中 §2.10 Stirling数x1k x2n?k项的系数C(n,k).依据加法法则有 C ( n , 0 ) ? C ( n , 1 ) ? ? ? C ( n ,n ) ? 2 n .

可把上面的讨论推广到n个有区别的球放到m

个有区别的盒子里,要求m个盒子放的球数

分 n 1 , n 2 , ? , n m ( n ? n 1 ? n 2 ? ? ? n m )别是的情况,

其不同方案数用 §2.10 Stirling数?n?? ?n1n2?nm? ?表示。

从n个有区别的球中取出n 1 个放到第1个 盒子里去,其选取方案数为 ?? n ;?? 当第1个? n1 ?

盒子的 n 个2 球选定后,第2个盒子里的 n个3 §2.10 Stirling数

球则是从 n?个n1中选取的,其方案数应为?? n ? n;1 ??第3个盒子的 个n球3 则是从 n?n1?n2?中n 选2 取?,其方案数为??n ? n1 ?;n依2 ??此类推,? n3?

根据乘法法则可得 §2.10 Stirling数???nn1n2?nm???????nn1??????nn2?n1??????nn3?n1?n2?? ????n?n1?n2 ???nm?1???nm? §2.10 Stirling数? n!(n ? n1 )!n1!( n ? n1 )! n 2!( n ? n1 ? n 2 )!? (n ? n1 ? n 2 )! ? n3!( n ? n1 ? n 2 ? n3 )!? nm! ?n! .n m !0! n1! n 2 !? n m ! §2.10 Stirling数n个有区别的球,放到m个有标志的盒子 的 问题,也可以考虑把n个有区n 别1 的球进行全排列。

对于每n 2 一个排列依次取 个放到第1个盒n 3子里,取 个放到第2个盒子里,…,最后 个放到第m个盒子里。

然而,放到盒子里的

球 不考虑球的顺序,故得不同的方案数为 §2.10 Stirling数n! . n1!n2!?nm! 结果和 (2?10 ?1)式一致。称?? ?n n1n2?nm?? ?

为多项式系数。 §2.10 Stirling数(x1?x2???xm)n?(x1?x2???xm) ?(x1?x2???xm)? ?(x1?x2???xm) (2-10-2)

多项式(x 1?x2? ? ?xm )n的展开式是由 (2-10-2)式右端的n项中,每项各取一个元 素相乘而得到的。 §2.10 Stirling数

表达式(2-10-2中) 共有n个因子项,令第i 个因子项对应于第i个有标志的球,从第i个 因子项中取 对应于把第i个有标志的球放到 第i个盒子。

(2-10式-2展)开的一般项x 1 n 1 x 2 n 2 ? x m n m ? ( n 1 ? n 2 ? ? ? n m ? n ) 表示第一个盒子有n 1个球,第二个盒子有 n 2 个球,等等。

因此 (2-10式-2中) x1n1x2n2?xm nm §2.10 Stirling数

项的系数应为?n???? n1n2 ?nm ?? 即(x1?x2?? ?xm)n?n1?n2?? ?nm?n???n n1n2? nm????x1n1x2n2? xm nm. (2?10 ?3) §2.10 Stirling数

定理:(x 1?x2? ? ?xm )n 展开式的项数等于?? n ? m ?1??, ,而且这些系数之和等于 m n?n?证明:(x 1?x2? ? ?xm )n 展开式中的 x1n1x2n2?xm nm项( n 1 ? n 2 ? ? ? n m ? n ) 和从m个

元素 x1,x2,? ,xm中取n个作允许重复的组合 一一对应。故得 (x 1?x2? ? 展? 开xm 式)n的 §2.10 Stirling数

项数等于?? n ? m ?1?? 。

从m个中取n个作允许重 ?n?

复的组合的全体,对于每个球都有m个盒子 可? 供选择,根据? ?乘n法法则? ? 有?m n. (-2 1-0 4)n 1? n 2? ? ? n m ? n?n 1 n 2? n m ? §2.10 Stirling数(2)Stirling数 只准备讨论其中的第二类Stirling数,至 于第一类的Stirling数只准备给出它的定义 和递推关系. 定义: [x]n ?x(x?1)(x?2)?(x?n?1)?s(n,0)?s(n,1)x?s(n,2)x2?? ?s(n,n)xn. §2.10 Stirling数称 s (n ,0 )s ( ,n ,1 ),s ,(n ,n )为第一类Stirling数 [x]n?1?[s(n,0)?s(n,1)x?? ?s(n,n)xn]x(?n)?s(n?1,0)?s(n?1,1)x?? s(n?1,n?1)xn?1,显然有

s ( n ? 1 , k ) ? s ( n , k ? 1 ) ? n ( n , k ) s ( 2 ? . 1 ? 5 ) 0 §2.10 Stirling数

定义: n个有区别的球放到m个相同的盒子

S(n,m)

中,要求无一空盒,其不同的方案数用

表示,称为第二类Stirling数.例如红,黄,蓝,白四种颜色的球,放到两个

无区别的盒子里,不允许有空盒,其方案有如下七种: §2.10 Stirling数1234567 第 1 盒 子r y b w ry rb R w 第 2 盒 子 y b wrb wry wry b b wy w y b其中r表红球,y表黄球,b表蓝球,w表白球, ?S(4,2)?7. §2.10 Stirling数

定理: 第二类Stirling数 S(有n,k下)列性 质:(a)S(n,0)?0,(b)S(n,1)?1,(c)S(n,2)?2n?1?1, (d)S(n,n?1)?C(n,2),(e)S(n,n)?1. 证明:公式(a),(b),(e)是显然的,只证(c), (d). §2.10 Stirling数(c)设有n个不相同的球 b1,b2,b3,从? 中,bn 取, 出球 b 1 ,其余的 n个?球1,每个都有与 同盒 ,或不与 b同1 盒两种选择.但必须排除一种情 况,即全体与 b同1 盒,因这时另一盒将是空盒. 故实际上只有 2n?1?种1方案,即 S(n,2)?2n?1?1 §2.10 Stirling数(d)n个球放到 n个?1盒子里,不允许有一空

盒,故必有一盒有两个球,从n个有区别的球中 取2个共有C(n,种2)组合方案.

定理: 第二类Stirling数满足下面的递推 关系, S ( n ,m )? m ( n ? 1 S ,m )? S ( n ? 1 ,m ? 1 )( 2 ,? 1? 6 0 )( n ? 1 ,m ? 1 ). §2.10 Stirling数

证明: 设有n个有区别的球 b1,b2,从? ,bn, 中取一个球设为b 1.把n个球放到m个盒子无一 空盒的方案的全体可分为两类。

(a) 独b 1 占一盒,其方案数显然为 S(n?1,m ?1).

(b) 不b 1独占一盒,这相当于先将剩下 的 n?个1球放到m个盒子,不允许空盒,共 §2.10 Stirling数

共有S(n?1,种m不) 同方案,然后将 球放b 1 进其中一盒,从乘法法则得 b 不1 独占一盒的 方案数应为 m(n S?1,m ).

根据加法法则有 S ( n , m ) ? S ( n ? 1 , m ? 1 ) ? m ( n ? 1 , m ) S .

上面证明递推公式 (2?1的? 0 过6程) ,

也就是给出构造所有方案的办法。例如今将 §2.10 Stirling数

红、黄、蓝、白、绿五个球放到无区别的两 个盒子里。

S ( 5 , 2 ) ? 2 S ( 4 , 2 ) ? S ( 4 , 1 ) ? 2 ? 7 ? 1 ? 1 , 5故共有15种不同的方案。

先把绿球取走,余下的四个球放到两个

盒子的方案已见前面的例子。

和前面一样用 r,y,b,w分别表示红,黄,蓝,白球,绿 球用g表示,故得表2?1? 0 1 §2.10 Stirling数

表 2-10-1g不 独 占 一 盒g独 占 一 盒

第 1盒 子第 2盒 子第 1盒 子第 2盒 子第 1盒 子第 2盒 子rgybwrybw ggrybwygrbwyrbw gbgrywbryw gw grybwrybgrygbwrybw grbgywrbyw grw gybrwybg §2.10 Stirling数n个球放到m个盒子里,依球和盒子是否有23 ?8

区别?是否允许空盒?共有 种状态。

其方案计数分别列于下表。

? n个球有区别,m个盒子有区别,有空盒时

方案计数为 m n? n个球有区别,m个盒子有区别,无空盒时

方案计数为 m !S(n,m ) §2.10 Stirling数? n个球有区别,m个盒子无区别,有空盒时 方案计数为

S(n,1) ? S(n,2) ??? S(n,m), n?m

S(n,1) ? S(n,2) ??? S(n,n), n?m §2.10 Stirling数? n个球有区别,m个盒子无区别,无空盒时

方案计数为 S(n,n)? n个球无区别,m个盒子有区别,有空盒时

方案计数为 C (n ? m ? 1 ,n ) §2.10 Stirling数? n个球无区别,m个盒子有区别,无空盒时 方案计数为C(n?(n?m)?1,n?m) ?C(n?1,n?m) ?C(n?1,m?1) §2.10 Stirling数? n个球无区别,m个盒子无区别,有空盒时 方案计数为

G (x)?(1?x)1 (?x1 2)? (1?xm ) 的 x n 项系数。 §2.10 Stirling数? n个球无区别,m个盒子无区别,无空盒时 方案计数为

G (x)?(1?x)1 (?x x2 m )? (1?xm ) 的 x n 项系数。 §2.10 Stirling数

利用S ( n , m ) ? S ( n ? 1 , m ? 1 ) ? m ( n ? 1 , m ) S , S (n ,1 )? S (n ,n )? 1 ,还可以如Pascal三角形 一样得到表2-10-3。

表 2-10-3见书119页。 §2.11 Catalan 数 §2.11 Catalan 数

这一节讨论Catalan数,其递推关系是非 线性的,许多有意义的计数问题都导致这样 的递推关系.本节将举出一些,后面还将见到. 一个凸n边形,通过不相交于n边形的对角 线,把n边形拆分成若干三角形,不同拆分的 数目用 表之.hn §2.11 Catalan 数例如五边形有如下五种拆分方案,故 hn ?5.

图 2-11-1 §2.11 Catalan 数1.递推关系 定理: (a) hn?1?h2hn?h3hn?1???hnh2, (2?11?1) (b) (n?3)hn?n2(h3hn?1?h4hn?2???hn?2h4?hn?1h3).(2?11?2) §2.11 Catalan 数证明: (a ) 的证明: 如图 2? 1? 1 1所示, 以 v1vn?1 作为一个边 的三角形 v1vkvn?1 , v n ?1 将凸 n?1边形分割

成两部分,一部分是 k边形,v2v1k边形 v 3n?k?2边形v kvn

图 2-11-2 §2.11 Catalan 数

另一部分是 n?k?2边形,k?2 ,3 ,? ,n ,即v k 点可以是 v2,v3,? ,vn点中任意一点。

依据加 法法则有n? hn?1? hkhn?k?2 k?2 ?h2hn?h3hn?1???hn?1h3?hnh2. §2.11 Catalan 数(b ) 的证明:如图 2? 1? 1 3所示,

从 v 1 点向其它n?3个 顶点{v3,v4,? ,vn?1} v 1 可引出 n?3条对角线。

对角线 v1vk 把 n边形 分割成两个部分,因此v2k边形 n?k?2边形v kvn

图 2-11-3 §2.11 Catalan 数

以 v1vk对角线作为拆分线的方案数为 hkhn?k?2 v k 可以是v3,v4,? ,vn?1 中任一点,对所有这

些点求和得 h 3 h n ? 1 ? h 4 h n ? 2 ? ? ? h n ? 2 h 4 ? h n ? 1 h 3 .

以 v2,v3,? ,vn取代 v 1 点也有类似的结果。但

考虑到对角线有两个顶点,同一对角线在两 个顶点分别计算了一次, §2.11 Catalan 数

作 n 2 ( h 3 h n ? 1 ? h 4 h n ? 2 ? ? ? h n ? 2 h 4 ? h n ? 1 h 3 )( 2 , ? 1 ? 3 ) 1 (2?1? 13)式并不就给出剖分数,无疑其中 是有重复的。

其重复度是由于一个凸 n边形

的剖分有 n?3条对角线,而对其每一条边 计数时该剖分都计数了一次,故重复了 n?3 次即 2? 1? 1 3 式给出的结果是 h n 的 n?3倍。 §2.11 Catalan 数?(n?3)hn ?n2(h3hn?1?h4hn?2?? ?hn?2h4?hn?1h3).(2?1? 11)式和 (2?1? 12)式都是非线性的

递推关系。 §2.11 Catalan 数2.Catalan 数计算公式由(2?1式? 11及) ,h故2 ?得1 hn?1?2hn ?h3hn?1?h4hn?2 ???hn?2h4 ?hn?1h3. ?(n?3)hn ?n2(h3hn?1?h4hn?2 ???hn?1h3) ?n2(hn?1?2hn) §2.11 Catalan 数由 (n?3)hn?n 2(hn?1?2hn), 整理得 2 ( n ? 3 ) h n ? n n ? 1 ? h 2 n n .h? n n ? 1 h ? ( 4 n ? 6 ) h n .令 fn?1? ?nfnn ?h ? 11?, (4n?6)nf?n1?2(nn??13) fn?(2n?2)(2n?3) (n?1)(n?1)fn. §2.11 Catalan 数即 ffn n ? 1?(2 (n n? ? 2 1 ))n 2 ((n ? ? 1 )3 ),f2?h 2?1 ,fn?1?fn?1 ? fn

fn ? fn?1fn?1 ? f4 ? fn?2 f3f3 f2? (2n ? 2)(2n ? 3) ? (2n ? 4)(2n ? 5) (n ?1)(n ?1) (n ? 2)(n ? 2)?4?3? 2?2 2? 2 1?1 §2.11 Catalan 数? (2n?2)! ???2n?2?? (n?1)!(n?1)! ?n?1 ??nbn?1.?hn?1?1??2n?2??. n?n?1 ? §2.11 Catalan 数3.母函数方法设 G (x )? h 2? h 3 x ? h 4 x 2? ? ,x2:h4 ?h2h3 ?h3h2,x3:h4 ?h2h4 ?h3h3 ?h4h2,x4:h4 ?h2h5 ?h3h4 ?h4h3 ?h5h2? )? ? ? ? §2.11 Catalan 数G(x) ? x ? 1 ? h2 (h3x2 ? h4 x3 ? ?) ? h3 x(h2 x ? h3x2 ? ?) ? h4 x2 (h2 x ? h3 x2 ? ?) ? ?? ? x ? h2 (h2 x ? h3 x2 ? h4 x3 ?) ? h3x(h2 x ? h3 x2 ? h4 x3 ?) ? ?.? G (x )? 1 ? x [G (x )2 ,]即 x2 G ? G ? 1 ? 0 . §2.11 Catalan 数

G?1? 1?4x. 2x

后面将看到只能取 G?1? 1?4x 才有意义.由二项式定理2x(1?y)12?1?1y?12(12?1)y2 2 2! §2.11 Catalan 数1(1?1)(1?2) ?2 2 2 y3??,3!?(1?4x)12?1?2x?212??12!42x2?12?31??33!43x3 ?? ?1?3?5?27k? ?k(!2k?3)4kxk?? , §2.11 Catalan 数即(1?4x)12中 xn?1 项的系数为1 ? 2(1 ?1)(1 ? 2)?(1 ? n)(?4)n?1(n ?1)! 2 22?(?1)2n?1 (n ?1)!1?3?(2n 2n?1?1)22n?2? ? 2n?1 1? 3? 5?(2n ?1) (n ?1)! §2.11 Catalan 数?(n??21()2nn ()!)2 !?n??21???2 nn???. ?G(x)?1? 1?4x 的系数为正,而且得2xhn?1?1??2n?2??. n?n?1 ? §2.11 Catalan 数

从递推关系n n ? 1 ? h ( 4 n ? 6 ) h n ,h 2 ? 1 ,同样可 推出G(x)?1? 1?4x 2x令 G (x)?h2?h3x?h4x2?? , x(G x)?h2x?h3x2?h4x3?? ?G 1(x) §2.11 Catalan 数x: 2h3 ? 4?2h2 ?6h2, x2 :3h4 ? 4?3h3 ?6h3, ?) ????? G1'(x) ?1? 4[xG1(x)]' ?6G1(x), (1?4x)G1'(x) ?2G1(x) ?1, G1(0) ?0, §2.11 Catalan 数用1 (1 ? 4x)3

乘等式两端得1 1?4x

G1'(x)?2G1(x) ? (1? 4x)31, (1? 4x)3?

d? dx ??

G1( x) 1? 4x? ???1 ,(1? 4x)3? G1(x) ? 1 ? C. 1? 4x 2 1? 4x §2.11 Catalan 数即 G1(x) ? C1?4x?1, 2

G1(0)?0,? C ? ?1, 2

G1(x) ? 1 ?1? 4x, 2G(x) ? 1? 1? 4x . 2x §2.11 Catalan 数 4.举例 §2.11 Catalan 数

图 2-11-4 §2.11 Catalan 数例1.h6?1??8,见?? ?图14 5?4?2? 1? 1 4

例2. P?a 1a2a 为3? n个an 数a1,a2,? ,an

的乘积,依据乘法的结合率,不改变其顺序,

只用括号表示成对的乘积.试问有几种不同

的乘法方案? §2.11 Catalan 数令 p n 表示n个数乘积的 n?对1 括号插入的不

同方案数. p n ? p 1 p n ? 1 ? p 2 p n ? 2 ? ? ? p n ? 1 p 1 , p 1 ? p 2 ? 1 .令 p k? p k ? 1 ,k ? 1 ,2 ,3 ,? ,n ,故得 h n ? 1 ? h 2 h n ? h 3 h n ? 1 ? ? ? h n ? 1 h 3 ? h n h 2 ,

而且 hn? 1?hn? 1?1.故 p n 即为Catalan数hn?1. §2.11 Catalan 数

以 n?4为例p4?h5?1??6???5. 4?3?(a ( 1 (a 2 a 3)a )4)(,a (1 a ( 2)a 3)a 4)(,a ( 1 a 2)a ( 3 a 4)), (a 1 (a 2(a 3 a 4))(a 1 )(a ,(2 a 3)a 4))(.-2 1-4 1)p4 ? Catalan数 h 5,下面建立 (2-1式1-4) 中不同的乘法顺序和一个5边形不同拆分的 一一对应关系,如图 2? 1? 1 6 §2.11 Catalan 数 (a (1(a2a3)a )4)(a1(a2a3))(a2a3)a 1 ((a a 1 2(a2)aa33)a4a)4 ((a1a2)a3) (a1a2)a1 a2 a3 a4a0a4a1a2 a0a3 a4a1a3a2 §2.11 Catalan 数 (a (1a2)a (3a4))(a1a2)(a3a4)a1 a2 a3 a4 (a1(a2(a3a4)))(a2(a3a4)) (a3a4)a1 a2 a3 a4a0a4a1a2 a0a3 a4a1a3a2 §2.11 Catalan 数(a1(a (2a3)a4))a0((a2a3)a4)(a2a3)a1a1 a2 a3 a4

图 2-11-6a4a3 a2 §2.11 Catalan 数a?b运算用二分树表示,两片叶子分别表

乘数和被乘数,分支点为运 算符 ?,如图 2? 1? 1 5ab(a?b)

图 2-11-5 §2.11 Catalan 数

例3. n个1和n个0组成一2n位的2进制数,要 求从左到右扫描,1的累计数不小于0的累计 数,试求满足这条件的数有多少?

下面介绍两种算法。

解法1. 设 p为2n 这样所得的数的个数。在2n

位上填入n个1的方案数为?? 2 n ??,不填1的其余 ?n ? §2.11 Catalan 数n位自动填以数0。

从?? 2 n中?? 减去不符合要求 ?n ?

的方案数即为所求。

不合要求的数指的是从 左而右扫描,出现0的累计数超过1的累计数 的数。

不合要求的数的特征是从左而右扫描时,

必然在某一奇数 2m? 位1上首先出现 m?1 §2.11 Catalan 数

个0的累计数,和m个1的累计数。

此后的 2(n?位m 上)? 有1 个1n ,? m n?m 个?01。如若把后面这部分 2(n?m)?1 位,0与1交换,使之成为n? 个m 0, n?m ?1 个1,结果得1个由 n?个10和 n个?11组成

的2n位数,即一个不合要求的数对应于一个由 n?个10和 n个?11组成的一个排列。 §2.11 Catalan 数

反过来,任何一个由 n?1个0,n?1个1组

成的2n位数,由于0的个数多2个,2n是偶数, 故必在某一个奇数位上出现0的累计数超过1 的累计数。

同样在后面的部分,令0和1互换, 使之成为由n个0和n个1组成的2n位数。即n?1

个0和 n?个11组成的2n位数,必对应于一个

不合要求的数。 §2.11 Catalan 数用上述方法建立了由 n?1个0和 n?个11

组成的2n位数,与由n个0和n个1组成的2n 位

数中从左向右扫描出现0的累计数超过1的累

计数的数10一10一0* 1对01应。例如

是由4个0和4个1组成的8位2进制数。但从左而右扫描在第5位(打*号)

出现0的累计数3超过1的累计数2,它对应于 §2.11 Catalan 数由3个1,5个0组成的10100。010*

反过来 1010对00应10于10。100101因而不合要求的2n位数与 n个?10, n?1

个1组成的排列一一对应,故有

p 2 n? ? ? ?2 n n ? ? ?? ? ? ?2 n n ? 1 ? ? ?? (2 n )? ? ? n ! ! 1 n !? (n ? 1 )1 (n !? 1 )? ? ?! §2.11 Catalan 数?(2n)!???(nn??1)1!n!?(n?n1)!n!????(n(?2n1))!!n! ? 1 ??2n??.n?1?n ? §2.11 Catalan 数

解法2.这个问题可以一一对应于图 2? 1? 1 7 中从原点 (0,0到) (点n,n的) 路径要求中途所 经过的点 (a,b满) 足关系 a?b

对应的办法是从 (0出,0)发,对2n位数从左 而右扫描,若遇到1便沿y轴正方向走一格;

若遇到0便沿x轴正方向走一格。由于有n个0, n个1,故对应一条从(0,0点) 到达 (n点,n的) 路 §2.11 Catalan 数

径,由于要求1的累计数不少于0的累计数, 故可以途经对角线 O上A的点,但不允许穿越 过对角线。

反过来,满足这条件的路径对应 一满足要求的2n位2进制数。

见图2? 1? 1 8

问题导致求从 (出0,0发) ,途经对角线 及对角线上方的点到达(n,点n)的路径数。 §2.11 Catalan 数yA'(n,n?1) yA(n,n)10 0

O' (0,1) O(0,0) B11010x0x

图 2-11-7

图 2-11-8 §2.11 Catalan 数

从一点到另一点的路径数的讨论见第1章§3 例1。

见图2? 1,? 1 7 从 点出O发经过 及OA

O上A 方的点到达 点A的路径对应一条从 点出发经过O' A及' O上' A方' 的点到达 点的O '

路径,这是显而易见的。

从 点O 出' 发途经 上O的A点到达 点的A 路'

径,故对应一点从O点出发穿越 O到A达 A ' §2.11 Catalan 数

点的路径,故对应一从 O点出发穿越 O到A达 A点的路径。

所以从 点O出发经过 及OA以O上A的点 最后到达 A点的路径树,等于从 点出发到 达 A点' 的所有路径数,减去从 O点' 出发路径 O上A的点到达 点A ' 的路径数。即 §2.11 Catalan 数

p 2 n? ? ? ?2 n n ? ? ?? ? ? ?2 n n ? 1 ? ? ?? (2 n )? ? ? n ! ! 1 n !? (n ? 1 )1 (n !? 1 )? ? ?! ?(2n)!???(nn??1)1!n!?(n?n1)!n!????(n(?2n1))!!n! ?n1?1???2nn????hn?2. §2.11 Catalan 数

例4. 由n个1,n个0组成的2n位二进制数,要2n?1

求从左向右扫描前 位时1的累计数大于0

的累计数,求满2 足? 这1样? 1 条7件的O数的个数。

此 问题可归O结A为图 中从A 点出发只经过

对角线 上方的点O抵'(0达,1) 点,求这样的路O径A数。

相A当'(n于?求1,n从) 点不经过对角线 ,抵达

点的路径数,于是便转换为 §2.11 Catalan 数

例3的问题。

根据例3的结果。

从 O'(点0,1通) 过 的O' A'

点,以及O' A上' 方的点到达 A'(n的?1路,n径)数为??2n?2?????2n?2???(2n?2)[!1?n?1 ? ?n ?(n?1)!(n?1)!? 1 ]?(2n?2)!n?n?1n!(n?2)!n!(n?1)! §2.11 Catalan 数?1n???2nn??12????hn?1. 谢谢!357

我是一个大三的学生!自大学一年级,我开始做的ACM,我觉得你可能有资格在杭州新华下载了一套杭电ACM课件PPT,你将有很大的提高!有什么不明白在网上搜索!现在有很多的在线答疑!我觉得网上资源太丰富。比一本好书,而不是为了金钱!你就会快速的得到提高,对细节的关注,恒功率,以帮助您确定问题是否纠正你做,有时你认为你自己的问题,正确的,但不完全。杭电可以帮你了解一下。事实上,游戏的时间,很多的答案认为是正确的,但笔者不上去,细节决定成败。一个良好的开端,从大一在杭州新华有权这样做。你会成为高手!内容来自www.07swz.com请勿采集。

  • 人力资源管理师职业资格认证 第五章 薪酬福利管理
  • 人力资源管理师职业资格认证 第五章 薪酬福利管理
  • 人教版八年级物理下册3A第七章力 课时作业课件.p
  • 人教版八年级物理下册3A第七章力 课时作业课件.p
  • 人教版九年级上册第二十二章: 二次函数复习课 .p
  • 人教版九年级上册第二十二章: 二次函数复习课 .p
  • 上册第三章中国的自然资源第二节土地资源-课件 24
  • 上册第三章中国的自然资源第二节土地资源-课件 24
  • 上海财经大学证券投资学精品课程 第一章.ppt 5
  • 上海财经大学证券投资学精品课程 第一章.ppt 5
  • 人教版八年级上册地理课件第一章第一节疆域.ppt
  • 人教版八年级上册地理课件第一章第一节疆域.ppt
  • 小弟大一学ACM,求推荐几本书,谢谢
  • 组合2母函数递推关系
  • 幼儿园数学课件集ppt
  • 数学课件ppt模板ppt
  • 数学课件ppt怎么做
  • 二年级数学课件ppt
  • 最新推荐
    热门推荐