外文翻译师范设计外文翻译

长度为的路径是指包含上升步和下降步的元序列。平衡n-路径是指长度为2n且包含n个上升步和n个下降步的路径。平衡n-路径的数量显然是。我们用表示所有平衡n-路径所组成的集合。我们设想路径是以通常的方式：即从原点开始，是上升步(1,1)，是下降步(1,−1)，n量是。用表示所有n-戴克路径所组成的集合。一个标记的n-戴克路径是集合的一个元素。所有标记的n-戴克路径组成的集合用表示。在标记的或者未标记的n-戴克路径P（或者下降步）数量称为P我们引入一个新的术语：如果一个(平衡或非平衡)的路径在x4even-zeroed。如果，那么每个平衡n-路径都可以非常自然地被唯一分解为一系列标记的n-戴克路径(见图1):x轴将平衡路径切割成非空的子路径，所以，每个子路径要么是从未接触xx射的戴克路径)得到标记的n-戴克路径所决定，并且我们可以将这些标记的戴克路引理3.Even-zeroed平衡2n-路径的数量是。1.和的例解图2.的例证明.当时结论是正确的。现在让我们假 显然，一个平衡的2n-路径P是even-zeroed，当且仅当其序列中所有标记的路径都有奇参数。所以如果我们用表示even-zeroed2n-路径组成的集合，到的约束给出一个和之间的双射，此处：的证明从一个名的关于卡塔兰递归的标准证明可知，D可以被唯一地写成 ，也就是D可以分解成一个有序对，此处L和R都是路径，它的参数共计为2n−1。，然后我们重复递归这个过程:=，去得到另一个中的元素。如果是奇数，那么我们定义的第一个元素为，然后我重复递归这个过程:=L（这里−意味着“左”，+意味着“右”）。当是空的粗略地讲，我们的双射将的“左右对称”转变为的“上下对称”。当定义时，卡塔兰数的另一与满二叉树的共同作用可能会较为自然留给读者）。然而将不会那么直观，因为我们需要在满二叉树和路径之如果我们已经知道或设想了，我们可以找到一个更快的（但是递归 满足下面的递归2引理(i)的平衡(2n+1)-路径和最左边的长度为(j)的奇参数的标记路径段(被x轴所2n+1。如果这段的起点3.理2证下面的引理是众所周知的，它有几个组合证明[2]引理5.在第一步后再也不返回x轴且长度为2n的路径数量为3，(1)和(2)式的左边给出一个有趣的组合解释。引理6. 4neven-zeroed(b)是从原点到(4n+1,1)的even-zeroed路径数证明.(a)35，最右边的x4i，4neven-zeroed路径数为。(b)x4i(其次是一个向上的步骤)，且是从原点到的路径标准解释。3even-zeroed，而第4列的总标记数字是。为了证明定理2，我们只需证。关键要观察的是，可以容易地通过和的计算得到，但由第1节我们知道，所以事实上可以容易地通过的计算得2。图3.even-zeroed路径数引理7.长度为4n的even-zeroed路径数为 过n的归纳，我们可以证明。当n=0显然是正确的。我们假成立。显然，每中的路径是一个中的路径扩展4步之后得到的路径。对中的每个路径都有16个可能的扩展。但是一些16扩展却不是中。这些“错误”的扩展全是从原点到(4n+1,-1)且后面跟着一步下even-zeroedx6(b)，4.交替卷 中 二项式系Spivey[4]，定理82，8合证明都是定理2的一个组合证明。相反地，我们一节的证明也能够被理解为8定理证明.利用引理3， 用来表示这些对组成的集合。利用引理3，等式左边是和为even参数的平衡路径且有一个形式为4t+2的x轴截距(对于整数t)，并满足的对数。用来表示这些对组成的集合我们会给出一个与之间的双射，如上所述，这意味着。选择中任意一个元素。用L表示从原点到它最左边的x轴截距为4t+2的子路径，中其余的子路径用R表示。然后将的象定义为，此处是L和的4)。 推论10.参考文 G.E.Andrews,OnShapiro’sCatalanconvolution,Adv.inAppl.Math.46(2011) Ö.E˘gecio˘glu,A.King,RandomwalksandCatalanfactorization,Congr.Numer.138(1999)129–140. T.Koshy,CatalanNumberswithApplications,OxfordUniversityPress,NewYork,M.Spivey,Combinatorialinterpretationofthealternatingconvolutionofthecentralbinomial