达文波特-欣策尔序列

✍ dations ◷ 2025-08-03 16:56:07 #组合数学

在组合数学中,达文波特–欣策尔序列是指对任意两个符号交替出现的次数作出限制的序列。达文波特–欣策尔序列其最大长度的界等于序列中不同符号的数目乘以一个渐近意义上很小但并非常数的因子,该因子取决于前述的交替次数上限。达文波特–欣策尔序列最早是由哈罗德·达文波特(英语: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 的交替子序列。

相关

  • 乌拉圭乌拉圭东岸共和国(西班牙语:República Oriental del Uruguay),通称乌拉圭(Uruguay,西班牙语发音:.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertin
  • 先天性疾病先天性障碍,又称先天性疾病、先天畸形、先天缺陷,是指发育中的胎儿因为遗传性疾病或发育环境等因素导致某个部位特征结构畸形,导致在婴儿出生时即有的病症,包括了身体(英语:Physic
  • 肯尼思·博尔丁肯尼思·爱华·博尔丁(英语:Kenneth Ewart Boulding,1910年1月18日-1993年3月18日),生于英国英格兰利物浦,经济学家,教育学家,和平主义者,诗人,宗教神秘主义者,贵格会教徒,系统论科学家,哲
  • 国际泛欧联盟国际泛欧联盟(International Paneuropean Union)是最始主张进行欧洲统一运动(European unification movement),或称泛欧运动(Paneuropean Movement,Pan-Europa Movement)的一个组织
  • 临淄区临淄区位于中华人民共和国山东省中部,是淄博市一个石油化工产业密集的市辖区。在古代曾为西周、春秋、战国时的大国齐国国都,1994年被国务院定为国家历史文化名城。临淄,古称营
  • 明水组明水组是位于中国黑龙江绥化市一带以及吉林、内蒙古的上白垩世地层,1960年由松辽石油勘探局综合研究大队命名。该地层以灰棕、灰白、灰黑色泥岩、粉砂质泥岩、粉砂岩(上部),灰绿
  • 天使演唱会PC版(2001年)封面《天使演唱会》是日本工画堂工作室(工画堂スタジオ)所发行的音乐冒险游戏。故事叙述想成为音乐家的一对青梅竹马,为了参加一年一度在王都举行的音乐会,而离开故乡
  • 深夜FM《深夜FM》(韩语:심야의 FM,英语:)是一部韩国惊悚片,2010年10月14日发行于韩国,连续2周登上韩国周末排行榜,创下91亿韩元(约2亿4千万台币)的票房成绩。深夜电台节目《深夜FM》的电台DJ
  • 邮戳邮戳是邮局盖在实寄过的邮件包裹等上的各类戳记,包括普通邮戳、纪念邮戳、宣传邮戳等。是历史的反映。收集邮戳已经成为集邮必不可少的一项内容。现在也出现电子邮戳等新种类
  • 米卢廷·米兰科维奇米卢廷·米兰科维奇(塞尔维亚语:Милутин Миланковић,拉丁化:Milutin Milanković,发音:,1879年5月28日-1958年12月12日)是一位塞尔维亚土木工程师、地球物理学家和