第七章 反演公式及其应用

1、整理课件第七章第七章 反演公式及其应用反演公式及其应用-解决组合数学中一些类型的求和、级数变换问题的有效工具7.1 正规多项式族正规多项式族n1. 正规多项式族正规多项式族 定义定义7.1.1 实变量x的多项式族 P0(x), P1(x), P2(x), , Pn(x), 简记为Pn(x) 若满足P0(x)=1, Pn(0)=0, n1, 则称Pn(x)为正规多项式族. 引理引理7.1.1 给定正规多项式族Pn(x), 则对任一k次多项式Qk(x), 存在常数 即Qk(x)可表示为P0(x), P1(x), P2(x), , Pk(x)的线性组合.使得k,10),()()()(1100 xPx

2、PxPxQkkk整理课件 定义定义7.1.2 给定正规多项式族Pn(x), D是将Pn(x)中每个多项式Pn(x)映射为多项式DPn(x)的映射. 若D满足 (2)DPn(x)=DPn(x); (3) DPm(x)+Pn(x)= DPm(x)+DPn(x); 则称D为Pn(x)上的微分算子. 注:求导运算为xn的微分算子. . 0,00,n,(x)nP(x)P) 1 (1 -nnnD整理课件 例例2 对正规多项式簇xn, 定义算子 则是xn上的微分算子. 定理定理7.1.1 若D是正规多项式簇Pn(x)上的一个微分算子,则D是任意多项式上的微分算子, 称之为与Pn(x)相联系的微分算子. 定理

3、定理7.1.2(Taylor) 若D是正规多项式簇Pn(x)上的一个微分算子,Q(x)为任一k次多项式, 则有 注注: 若正规多项式簇为xn, 则(6.1.2)即为Taylor- Maclaurin 公式., 1nnnxxx)2 . 1 . 6()(!)0()(! 2)0()(! 1)0()0()(221xPkQDxPQDxPDQQxQkk整理课件 例例3 利用Taylor定理证明二项式公式 例例4 证明Norlund公式,0knnkknyxknyx,0knnkknyxknyx整理课件 定理定理7.1.3 设 和 为满足条件 的两个多项式簇, 和 为两组数,则 )(xn)(xnnjxxxxnk

4、kjkjnkkjkj, 2 , 1 , 0),()(),()(00naaa,10nbbb,10), 2 , 1 , 0(), 2 , 1 , 0(00njabnjbankkjkjnkkjkj2. 第一反演公式第一反演公式整理课件 说明: 若和D分别为正规多项式簇Pn(x)和Qn(x)上的微分算子, 则由定理6.1.2知 从而由定理6.1.3知 互为可逆.njxPkQxQxQkPDxPnkknknnkknkn, 2 , 1 , 0),(!)0()(),(!)0()(00!)0(! 2)0(! 1)0()0(0! 2)0(! 1)0()0(00! 1)0()0(000)0(!)0(! 2)0(!

5、1)0()0(0! 2)0(! 1)0()0(00! 1)0()0(000)0(2222211022222110nQQQQQQQQQQnPDPDDPPPDDPPDPPPnnnnnnnnnn与整理课件 定理定理7.1.4(逆二项式公式逆二项式公式) 若数列 和 满足 则 naaa,10nbbb,10n,0,1,2,j0，kjkjbkjan.,0,1,2,j10，kjkkjjakjb整理课件 定理定理6.1.5(二项式反演公式二项式反演公式) 若 和 是两个数列,s为非负整数,若对任意不小于s的整数n均有 则naaa,10nbbb,10，knsknbkna，knskknnbknb1整理课件7.2

6、Mbius反演公式及其应用反演公式及其应用 -一种很有用的计算工具一种很有用的计算工具 1. Mbius反演公式反演公式 设n为一正整数,则n可唯一分解为 其中p1,p2,pk为互不相同的素数, 定义定义7.2.1 定义在正整数集上的函数(x)称为Mbius函数, 若它满足kkpppn2121。，kii21011,) 1(11,01, 1)(ikinnnnnn的分解式中所有且的分解式中存在一个且整理课件 引理引理7.2.1 对任意正整数n有 其中求和指标d|n表示d取n的所有正因数. 例例1 如n=6, 则,1,01, 1)(|nndnd0) 1() 1() 1(1)6()3()2() 1 (

7、)(26 |dd整理课件 定理定理7.2.1(Mbius反演定理反演定理) 设f(n)和g(n)定义在正整数集上的两个函数,则 称f(n)为g(n)的Mbius变换, g(n)为f(n)的Mbius逆变换. 例例2 设(n)欧拉函数, 则 (1) (2)ndnddnfdngdgnf|)()()()()(;)()(|ndddnn. )(|nddn整理课件2. 反演公式的应用反演公式的应用-求圆排列数求圆排列数 从n个不同元素中取r个作成的圆排列数为 如允许重复取元素, 则圆排列数如何计算?n引入以下几个概念: 1)线排列的长度线排列的长度: 排列中元素的个数; 2)线排列的周期线排列的周期: 长

8、为n的线排列(包括重排列)可看作是由一个长为d的线排列重复k次得到(n=kd), 满足该性质的最小的d称为线排列的周期. 例如例如 对线排列T1=(12312), 长n=5, 重复k=1次即可,周期为5; 对线排列T2=(123123123123), 长n=12, 由123重复k=4次即可,周期为3./ ),(),(rrnPrnQ整理课件 3)圆排列的展开圆排列的展开: 将长和周期均为n的圆排列从n个位置断开可得n个互不相同的线排列; 对长为n、元素可重复出现的周期为dn的圆排列从n个位置断开得到的n个线排列中有d个是互不相同的. 例如例如 对圆排列(123123123123) 圆排列的周期圆

9、排列的周期: 圆排列展成的线排列的周期. 例如例如 圆排列(111223)的周期为6 整理课件 定理定理7.2.2 设重集B=b1, b2, br的n-圆排列个数为T(r,n),其中周期为n的圆排列个数为M(r,n),则有 1) 2) 例如例如;)(1),(|nddnrdnnrM.)(1),(|nddnrdnnrT.2195363231913)9(3)3(3) 1 (913)(91)9 , 3(1399939199 |9dddT.2184303) 1(31913)9(3)3(3) 1 (913)(91)9 , 3(1399939199 |9dddM整理课件 证明证明 (1)设d|n. 由于每一

10、个长为n、周期为d的圆排列均可由一个长度和周期均为d的圆排列重复n/d次而得到，所以长为n而周期为d的圆排列的总数为M(r,d). 又由于每个这样的圆排列可展成d个不同的线排列，从而M(r,d)个这样的圆排列可展成dM(r,d)个不同的线排列，所以全体长为n的圆排列展成不同的线排列的总数为 。 另一方面，这些线排列也是从重集B中取n个元素组成的线排列，其个数为rn。所以有 令f(n)=rn , g(d)= dM(r,d), 则由Mbius反演定理得 即nddrdM|),(ndndrdMr|),(nddnrdnrnM|)(),(nddnrdnnrM|)(1),(整理课件 (2) 由于 令 则 n

11、dnddddndddddndddddndrddrddrdddrMnrT|)(1)(1)(1),(),(,kdddnndknknkknkkndknddnkkrdnrknnnkknkrddkrrdkdnrT|)(1)(1)()()(),(整理课件 定理定理7.2.3(r元元Mbius反演公式反演公式) 设f(x1,x2,xr)和g(x1,x2,xr)是定义在NNN(r个正整数集的笛卡尔积)的r元函数。若 则 其中),.,2 , 1(, ),(),(|2121riNndndndngnnnfimdrr, ),()(),(|2121mdrrdndndnfdnnng),)(,gcd(21最大公约数rnnn

12、m整理课件 对给定的正整数n1,n2,nr, n= n1+n2+nr. T(n1,n2,nr ;n)表示n1个b1,n2个b2,nr个br的n-圆排列个数，M(n1,n2,nr ;n)表示其中周期为n的圆排列个数, 则由定理7.2.2得以下定理。 定理定理7.2.4 令 ,则),gcd(21rnnnmmdrrmdrrdndndndnnnnnTdndndndnnnnnM|121|121!,!)(1);,(!,!)(1);,(整理课件 例例5 用两颗红珠、三颗黄珠和四颗绿珠能摆成多少个不同样式的圆环？ 例例6 设重集B=2a, 4b, (1)将B的所有元素作圆排列，求其中周期为6的圆排列的个数，并

13、列出它们。 (2)将B的所有元素作圆排列，求该圆排列的个数，并列举它们。整理课件7.3 其他一些反演定理其他一些反演定理 设A(X)和B(X)分别为序列a0,a1,a2,和b0,b1,b2,的指数母函数, 若A(X)B(X)=1, 即 则称函数A(X)和B(X)是互逆的. 此时有A(X)B(X)=1. 定理定理7.3.1 设f(n),g(n)和h(n)是定义在非负整数集上的三个函数,且h(0)0, 则对任意非负整数n有 其中序列 的指数母函数与序列 的指数母函数是互逆的.,0, 00, 10kkbaikkiikininiinfihinngingihinnf00)()()()()()(),.2(),1 (),0(hhh),.2(),1 (),0(hhh整理课件 推论推论7.3.1 设f(n),g(n) 是定义在非负整数集上的两个函数,且c0为任一