达文波特-欣策尔序列

✍ dations ◷ 2025-04-04 06:44:13 #组合数学

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

相关

  • 二羟丙酮二羟基丙酮,丙糖的一种,为白色潮解结晶粉末,有凉的甜味和特征性气味。是最简单的酮糖。无手性中心,故无光学活性。通常以二聚体存在,二聚体可缓慢溶于1份水与15份乙醇的混合液中
  • T-MobileT-Mobile是一家跨国电信公司,是德国电信的子公司,属于Freemove联盟。T-Mobile在西欧和美国营运GSM网络并通过金融手段参与东欧和东南亚的网络营运。该公司拥有1.09亿用户,是世
  • 拉丁语族罗马语族(又称罗曼语族、拉丁语族),属于印欧语系,是从意大利语族衍生出来的现代语族,主要包括从拉丁语演化而来的现代诸语言。操罗马语族语言的人主要包括传统意义上的“欧洲拉丁
  • 泻湖潟湖是一种因为海湾被沙洲所封闭而演变成的湖泊,所以一般都在海边。这些湖本来都是海湾,后来在海湾的出海口处由于泥沙沉积,使出海口形成了沙洲,继而将海湾与海洋分隔,因而成为湖
  • N-末端N端(亦作N-端,英语:N-terminus),又称氮端、氨基端,指多肽链具有游离的α氨基的末端。在转译过程中,多肽链是从N端往C端合成的,因而在书写表示多肽序列时,从N端开始书写,从左到右写到C
  • 股份制关键伙伴关系 · 关键活动 · 关键资源 价值主张 · 顾客关系 · 行销通路 顾客区隔股份公司(英语:Joint-stock company)指由两个或以上个体持有公司股票份额的企业组织形
  • A-10四个 LAU-61/LAU-68火箭荚舱(每个含19x/7x Hydra 70毫米火箭弹或APKWS II导引火箭) 四个 LAU-5003火箭荚舱(每个含19x CRV7 70毫米火箭弹) 四个 LAU-10火箭荚舱(每个含4x 127毫米
  • 亚洲野猫亚洲野猫(学名:Felis silvestris ornata)是非洲野猫的一个亚种,分布于里海附近至中国西部和印度西部的广大地区。高加索山脉将其与欧洲野猫分开。其现存种群数目并未曾得到统计,
  • 军人身份确认牌军人身份确认牌(亦称兵籍牌、军籍牌、兵籍名牌、金属身份识别证),又俗称“狗牌”(Dog tag),始于美国南北战争时期,是为了便于对战场上的伤亡士兵进行身份鉴别,以及了解诸如血型、预
  • 凯尔采县坐标:50°53′N 20°37′E / 50.883°N 20.617°E / 50.883; 20.617凯尔采县(波兰语:Powiat kielecki),是波兰的县份,位于该国中部,由圣十字省负责管辖,首府设于凯尔采,面积2,247平方