達文波特-欣策爾序列

在組合數學中，達文波特–欣策爾序列是指對任意兩個符號交替出現的次數作出限制的序列。達文波特–欣策爾序列其最大長度的界等於序列中不同符號的數目乘以一個漸近意義上很小但並非常數的因子，該因子取決於前述的交替次數上限。達文波特–欣策爾序列最早是由哈羅德·達文波特和安傑伊·欣策爾於 1965 年為研究線性微分方程而定義的。該序列及其長度的漸近界繼 Atallah (1985) 一文之後成為了離散幾何與幾何算法分析領域的標準工具。

定義

有限序列 U = u₁, u₂, u₃, ... 滿足下列條件時被稱作是 s 階 達文波特–欣策爾序列：

1. 任意兩個相鄰的元素不相等。
2. 若 x 和 y 是序列中不同的兩個元素，那麼該序列中不包含 x 和 y 交替出現，共有 s + 2 個數值的子序列 ... x, ... y, ..., x, ..., y, ...。

例如，序列

1, 2, 1, 3, 1, 3, 2, 4, 5, 4, 5, 2, 3

是一個 3 階 達文波特-欣策爾序列：它包含了長度為 4 的交替序列，如 ...1, ... 2, ... 1, ... 2, ... （作為子序列在整個序列中出現了 4 次），但它並不包含任何長度為 5 的交替序列。

如果一個 s 階 達文波特-欣策爾序列包含了 n 個不同的值，就稱其為 (n,s) 達文波特-欣策爾序列，或稱 DS(n,s) 序列。

長度的界

相關文獻已經研究了 DS(n,s) 序列在漸近意義上的複雜度：對於 n 趨於無窮，假設 s 是固定的常數，已經得出了對於所有 s 的近乎緊確的界。令 λ_s(n) 表示最長的 DS(n,s) 序列的長度。目前已知的 λ_s 的最佳的界可用反阿克曼函數

α(n) = min { m | A(m,m) ≥ n }

來描述。其中 A 是阿克曼函數。由於阿克曼函數增長得很快，其反函數的增長就非常慢，以至於在所有的實際規模的問題中，該函數的值都不會超過常數 4。

用大O符號和大Θ符號可以表述下面這些已知的漸近界：

• λ₁(n) = n.
• λ₂(n) = 2n − 1.
• $2n\alpha (n)-O(n)\leq \lambda _{3}(n)\leq 2n\alpha (n)+O(n{\sqrt {\alpha (n)}})$. 這個界可以在常數因子的誤差範圍內達到：對於平面上的 n 條線段，存在一種擺放它們的方式，使得它們的下包絡線（英語：lower envelope）的線段條數的複雜度達到 Ω(n α(n))。
• 對於 s ≥ 4 且 s 為偶數，

$\lambda _{s}(n)=n\cdot 2^{{\frac {1}{t!}}\alpha (n)^{t}(1+o(1))}$, 其中 t = (s − 2)/2.

• 對於 s ≥ 5 且 s 為奇數，目前已知的最佳的界是

$\lambda _{s}(n)<n\cdot 2^{{\frac {1}{t!}}\alpha (n)^{t}\log \alpha (n)(1+o(1))}$, 其中 t = (s − 3)/2.

然而這個界並未被確認是緊確的。

當 s 是變量而 n 是一個很小的常數時，λ_s(n) 的值目前也已知道：

$\lambda _{s}(2)=s+1\,$

$\lambda _{s}(3)=3s-2+(s\,{\bmod {\,}}2)$

$\lambda _{s}(4)=6s-2+(s\,{\bmod {\,}}2).$

在下包絡線中的應用

由一組線段的下包絡線形成的一個 3 階 達文波特-欣策爾序列

以實數 x 為變量的函數族 ƒ_i(x) 的下包絡線（英語：lower envelope）可用這族函數逐點取的最小值

ƒ(x) = min_iƒ_i(x)

來描述。 我們假定這族函數都非常理想化：它們都是連續的，而且它們之中任意兩個函數都只能在最多 s 個自變量取值處相等。有了這些假設，我們就可以把實數軸劃分為有限個區間，使得在每一個這樣的區間當中，都存在一個函數，其值比其他任何函數的值都要小。用某個區間上值最小的函數為該區間標上號，這些區間所形成的序列就是一個 s 階 達文波特-欣策爾序列。因此，s 階 達文波特-欣策爾序列長度的上界也就是下包絡線在這種表示方法中區間數目的上界。

在達文波特和欣策爾最初提出的應用當中，上述函數族就是某個 s 階齊次線性微分方程的不同的解之集合。任意兩個不同的解最多只能有 s 個相同的值，所以 n 個兩兩不同的解的下包絡線就可形成一個 DS(n,s) 序列。

下包絡線的概念也可以應用於分段連續或僅在實數軸的某些區間上才有定義的函數族；但在這些情況下，計算達文波特-欣策爾序列的階時，不僅要算不同的函數其圖像最多能在幾個點處相交，函數中不連續點的個數和函數定義區間的端點個數也要算。例如，平面上一條非豎直的線段可看作是把某個區間上的 x 值映射到相應的 y 值的函數圖形，而一族這樣的線段的下包絡線形成的是3 階的達文波特-欣策爾序列，因為任何兩條線段可以形成長度最大為 4 的交替子序列。

另見

• 無平方字

參考文獻

• Agarwal, P. K.; Sharir, Micha; Shor, P., Sharp upper and lower bounds on the length of general Davenport–Schinzel sequences, Journal of Combinatorial Theory, Series A, 1989, 52 (2): 228–274, MR 1022320, doi:10.1016/0097-3165(89)90032-0 .
• Atallah, Mikhail J., Some dynamic computational geometry problems, Computers and Mathematics with Applications, 1985, 11: 1171–1181, MR 0822083, doi:10.1016/0898-1221(85)90105-1 .
• Davenport, H.; Schinzel, Andrzej, A combinatorial problem connected with differential equations, American Journal of Mathematics (The Johns Hopkins University Press), 1965, 87 (3): 684–694, JSTOR 2373068, MR 0190010, doi:10.2307/2373068 .
• Hart, S.; Sharir, Micha, Nonlinearity of Davenport–Schinzel sequences and of generalized path compression schemes, Combinatorica, 1986, 6 (2): 151–177, MR 0875839, doi:10.1007/BF02579170 .
• Klazar, M., On the maximum lengths of Davenport–Schinzel sequences, Contemporary Trends in Discrete Mathematics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 49, American Mathematical Society: 169–178, 1999 .
• Komjáth, Péter, A simplified construction of nonlinear Davenport–Schinzel sequences, Journal of Combinatorial Theory, Series A, 1988, 49 (2): 262–267, MR 0964387, doi:10.1016/0097-3165(88)90055-6 .
• Mullin, R. C.; Stanton, R. G., A map-theoretic approach to Davenport-Schinzel sequences., Pacific Journal of Mathematics, 1972, 40: 167–172, MR 0302601, doi:10.2140/pjm.1972.40.167 .
• Nivasch, Gabriel, Improved bounds and new techniques for Davenport–Schinzel sequences and their generalizations, Proc. 20th ACM-SIAM Symp. Discrete Algorithms (PDF): 1–10, 2009 [2014-07-09], arXiv:0807.0484 , （原始內容 (PDF)存檔於2012-10-18） .
• Roselle, D. P.; Stanton, R. G., Some properties of Davenport-Schinzel sequences, Acta Arithmetica, 1970/71, 17: 355–362, MR 0284414  .
• Sharir, Micha; Agarwal, Pankaj K., Davenport–Schinzel Sequences and Their Geometric Applications, Cambridge University Press, 1995, ISBN 0-521-47025-0 .
• Stanton, R. G.; Dirksen, P. H., Davenport-Schinzel sequences., Ars Combinatoria, 1976, 1 (1): 43–51, MR 0409347 .
• Stanton, R. G.; Roselle, D. P., A result on Davenport-Schinzel sequences, Combinatorial theory and its applications, III (Proc. Colloq., Balatonfüred, 1969), Amsterdam: North-Holland: 1023–1027, 1970, MR 0304189 .
• Wiernik, Ady; Sharir, Micha, Planar realizations of nonlinear Davenport–Schinzel sequences by segments, Discrete & Computational Geometry, 1988, 3 (1): 15–47, MR 0918177, doi:10.1007/BF02187894 .

外部連結

• Davenport-Schinzel Sequence （頁面存檔備份，存於網際網路檔案館）（MathWorld 上的頁面）
• Davenport-Schinzel Sequences （頁面存檔備份，存於網際網路檔案館），Motion Planning 一書中的一節，作者是 Steven M. LaValle。