论文部分内容阅读
组合数学是研究离散结构的存在、计数、分析和优化的一门学科。现代组合数学研究的主要内容之一是集合的组合结构,即把集合的元素按要求分成各种组态的理论和技术。对各种事件、序列、图形等的计数和枚举是组合分析的主要研究内容。其中一个最基本的研究对象是排列和组合,对于排列上的各种统计量和性质的研究,以及相关的多重排列、分拆、对合和匹配等结构的研究始终是组合数学的重要课题。特别是对排列等结构加限制,即有禁排列、有禁分拆等问题,在最近的十几年来更是引起许多组合数学家的兴趣和关注,成为了组合数学中的一个新的方向和热点。
另一个基本研究对象是格路径和树,它们自身的结构、计数的研究一直是组合数学中的重要部分,而且在生物信息学、计算机科学、物理学中都有广泛的应用。由于格路径和树结构天然的直观性,组合数学中的许多问题都可以归结为对格路径和树结构的探讨。
组合数学的主要研究方法有反演公式方法、生成函数方法,递归公式方法,组合双射法等。其中生成函数方法,递归公式方法是基本的方法,组合双射法可以直观而简单地给出事件、序列和图形之间的关系与内在的结构。近年来,这种构造性的组合数学成为组合数学领域的一个非常热门的课题。
本文对组合数学中的三种格路径Dyck路径、Motzkin路径和、Schr(o)der路径进行研究,并将它们统一起来做以推广,提出了k-路径:由上升步(1,1),下降步(1,-1)和水平步(k,0)构成的,从(0,0)到(n,0)的格路径。并且还给出了这几类格路径与有序树之间的双射关系。
本文研究了k-路径集合中各条路径与x轴限定的区域的总面积的计数满足的一个仅与k相关的四元递归关系式。并分别用双射法和生成函数法来证明En中路径下的所有区域的总面积等于从(0,0)到(n-2,0)由上升步(1,1),下降步(1,-1),水平步(k,0)构成的非严格约束的格路径与x轴相交的格点数。