查看“︁達文波特-欣策爾序列”︁的源代码

在[[组合数学]]中，'''達文波特–欣策爾序列'''是指对任意两个符号交替出现的次数作出限制的序列。達文波特–欣策爾序列其最大长度的界等于序列中不同符号的数目乘以一个渐近意义上很小但并非常数的因子，该因子取决于前述的交替次数上限。達文波特–欣策爾序列最早是由{{link-en|哈罗德·达文波特|Harold Davenport}}和{{link-en|安杰伊·欣策尔|Andrzej Schinzel}}于 1965&nbsp;年为研究[[线性微分方程]]而定义的。该序列及其长度的渐近界继 {{harvtxt|Atallah|1985}} 一文之后成为了[[离散几何]]与[[计算几何|几何算法]]分析领域的标准工具。<ref>{{harvtxt|Sharir|Agarwal|1995}}，第 x 至第 2&nbsp;页。</ref>

==定义==
有限序列 ''U'' = ''u''<sub>1</sub>, ''u''<sub>2</sub>, ''u''<sub>3</sub>, ... 满足下列条件时被称作是 ''s''&nbsp;阶 達文波特–欣策爾序列：
#任意两个相邻的元素不相等。
#若 ''x'' 和 ''y'' 是序列中不同的两个元素，那么该序列中不包含 ''x'' 和 ''y'' 交替出现，共有 ''s''&nbsp;+&nbsp;2 个数值的子序列 ... ''x'', ... ''y'', ..., ''x'', ..., ''y'', ...。

例如，序列
:1, 2, 1, 3, 1, 3, 2, 4, 5, 4, 5, 2, 3
是一个 3&nbsp;阶 達文波特-欣策爾序列：它包含了长度为 4 的交替序列，如 ...1, ... 2, ... 1, ... 2, ... （作为子序列在整个序列中出现了 4&nbsp;次），但它并不包含任何长度为 5 的交替序列。

如果一个 ''s''&nbsp;阶 達文波特-欣策爾序列包含了 ''n''&nbsp;个不同的值，就称其为 (''n'',''s'') 達文波特-欣策爾序列，或称 ''DS''(''n'',''s'') 序列。<ref>关于这些记号，参见 {{harvtxt|Sharir|Agarwal|1995}} 的第 1&nbsp;页。</ref>

==长度的界==
相关文献已经研究了 ''DS''(''n'',''s'') 序列在[[渐近分析|渐近]]意义上的复杂度：对于 ''n'' 趋于无穷，假设 ''s'' 是固定的常数，已经得出了对于所有 ''s'' 的近乎紧确的界。令 λ<sub>''s''</sub>(''n'') 表示最长的 ''DS''(''n'',''s'') 序列的长度。目前已知的 λ<sub>''s''</sub> 的最佳的界可用[[阿克曼函数#反函数|反阿克曼函数]]
:&alpha;(''n'') = min { ''m'' | A(''m'',''m'') ≥ ''n'' }
来描述。其中 ''A'' 是阿克曼函数。由于阿克曼函数增长得很快，其反函数的增长就非常慢，以至于在所有的实际规模的问题中，该函数的值都不会超过常数 4。<ref>{{harvtxt|Sharir|Agarwal|1995}}，第 14&nbsp;页。</ref>

用[[大O符号]]和[[大Θ符号]]可以表述下面这些已知的渐近界：
*λ<sub>1</sub>(''n'')&nbsp;=&nbsp;''n''.<ref name="DS12">{{harvtxt|Sharir|Agarwal|1995}}，第 6&nbsp;页。</ref>
*λ<sub>2</sub>(''n'')&nbsp;=&nbsp;2''n''&nbsp;&minus;&nbsp;1.<ref name="DS12" />
*<math>2n\alpha(n)-O(n)\le\lambda_3(n)\le2n\alpha(n)+O(n\sqrt{\alpha(n)})</math>.<ref>{{harvtxt|Sharir|Agarwal|1995}}，第 2&nbsp;章，第 12 至第 42&nbsp;页；{{harvtxt|Hart|Sharir|1986}}；{{harvtxt|Wiernik|Sharir|1988}}；{{harvtxt|Komjáth|1988}}；{{harvtxt|Klazar|1999}}；{{harvtxt|Nivasch|2009}}。</ref> 这个界可以在常数因子的误差范围内达到：对于平面上的 ''n'' 条线段，存在一种摆放它们的方式，使得它们的下包络线（{{Lang-en|lower envelope}}）的线段条数的复杂度达到 Ω(''n''&nbsp;α(''n''))。<ref>{{harvtxt|Sharir|Agarwal|1995}}，第 4&nbsp;章，第 86 至第 114&nbsp;页；{{harvtxt|Wiernik|Sharir|1988}}。</ref>
*对于 ''s'' ≥ 4 且 ''s'' 为偶数，<ref name="high-order">{{harvtxt|Sharir|Agarwal|1995}}，第 3&nbsp;章，第 43 至第 85&nbsp;页；{{harvtxt|Agarwal|Sharir|1989}}；{{harvtxt|Nivasch|1999}}。</ref>
::<math>\lambda_s(n)=n\cdot 2^{\frac{1}{t!}\alpha(n)^t(1+o(1))}</math>, 其中 ''t''&nbsp;=&nbsp;(''s''&nbsp;&minus;&nbsp;2)/2.
*对于 ''s'' ≥ 5 且 ''s'' 为奇数，目前已知的最佳的界是 <ref name="high-order" />
::<math>\lambda_s(n) < n\cdot 2^{\frac{1}{t!}\alpha(n)^t\log\alpha(n)(1+o(1))}</math>, 其中 ''t''&nbsp;=&nbsp;(''s''&nbsp;&minus;&nbsp;3)/2.
然而这个界并未被确认是紧确的。<ref name="high-order" />

当 ''s'' 是变量而 ''n'' 是一个很小的常数时，λ<sub>''s''</sub>(''n'') 的值目前也已知道：<ref>{{harvtxt|Roselle|Stanton|1970/71}}.</ref>
:<math>\lambda_s(2)=s+1\,</math>
:<math>\lambda_s(3)=3s-2+(s\, \bmod \, 2)</math>
:<math>\lambda_s(4)=6s-2+(s\, \bmod\, 2).</math>

==在下包络线中的应用==
[[Image:Line segment lower envelope.svg|thumb|300px|由一组线段的下包络线形成的一个 3&nbsp;阶 達文波特-欣策爾序列]]
以实数 ''x'' 为变量的函数族 &fnof;<sub>''i''</sub>(''x'') 的'''下包络线'''（{{Lang-en|lower envelope}}）可用这族函数逐点取的最小值
:&fnof;(''x'')&nbsp;=&nbsp;min<sub>''i''</sub>&fnof;<sub>''i''</sub>(''x'')
来描述。
我们假定这族函数都非常理想化：它们都是[[连续函数|连续]]的，而且它们之中任意两个函数都只能在最多 ''s'' 个自变量取值处相等。有了这些假设，我们就可以把实数轴划分为有限个[[区间]]，使得在每一个这样的区间当中，都存在一个函数，其值比其他任何函数的值都要小。用某个区间上值最小的函数为该区间标上号，这些区间所形成的序列就是一个 ''s''&nbsp;阶 達文波特-欣策爾序列。因此，''s''&nbsp;阶 達文波特-欣策爾序列长度的上界也就是下包络线在这种表示方法中区间数目的上界。

在{{link-en|哈罗德·达文波特|Harold Davenport|达文波特}}和{{link-en|安杰伊·欣策尔|Andrzej Schinzel|欣策尔}}最初提出的应用当中，上述函数族就是某个 ''s''&nbsp;阶齐次[[线性微分方程]]的不同的解之集合。任意两个不同的解最多只能有 ''s'' 个相同的值，所以 ''n'' 个两两不同的解的下包络线就可形成一个 ''DS''(''n'',''s'') 序列。

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

==另见==
* {{link-en|无平方字|Squarefree word}}

==注释==
{{reflist|2}}

==参考文献==
*{{citation
 | last1 = Agarwal | first1 = P. K. | author1-link = Pankaj K. Agarwal
 | last2 = Sharir | first2 = Micha | authorlink2 = Micha Sharir
 | last3 = Shor | first3 = P. | authorlink3 = Peter Shor
 | title = Sharp upper and lower bounds on the length of general Davenport–Schinzel sequences
 | journal = Journal of Combinatorial Theory, Series A
 | volume = 52 | issue = 2 | year = 1989 | pages = 228–274
 | mr = 1022320 | doi = 10.1016/0097-3165(89)90032-0}}.
*{{citation
 | last = Atallah | first = Mikhail J.
 | authorlink = Mikhail Atallah
 | title = Some dynamic computational geometry problems
 | journal = Computers and Mathematics with Applications
 | mr = 0822083 | doi = 10.1016/0898-1221(85)90105-1
 | volume = 11 | pages = 1171–1181 | year = 1985}}.
*{{citation
 | last1 = Davenport | first1 = H. | authorlink1 = Harold Davenport
 | last2 = Schinzel | first2 = Andrzej | authorlink2 = Andrzej Schinzel
 | title = A combinatorial problem connected with differential equations
 | journal = American Journal of Mathematics
 | volume = 87 | year = 1965 | pages = 684–694
 | mr = 0190010 | doi = 10.2307/2373068
 | jstor = 2373068
 | issue = 3
 | publisher = The Johns Hopkins University Press}}.
*{{citation
 | last1 = Hart | first1 = S.
 | last2 = Sharir | first2 = Micha | authorlink2 = Micha Sharir
 | title = Nonlinearity of Davenport–Schinzel sequences and of generalized path compression schemes
 | journal = Combinatorica
 | volume = 6 | issue = 2 | year = 1986 | pages = 151–177
 | mr = 0875839 | doi = 10.1007/BF02579170}}.
*{{citation
 | last = Klazar | first = M.
 | contribution = On the maximum lengths of Davenport–Schinzel sequences
 | pages = 169–178
 | publisher = American Mathematical Society
 | series = DIMACS Series in Discrete Mathematics and Theoretical Computer Science
 | title = Contemporary Trends in Discrete Mathematics
 | volume = 49
 | year = 1999}}.
*{{citation
 | authorlink = Péter Komjáth
 | last = Komjáth | first = Péter
 | title = A simplified construction of nonlinear Davenport–Schinzel sequences
 | journal = Journal of Combinatorial Theory, Series A
 | volume = 49 | year = 1988 | issue = 2 | pages = 262–267
 | mr = 0964387 | doi = 10.1016/0097-3165(88)90055-6}}.
*{{citation
 |last1   = Mullin
 |first1  = R. C.
 |last2   = Stanton
 |first2  = R. G.
 |title   = A map-theoretic approach to Davenport-Schinzel sequences.
 |journal = Pacific Journal of Mathematics
 |volume  = 40
 |year    = 1972
 |pages   = 167–172
 |url     = http://projecteuclid.org/getRecord?id=euclid.pjm/1102968831
 |mr      = 0302601
 |doi     = 10.2140/pjm.1972.40.167
}}{{dead link|date=2018年2月 |bot=InternetArchiveBot |fix-attempted=yes }}.
*{{citation
 |last         = Nivasch
 |first        = Gabriel
 |contribution = Improved bounds and new techniques for Davenport–Schinzel sequences and their generalizations
 |arxiv        = 0807.0484
 |pages        = 1–10
 |title        = Proc. 20th ACM-SIAM Symp. Discrete Algorithms
 |url          = http://www.siam.org/proceedings/soda/2009/SODA09_001_nivaschg.pdf
 |year         = 2009
 |access-date  = 2014-07-09
 |archive-url  = https://web.archive.org/web/20121018164441/http://siam.org/proceedings/soda/2009/SODA09_001_nivaschg.pdf
 |archive-date = 2012-10-18
 |dead-url     = yes
}}.
*{{citation
 | last1 = Roselle | first1 = D. P. | author1-link = David Roselle
 | last2 = Stanton | first2 = R. G.
 | title = Some properties of Davenport-Schinzel sequences
 | journal = Acta Arithmetica
 | volume = 17 | year = 1970/71 | pages = 355–362
 | mr = 0284414 }}.
*{{citation
 | last1 = Sharir | first1 = Micha | authorlink1 = Micha Sharir
 | last2 = Agarwal | first2 = Pankaj K.
 | title = Davenport–Schinzel Sequences and Their Geometric Applications
 | publisher = Cambridge University Press
 | year = 1995
 | isbn = 0-521-47025-0}}.
*{{citation
 | last1 = Stanton | first1 = R. G.
 | last2 = Dirksen | first2 = P. H.
 | title = Davenport-Schinzel sequences.
 | journal = Ars Combinatoria
 | volume = 1 | year = 1976 | issue = 1 | pages = 43–51
 | mr = 0409347 }}.
*{{citation
 | last1 = Stanton | first1 = R. G.
 | last2 = Roselle | first2 = D. P. | author2-link = David Roselle
 | contribution = A result on Davenport-Schinzel sequences
 | title = Combinatorial theory and its applications, III (Proc. Colloq., Balatonfüred, 1969)
 | pages = 1023–1027
 | publisher = North-Holland | location = Amsterdam | year = 1970
 | mr = 0304189 }}.
*{{citation
 | last1 = Wiernik | first1 = Ady
 | last2 = Sharir | first2 = Micha | authorlink2 = Micha Sharir
 | title = Planar realizations of nonlinear Davenport–Schinzel sequences by segments
 | journal = Discrete &amp; Computational Geometry
 | volume = 3 | issue = 1 | year = 1988 | pages = 15–47
 | mr = 0918177 | doi = 10.1007/BF02187894}}.

==外部链接==
* [http://mathworld.wolfram.com/Davenport-SchinzelSequence.html Davenport-Schinzel Sequence] {{Wayback|url=http://mathworld.wolfram.com/Davenport-SchinzelSequence.html |date=20210225182213 }}（[[MathWorld]] 上的页面）
* [http://planning.cs.uiuc.edu/node304.html  Davenport-Schinzel Sequences] {{Wayback|url=http://planning.cs.uiuc.edu/node304.html |date=20200113004458 }}，''Motion Planning'' 一书中的一节，作者是 Steven M. LaValle。

[[Category:序列]]
[[Category:词语组合]]
[[Category:離散幾何]]