Последовательность Дэвенпорта — Шинцеля

В комбинаторике последовательность Дэвенпорта — Шинцеля является последовательностью символов, в которой любые два символа могут появиться в чередующемся порядке ограниченное число раз. Максимальная возможная длина последовательности Дэвенпорта — Шинцеля ограничена числом символов, умноженным на небольшой постоянный множитель, который зависит от числа разрешённых чередований. Последовательности Дэвенпорта — Шинцеля были впервые определены в 1965 году Гарольдом Дэвенпортом и Анджеем Шинцелем для анализа линейных дифференциальных уравнений. Следуя Аталла, эти последовательности и границы их длин стали стандартным средством в комбинаторной геометрии и в анализе геометрических алгоритмов.

Определение

Говорят, что конечная последовательность U=u₁, u₂, u₃ является последовательностью Дэвенпорта — Шинцеля порядка s, если она удовлетворяет следующим двум свойствам:

1. Никакие два последовательных значения в последовательности не равны друг другу.
2. Если x и y — два различные значения, появляющиеся в последовательности, то последовательность не содержит подпоследовательность … x, … y, …, x, …, y, … состоящую из s + 2 чередующихся значений x и y.

Например, последовательность

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

является последовательностью Дэвенпорта — Шинцеля порядка 3 — она содержит чередующаяся последовательность длины четыре, такую как …1, … 2, … 1, … 2, … (появляется четырьмя разными способами как последовательность полной последовательности), но она не содержит подпоследовательности длины пять.

Если последовательность Дэвенпорта — Шинцеля порядка 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» большое, известны следующие границы:

• $\lambda _{0}(n)=1$.
• $\lambda _{1}(n)=n$
• $\lambda _{2}(n)=2n-1$.

$\lambda _{3}(n)=2n\alpha (n)+O(n)$ . Эта граница сложности может быть реализована с точностью до константы отрезками — существует такое расположение n отрезков на плоскости, нижняя огибающая которых имеет сложность Ω(n α(n)) .

• $\lambda _{4}(n)=\Theta (n2^{\alpha (n)})$.
• $\lambda _{5}(n)=\Theta (n\alpha (n)2^{\alpha (n)})$.

• Для чётных и нечётных значений s ≥ 6

$\lambda _{s}(n)=n\cdot 2^{{\frac {1}{t!}}\alpha (n)^{t}+O(\alpha (n)^{t-1})}$, где $t=\left\lfloor {\frac {s-2}{2}}\right\rfloor$.

Значение λ_s(n) также известно, если s переменна, а n — малая константа:

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

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

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

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

Если s является функцией от n, верхняя и нижняя граница последовательности Дэвенпорта — Шинцеля не являются точными.

• Если $s>n^{1/t}(t-1)!$, $\lambda _{s}(n)=\Omega (n^{2}s/(t-1)!)$ и $\lambda _{s}(n)=O(n^{2}s)$.
• Если $\log \log n<s=n^{o(1)}$, $\lambda _{s}(n)=\Omega \left(n\left({\frac {s}{2\log \log _{s}n}}\right)^{\log \log _{s}n}\right)$.
• Если $s\leq \log \log n$, $\lambda _{s}(n)=\Omega (n2^{s})$.

Приложение к нижним огибающим

Последовательность Дэвенпорта — Шинцеля порядка 3, образованная нижней огибающей отрезков.

Нижняя огибающая множества функций ƒ_i(x) от вещественной переменной x является функцией, заданной поточечным минимумом:

ƒ(x) = min_iƒ_i(x).

Предположим, что эти функции имеют очень хорошее поведение — они все непрерывны и любые две из них равны максимум в s значениях. При этих предположениях вещественную ось можно разбить на конечное число промежутков, внутри каждого из которых одна функция имеет значения, меньшие, чем значения всех других функций. Последовательность таких интервалов, помеченных минимальной функцией внутри каждого интервала, образует последовательность Дэвенпорта — Шинцеля порядка s. Таким образом, любая верхняя граница сложности последовательности Дэвенпорта — Шинцеля с этим порядком также ограничивает число интервалов в таком представлении нижней огибающей.

В оригинальном приложении Дэвенпорта — Шинцеля рассматривались функции, являющиеся различными решениями одного и того же однородного линейного дифференциального уравнения порядка s. Любые два различных решения имеют не более s общих значений, так что нижняя огибающая множества n различных решений образует DS(n,s)-последовательность.

Та же концепция нижней огибающей может быть применена к функциям, которые только кусочно непрерывны или определены только на интервалах вещественной оси. Однако в этом случае точки разрывности функций и концы интервалов, в которых каждая функция задана, добавляются к последовательности. Например, невертикальный отрезок на плоскости можно интерпретировать как график функции, отображающей точки x интервала в соответствующие значения y, и нижняя огибающая набора отрезков образует последовательность Дэвенпорта — Шинцеля порядка три, поскольку любые два отрезка могут образовать перемежающуюся последовательность длины, не превосходящей 4.

См. также

• Бесквадратное слово

Ссылки

• Davenport-Schinzel Sequence, from MathWorld.
• Davenport-Schinzel Sequences, a section in the book Motion Planning, by Steven M. LaValle.