主页 > 案例大全 > 论文写作分析-上下文无关文法与欧拉多项式

论文写作分析-上下文无关文法与欧拉多项式

2021-04-23 13:17:29

  1.上下文无关文法的背景

  上下文无关文法的背景最早可以追溯到公元前四世纪的印度著名语法学家帕尼尼,他在著作中阐述的语法规则是描述性语言学的第一个已知示例。那个时代的语言学家们以“块结构”的属性来描述帕尼尼的语法,这一语法展示了应当如何从字母,单词或是较小的短语递归得到句子与文段的。

  事实上,上下文无关文法提供了一种简易而精确的数学方法,描述了自然语言中的句子与短语,是如何由较小的块构建得到的。这一文法的思想,最早是由大数学家凯莱在19世纪提出的。

  上下文无关文法的微分运算符的概念以及用途,是由陈永川[1]首次详述的,其目的是用于研究组合学中的指数结构。陈永川使用上下文无关文法来研究FaadiBruno公式、Bell多项式、Stirling数和对称函数等,其给出的拉格朗日反演公式的一个语法表示十分简便。

  Dumont[2]较早地尝试用上下文无关文法来研究了欧拉多项式。在其后,马世美以及B.C.Berndt等一些数学家效法之,以上下文无关文法研究了Bessel多项式,组合数列,排列的生成等问题。

  在查阅了这些数学家的研究成果以后,可以发现,上下文无关文法在解决多项式函数等数学问题上,发挥了不错的效用。事实上,上下文无关文法在很大程度上简化了思路以及运算。在经过研究尝试后,我们发现,借助于上下文无关文法研究欧拉数、欧拉多项式及其相关性质,是有先例的,也是简便、可行且卓有成效的。

  2.上下文无关文法的基本思想

  2.1上下文无关法的定义与微分运算符

  陈永川在其论文[1]中阐述了上下文无关文法的具体定义。

  首先,其阐述了形式函数(formal function)。基于一个可以包含无限个字母的字母表A,其形式函数以以下途径实现:每一个字母均为形式函数,形式函数的乘积,以及以形式函数为自变量的解析函数仍为形式函数。此外,所有形式函数均应在有限步骤内得到,即不应有无限累乘等方法得到形式函数。

  基于A的上下文无关文法G即被其定义为了一种替换规则,这一规则用A上的形式函数来替换A上的字母。例如,对于一个字母表A={f,g},替换规则G={f->fg,g->g}即构成了一个上下文无关文法。当然,这只是一个十分简单的例子,事实上的情况可以远远复杂于此。

  其后,陈永川定义了微分运算符D。基于字母表A的运算符D的定义如下:

  (1)对于两个A上的两个形式函数u和v,有:

  (2)对于任意解析函数f(x)以及A上的形式函数w,有:

  (3)对于A上的字母v和形式函数w,如果规则G中包含了从v到w的映射,那么D(v)=w。或D(v)=0,在这种情况下,我们将v称为常数。

  我们将这样的运算符D称为上下文无关文法G上的形式导数。可以发现,形式导数是基于常规函数的导数得来的,因而其在性质上,也与常规的导数有许多相似之处。例如,很显然,莱布尼兹公式对于形式导数依然适用。

  命题:

  陈永川[1]证明了,对于前文中提到的G={f->fg,g->g},有:

  其中S(n,k)为第二类Stirling数,即将一个包含n个不同或被标记元素的集合分割为k块的分割方法数。事实上,我们发现,基于Stirling排列和Legendre-Stirling排列,使用上下文无关文法可以得到稳定的多元多项式,而这样的稳定的多元多项式被Haglund和Visontai[3]用于他们关于二阶欧拉多项式的研究。

  除此之外,利用上下文无关文法,马世美等几名中国教授[4]对于欧拉多项式及其相关多项式进行了研究,得出了一些有关性质,我们将在后文展开讨论分析。

  2.2形式幂级数

  陈永川[1]在论文中同样研究了形式幂级数(formal power series)的相关内容,这对于上下文无关文法的研究也至关重要。

  我们有字母表A,上下文无关文法G和形式导数D。对于A上的形式函数w,|w|代表w的估值(evaluation),其将A内的字母均映射到一个实数上去,一个常见的估值为将所有字母均映射为实数1。

  陈永川[1]对形式幂级数做了有如下定义:

  形式幂级数Gen+(w,t)和gen+(w,t)被称为w的delta级数,注意t不包含在A内。

  那么我们有[1]:

  陈永川基于微分算子以及形式幂级数,利用上下文无关文法做了许多基础性的研究,这些研究影响深远。例如,利用形式幂级数的性质,陈永川[1]证明了,对于Bell多项式,我们有:

  3.欧拉多项式的介绍

  3.1欧拉多项式的定义

  在数学史上,欧拉多项式(Eulerian polynomials)曾经多次被不同数学家发现,并被反复重新定义[5]。因而,我们现在所说的欧拉多项式也曾被冠以许多其他的名字,例如Euler polynomials,Eulerian,Euler-Frobenius polynomials等。除此之外,也有一些其他的多项式被称为欧拉多项式,且其有一些衍生的多项式也被冠以相关名称。因而,理清欧拉多项式的历史由来以及定义,明晰相关的多项式之间的差别,是有必要的。

  欧拉在1749年引入多项式以描述一种计算zeta函数取在负整数点的值的方法,他通过以下方式生成此多项式An(t),即我们现在所说的欧拉多项式:

  An(t)被证明仅具有简单的负实根。

  同时,欧拉多项式还可以由以下生成函数定义:

  An(t)可以被写为:

  其中,我们称A(n,k)为欧拉数(Eulerian numbers),其定义为:

  欧拉-弗罗贝尼乌斯数(Euler-Frobenius Fractions)Hn(t)相对不太常见,其被Carlitz命名为欧拉多项式(Eulerian polynomials),被Kim命名为欧拉-弗罗贝尼乌斯数。其以如下方式定义:

  衍生欧拉多项式(generalised Eulerian polynomials)Hn(u,t)的定义为:

  3.欧拉数与排列

  欧拉数的定义如上文所述。事实上,我们可以发现欧拉数与排列的某些特征之间存在一定联系。

  首先我们需要定义排列(permutation)。假设存在一个集合N,其具有n个元素。那么N的一个排列是N基于其自身的双射映射。例如,假设N={1,2,3},那么,s={2,3,1}就是其一个排列。

  对于这一排列,我们有:s(1)=2,s(2)=3,s(3)=1。

  现在,我们将这一概念一般化,对于一个给定的排列:

  s={s(1)s(2)...s(n)}

  对于其内的一个元素i(1<=i<=n):

  (1)若s(i)<s(i+1),则i被称为排列s的一个上升点(ascent);

  (2)若s(i)>s(i+1),则i被称为排列s的一个下降点(descent);

  (3)若s(i)>i,则i被称为排列s的一个超越数(excedance);

  (4)若s(i)<i,则i被称为排列s的一个弱超越数(weak excedance)。

  我们可以得知[5],欧拉数A(n,k)表示总元素数为n个的排列中:

  (1)具有k个上升点的排列的个数;

  (2)或具有k个下降点的排列的个数;

  (3)或具有k个超越数的排列的个数;

  (4)或具有k+1个弱超越数的排列的个数。

  我们在此处定义以下两个概念:

  (1)如果i=1且si>si+1,或si-1<si>si+1,则称i为外部谷峰点(exterior peak),将外部谷峰点的数目记为T(n,k);

  (2)如果3<=i<=n且si-2>si-1>si,则称i为双降点(proper double descent),将双降点的数目记为U(n,k)。

  基于此,我们定义了以下两个多项式:

  付梅[6]在其论文中,利用上下文无关文法,对这两个多项式进行了研究,得到其生成函数分别为:

  事实上,我们可以发现,排列就是一种特殊的上下文无关文法,其从初始元素到排列后的元素的映射,满足前文所述上下文无关文法的条件。因而,我们可以借助上下文无关文法的研究方法,来研究排列的相关性质,进而研究欧拉多项式的性质。

  4.对欧拉多项式的研究

  4.1研究的准备工作

  根据前文的结论,欧拉数A(n,k)表示总元素数为n个的排列中具有k个超越数的排列的个数。

  基于此,我们取一个集合N={1,2,3...n},Sn为这个集合的排列所构成的集合,即s∈Sn。对于一个特定的排列s,我们定义exc(s)为其中超越数的个数,则欧拉多项式可通过以下方法生成:

  其中A(n,k)即为前文提到的欧拉数,我们发现,A(n,k)满足:

  参考马世美等[4]的研究成果,我们将An(t)命名为A型欧拉多项式,并定义B型欧拉多项式。

  对于一个给定的集合N={0,+-1,+-2...+-n},考虑其排列s中,对于所有的i满足s(-i)=-s(i)条件的,将这样的s的集合命名为超八面体集(hyperoctahedral group)Bn。我们在s中添加一个元素s(0)=0,那么,我们可以取:

  des B(s)=#{i∈{0,1,2,...n-1}|s(i)>s(i+1)}

  B型欧拉多项式的定义为[4]:

  其中B(n,k)为B型欧拉数,其满足[11]:

  B(n+1,k)=(2k+1)B(n,k)+(2n-2k+3)B(n,k-1)

  B(0,0)=1

  B(0,k)=0,k>1

  命题[7]:

  命题[8]:

  若对于i∈N,有s(i)>=0,则我们将其称为正值点,否则将其称为负值点。我们用N(s)来表示排列s中负值点的个数。

  A型和B型的q阶欧拉多项式可以以如下形式定义[4]。

  其中,cyc(s)是对s进行k循环分解后,循环(cycle)的数量。

  根据文献[9],A型和B型欧拉多项式的交错运行多项式(alternating run polynomial)分别被以如下方式定义:

  其中n>=2,且。

  根据文献[10],A型和B型欧拉多项式的紊乱多项式(derangement polynomials)分别为:

  这些多项式均可以通过上下文无关文法得以较为简便地研究其性质,后文我们将主要基于q阶A型欧拉多项式和q阶B型欧拉多项式进行讨论。

  4.2q阶A型欧拉多项式的上下文无关文法

  首先,我们定义反超越数(anti-excedance)。

  对于排列s中的i,如果满足s(i)<=i,则称i为s中的反超越数。很明显,一个排列中的超越数和反超越数之和即为该排列的元素数n。

  现在我们对排列s做k循环分解,之后将其按照每个循环中的最小的元素,以从小到大的形式进行排列,得到的结果,我们称为标准循环形式的排列。现在,我们对于标准循环形式的排列做以下方式的标记[4]:

  (1)在每个超越数之后添加上角标z;

  (2)在每个反超越数之后添加上角标y;

  (3)在每个循环之前添加上角标q;

  (4)在s的末尾添加上角标x。

  我们定义Sn(i,j,k)={s∈Sn:aexc(s)=i,exc(s)=j,cyc(s)=k}。

  例如,对于n=1,我们有S1(1,0,1)={q(1y)x}。

  我们考虑对排列s进行估值运算。我们将标记后的s的标记字母逐个相乘,得到了s的值。

  w(s)=...

  对于Sn(i,j,k)中的排列s,我们插入一个元素n+1进去,则插入后的排列s’属于排列集Sn+1。考虑这样的插入,我们发现有以下三种情况:

  (1)如果插入的n+1自己形成了新的循环,即插入到了原有排列的最末尾,那么s’∈Sn+1(i+1,j,k+1)。因而,在这种情况下,这一插入对应运算x->qxy。

  (2)如果将n+1插入到一个超越数右边,则s’∈Sn+1(i+1,j,k)。因而,在这种情况下,这一插入对应运算z->yz。

  (3)如果将n+1插入到一个反超越数右边,则s’∈Sn+1(i,j+1,k)。因而,在这种情况下,这一插入对应运算y->yz。

  基于以上讨论,我们可以得到如下结论。

  在这种情况下,我们有集合A={x,y,z},以及上下文无关文法G={x->qxy,z->yz,y->yz}。