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

《《反演公式及其应用》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章反演公式及其应用----解决组合数学中一些类型的求和、级数变换问题的有效工具§7.1正规多项式族1.正规多项式族定义7.1.1实变量x的多项式族P0(x),P1(x),P2(x),…,Pn(x),…简记为{Pn(x)}若满足P0(x)=1,Pn(0)=0,n≥1,则称{Pn(x)}为正规多项式族.引理7.1.1给定正规多项式族{Pn(x)},则对任一k次多项式Qk(x),存在常数即Qk(x)可表示为P0(x),P1(x),P2(x),…,Pk(x)的线性组合.定义7.1.2给定正规多项式族{Pn(x)},D是将{Pn(x)}中每个多项式Pn(x)映射为多项式DPn(x)的映

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

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

4、它满足引理7.2.1对任意正整数n有其中求和指标d

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

6、T1=(12312),长n=5,重复k=1次即可,周期为5;②对线排列T2=(123123123123),长n=12,由123重复k=4次即可,周期为3.3)圆排列的展开:将长为n的圆排列从n个位置断开可得n个线排列;对长为n、元素可重复出现的圆排列从n个位置断开得到的n个线排列中有可能有相同的.4)圆排列的周期:圆排列展成的线排列的周期.对任一长为n、周期也为n的圆排列,从n个不同的位置断开得到的n个线排列是互不相同的;对任一长为n、周期也为d

7、n),其中周期为n的圆排列个数为M(r,n),则有1)2)例如证明(1)设d

8、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),则由Möbius反演定理得即(2)由于令则定理7.2.3(r元Möbius反演公式)

9、设f(x1,x2,…,xr)和g(x1,x2,…,xr)是定义在N×N×…×N(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的圆排列个数,则由定理7.2.3得以下定理。定理7.2.4令,则例5用两颗红珠、三颗黄珠和四颗绿珠能摆成多少个不同样式的圆环？例6设重集B={2a,4b},(1)将