Изменения

{{Определение|definition='''Последовательность''' — (англ. ''sequence'') {{---}} это набор элементов некоторого множества пронумерованный натуральными числами. Последовательность является результатом последовательного выбора элементов множества. При этом элементы последовательности могут повторяться. В частности, последовательность не является подмножеством заданного множества.}}

== Определения Виды последовательностей =={{Определение|definition = Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''неубывающей''''' (англ. ''nondecreasing''), если каждый элемент этой последовательности не превосходит следующего за ним. <tex>\{x_n\}</tex> &mdash; '''''неубывающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n \leqslant x_{n+1}</tex>.}}

{{Определение|definition = Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''неубывающейневозрастающей'''''(англ. ''nonincreasing''), если каждый следующий элемент этой последовательности не превосходит следующего за нимпредыдущего.<tex>\{x_n\}</tex> &mdash; '''''невозрастающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n \geqslant x_{n+1}</tex>.}}

{{Определение|definition = Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''возрастающей''''' (англ. ''increasing''), если каждый следующий элемент этой последовательности превышает предыдущий. <tex>\{x_n\}</tex> &mdash; '''''неубывающаявозрастающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n \leqslant < x_{n+1}</tex>.}}

{{Определение|definition = Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''монотонной''невозрастающей'(англ. ''monotonic''), если каждый следующий элемент этой последовательности не превосходит предыдущегоона является неубывающей, либо невозрастающей.}}

<tex>\{x_n\}</tex> &mdash; '''''невозрастающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n \geqslant x_{n+1}</tex>  Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''возрастающей''''', если каждый следующий элемент этой последовательности превышает предыдущий. <tex>\{x_n\}</tex> &mdash; '''''возрастающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n < x_{n+1}</tex>  Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''убывающей''''', если каждый элемент этой последовательности превышает следующий за ним. <tex>\{x_n\}</tex> &mdash; '''''убывающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n > x_{n+1}</tex>Определение|definition = Последовательность называется '''строго монотонной''', если она является неубывающей, либо невозрастающей(англ. Последовательность называется '''строго монотонной'strictly monotonic''), если она является возрастающей, либо убывающей.}}

Произведение длин Пусть <tex>a</tex> {{---}} перестановка чисел длины <tex>n, l</tex> {{---}} длина наибольшей возрастающей и подпоследовательности ([[Задача о наибольшей возрастающей подпоследовательности|НВП]]), <tex>k</tex> {{---}} длина наибольшей убывающей подпоследовательностей больше либо равно длине последовательностиподпоследовательности (НУП). Тогда <tex>l k \geqslant n</tex>.

Пусть есть стока Рассмотрим два массива длины <tex> a n : S </tex> длины и <tex> n T </tex>. Рассмотрим наибольшую возрастающую подпоследовательность , где <tex> a[i_1] S_i < a[i_2] /tex> {{---}} длина НВП, которая заканчивается на < \dots < a[i_k] tex>a_i</tex> и наибольшую убывающую подпоследовательность , <tex> x[j_1] > x[j_2] > \dots > x[j_l] T_i </tex> строки {{---}} длина НУП, которая начинается на <tex> a a_i</tex>.

== Следствие из теоремы == {{Утверждение|statement=Пусть <tex>n</tex> {{---}} длина последовательности, тогда длина наибольшей монотонной подпоследовательности не меньше <tex>\sqrt{n}</tex>.}} ==См. также==* [[Задача о минимуме/максимуме скалярного произведения]]* [[Теорема Кэли]]* [[Матричное представление перестановок]] == Источники информации ==* [http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D1%8C#.D0.9D.D0.B5.D0.BA.D0.BE.D1.82.D0.BE.D1.80.D1.8B.D0.B5_.D0.B2.D0.B8.D0.B4.D1.8B_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B5.D0.B9 Википедия {{---}} Последовательность] *[http://en.wikipedia.org/wiki/Longest_increasing_subsequence Wikipedia Последовательность{{---}} Longest increasing subsequence]

*[http[Категория: Дискретная математика и алгоритмы]][[Категория: Комбинаторика]][[Категория://en.wikipedia.org/wiki/Longest_increasing_subsequence Longest increasing subsequence - Wikipedia, the free encyclopediaСвойства комбинаторных объектов]]