Изменения

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

{{Определение|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 < x_{n+1}</tex>.}}

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

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

|proof=Рассмотрим два массива длины <tex>\n : S </tex> и <tex> T </tex>, где <tex> S_i </tex> {x_n\{---}} длина НВП, которая заканчивается на <tex>a_i</tex> &mdash; '''''возрастающая''''' , <tex>\Leftrightarrow\forall n \in \mathbb N: x_n T_i < x_/tex> {n+1{---}}длина НУП, которая начинается на <tex>a_i</tex>.

Последовательность Заметим что <tex>1 \{x_nleqslant S_i \}leqslant l, 1 \leqslant T_i \leqslant k</tex>, поэтому существуют <tex>l k</tex> различных пар <tex> (S_i, T_i) </tex>. Если <tex>l k < n</tex> тогда среди <tex> n </tex> элементов множества пар найдутся две одинаковые. Такого быть не может по доказанному выше, т. е. <tex>Xl k \geqslant 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[Категория://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 Wikipedia ПоследовательностьСвойства комбинаторных объектов]]