《反演公式及其应用》PPT课件.ppt

《《反演公式及其应用》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《反演公式及其应用》PPT课件.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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)为正规多项式族.引理引理 给定正规多项式族Pn(x),则对任一k次多项式Qk(x),存在常数 即Qk(x)可表示为P0(x),P1(x),P2(x),Pk(x)的线性组合.定义定义 给定正规多项式族Pn(x),D是将Pn(x)中每个多项式Pn(x)映射为多项式DPn(x)的

2、映射.若D满足 (2)DPn(x)=DPn(x);(3)DPm(x)+Pn(x)=DPm(x)+DPn(x);则称D为Pn(x)上的微分算子.注:求导运算为xn的微分算子.例例2 对正规多项式簇xn,定义算子 则是xn上的微分算子.定理定理 若D是正规多项式簇Pn(x)上的一个微分算子,则D是任意多项式上的微分算子.定理定理6.1.2(Taylor)若D是正规多项式簇Pn(x)上的一个微分算子,Q(x)为任一k次多项式,则有 注注:若正规多项式簇为xn,则(6.1.2)即为Taylor-Maclaurin 公式.例例3 证明Norlund公式2.第一反演公式第一反演公式 定理定理 设 和 为满

3、足条件 的两个多项式簇,和 为两组数,则 说明:若和D分别为正规多项式簇Pn(x)和Qn(x)上的微分算子,则由定理知 从而由定理知 互为可逆.定理定理6.1.4(逆二项式公式逆二项式公式)若数列 和 满足 则 j=0,1,2,n.定理定理6.1.5(二项式反演公式二项式反演公式)若 和 是两个数列,s为非负整数,若对任意不小于s的整数n均有 则7.2 Mbius反演公式及其反演公式及其应用用 -一种很有用的一种很有用的计算工具算工具1.Mbius反演公式反演公式 设n为一正整数,则n可唯一分解为 其中p1,p2,pk为互不相同的素数,定义定义 定义在正整数集上的函数(x)称为Mbius函数,

4、若它满足引理引理 对任意正整数n有 其中求和指标d|n表示d取n的所有正因数.例例1 如n=6,则定理定理7.2.1(Mbius反演定理反演定理)设f(n)和g(n)定义在正整数集上的两个函数,则 称f(n)为g(n)的Mbius变换,g(n)为f(n)的Mbius逆变换.例例2 设(x)欧拉函数,则 (1)(2)2.反演公式的应用反演公式的应用从n个不同元素中取r个作成的圆排列数为n如允许重复取元素,则圆排列数如何计算?引入以下几个概念:1)线排列的长度线排列的长度:排列中元素的个数;2)线排列的周期线排列的周期:长为n的线排列可看作是由一个长 为d的线排列重复k次得到(n=kd),满足该性

5、质的最小的d称为线排列的周期.例如例如 对线排列T1=(12312),长n=5,重复k=1次即可,周期为5;对线排列长n=12,由123重复k=4次即可,周期为3.3)圆排列的展开圆排列的展开:将长为n的圆排列从n个位置断开可得n个线排列;对长为n、元素可重复出现的圆排列从n个位置断开得到的n个线排列中有可能有相同的.4)圆排列的周期圆排列的周期:圆排列展成的线排列的周期.对任一长为n、周期也为n的圆排列,从n个不同的位置断开得到的n个线排列是互不相同的;对任一长为n、周期也为dn的圆排列,断开得到的线排列中有d个是互不相同的.定理定理 设重集B=b1,b2,br的n-圆排列个数为T(r,n)

6、,其中周期为n的圆排列个数为M(r,n),则有 1)2)例如例如证明证明(1)设d|n.由于每一个长为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反演定理得 即(2)由于 令 则定理定理7.2.3(r元元Mbius反演

7、公式反演公式)设f(x1,x2,xr)和g(x1,x2,xr)是定义在NNN(r个正整数集的笛卡尔积)的r元函数。若 则 其中对给定的正整数n1,n2,nr,n=n1+n2+nr.T(n1,n2,nr;n)表示n1个b1,n2个b2,nr个br的圆排列个数，M(n1,n2,nr;n)表示其中周期为n的圆排列个数,则由定理得以下定理。定理定理 令 ,则例例5 用两颗红珠、三颗黄珠和四颗绿珠能摆成多少个不同样式的圆环？例例6 设重集B=2a,4b,(1)将B的所有元素作圆排列，求其中周期为6的圆排列的个数，并列出它们。(2)将B的所有元素作圆排列，求该圆排列的个数，并列举它们。7.3 其他一些反演

8、定理其他一些反演定理设A(X)和B(X)分别为序列a0,a1,a2,和b0,b1,b2,的指数母函数,若A(X)B(X)=1,即 则称函数A(X)和B(X)是互逆的.定理定理 设f(n),g(n)和h(n)是定义在非负整数集上的三个函数,且h(0)0,则对任意非负整数n有 其中序列 的指数母函数与序列 的指数母函数是互逆的.推论推论7.3.1 设f(n),g(n)是定义在非负整数集上的两个函数,且c0为任一复数,则对任意非负整数n有 注:在定理中设h(n)=cn,推推论设f(n),g(n)是定义在非负整数集上的两个函数,则对任意非负整数n有 注:在推论中设c=1即可.例1 用推论推导错排数Dn的计算公式.