达文波特-欣策尔序列

✍ dations ◷ 2025-08-24 08:00:45 #组合数学

在组合数学中,达文波特–欣策尔序列是指对任意两个符号交替出现的次数作出限制的序列。达文波特–欣策尔序列其最大长度的界等于序列中不同符号的数目乘以一个渐近意义上很小但并非常数的因子,该因子取决于前述的交替次数上限。达文波特–欣策尔序列最早是由哈罗德·达文波特(英语:Harold Davenport)和安杰伊·欣策尔(英语:Andrzej Schinzel)于 1965 年为研究线性微分方程而定义的。该序列及其长度的渐近界继 Atallah (1985) 一文之后成为了离散几何与几何算法分析领域的标准工具。

有限序列 = 1, 2, 3, ... 满足下列条件时被称作是  阶 达文波特–欣策尔序列:

例如,序列

是一个 3 阶 达文波特-欣策尔序列:它包含了长度为 4 的交替序列,如 ...1, ... 2, ... 1, ... 2, ... (作为子序列在整个序列中出现了 4 次),但它并不包含任何长度为 5 的交替序列。

如果一个  阶 达文波特-欣策尔序列包含了  个不同的值,就称其为 (,) 达文波特-欣策尔序列,或称 (,) 序列。

相关文献已经研究了 (,) 序列在渐近意义上的复杂度:对于 趋于无穷,假设 是固定的常数,已经得出了对于所有 的近乎紧确的界。令 λ() 表示最长的 (,) 序列的长度。目前已知的 λ 的最佳的界可用反阿克曼函数

来描述。其中 是阿克曼函数。由于阿克曼函数增长得很快,其反函数的增长就非常慢,以至于在所有的实际规模的问题中,该函数的值都不会超过常数 4。

用大O符号和大Θ符号可以表述下面这些已知的渐近界:

然而这个界并未被确认是紧确的。

当 是变量而 是一个很小的常数时,λ() 的值目前也已知道:

以实数 为变量的函数族 ƒ() 的下包络线(英语:lower envelope)可用这族函数逐点取的最小值

来描述。我们假定这族函数都非常理想化:它们都是连续的,而且它们之中任意两个函数都只能在最多 个自变量取值处相等。有了这些假设,我们就可以把实数轴划分为有限个区间,使得在每一个这样的区间当中,都存在一个函数,其值比其他任何函数的值都要小。用某个区间上值最小的函数为该区间标上号,这些区间所形成的序列就是一个  阶 达文波特-欣策尔序列。因此, 阶 达文波特-欣策尔序列长度的上界也就是下包络线在这种表示方法中区间数目的上界。

在达文波特(英语:Harold Davenport)和欣策尔(英语:Andrzej Schinzel)最初提出的应用当中,上述函数族就是某个  阶齐次线性微分方程的不同的解之集合。任意两个不同的解最多只能有 个相同的值,所以 个两两不同的解的下包络线就可形成一个 (,) 序列。

下包络线的概念也可以应用于分段连续或仅在实数轴的某些区间上才有定义的函数族;但在这些情况下,计算达文波特-欣策尔序列的阶时,不仅要算不同的函数其图像最多能在几个点处相交,函数中不连续点的个数和函数定义区间的端点个数也要算。例如,平面上一条非竖直的线段可看作是把某个区间上的 值映射到相应的 值的函数图形,而一族这样的线段的下包络线形成的是3 阶的达文波特-欣策尔序列,因为任何两条线段可以形成长度最大为 4 的交替子序列。

相关

  • 三蝶烯三蝶烯(英语:Triptycene)是一种由蒽和苯炔通过狄尔斯–阿尔德反应合成的芳香烃。三蝶烯还具有三重对称性和桨状结构,是一种桶烯的相似物。三蝶烯的碳架结构十分稳定,所以三蝶烯及
  • 月球陨石月球陨石指源自月球,后来掉落地球表面的陨石。第一颗月球陨石──YAMATO 791197,在1979年于南极洲被发现,但当时仍不知道它源自何方。第一颗确认源自月球的陨石为1981年在南极
  • 民变明朝民变收录了明代主要的起事运动。其中最大的一次是从明熹宗天启七年(1627年)叛乱军与明军作战开始,直至清朝顺治年间才结束的一场战争,被称为明末农民战争。明太祖洪武三年
  • 王赓王赓(1895年5月15日-1942年4月),字受庆,亦作绶卿,江苏无锡人,中华民国陆军少将。官至国民政府兵工署昆明办事处长。亲孔宋系。王赓其家世代显贵,祖父王谷生系浙江湖州知府,浙江总兵,显
  • 希腊尺希腊尺(希腊语:ποῦς ),希腊的长度单位。在不同时期或地区,它曾拥有不同的辅助单位。100尺合1普勒戎(希腊引),600尺合1斯塔达(英语:Stadion (unit))(希腊浪),而5000尺合1里。希腊尺有
  • 镇海蛟川书院镇海蛟川书院位于宁波市镇海区,是一所股份制形式的民办中学,实行董事会领导下的院长负责制。“蛟川”是镇海的别名。清乾隆八年,邑人郑宗璧、李士瀛等将镇海梓荫山下一座罗汉堂
  • 小林斗盦小林斗盦(日语:こばやし とあん,1916年2月23日-2007年8月13日),又名斗庵,本名庸浩,日本书法家及篆刻界名人、全日篆刻联盟会长。小林的篆刻师承自河井荃庐。1984年获得日本艺术院赏
  • 生态系统与生物多样性经济学生态系统与生物多样性经济学(The Economics of Ecosystems and Biodiversity,缩写:TEEB)是关于生物多样性与生态系统的价值评估、示范和政策应用的综合研究体系,由德意志银行的高
  • 苏尔发苏尔发(?-1708年),满洲爱新觉罗氏。豫通亲王多铎之孙、追封睿亲王多尔博第二子。康熙十二年(1673年),在父亲贝勒多尔博死后,袭爵位为贝子。康熙三十九年(1700年),被降爵位为镇国公。康熙
  • 米格尔·普里莫·德里维拉唐·米格尔·普里莫·德里维拉-奥瓦内哈,第二代埃斯特利亚侯爵,第二十二代索布雷蒙特伯爵,卡拉特拉瓦骑士(西班牙语:Don Miguel Primo de Rivera y Orbaneja,1870年1月8日-1930年3