19
правок
Изменения
м
<tex>\{x_n\}</tex> — '''''неубывающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n \leqslant x_{n+1}</tex> Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''невозрастающей''''' (англ. ''nonincreasing''), если каждый следующий элемент этой последовательности не превосходит предыдущего. <tex>\{x_n\}</tex> — '''''невозрастающая''''' <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> — '''''возрастающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n < x_{n+1}</tex> Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''убывающей''''' (англ. ''decreasing''), если каждый элемент этой последовательности превышает следующий за ним. <tex>\{x_n\}</tex> — '''''убывающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n > x_{n+1}</tex>
Исправил замечания
}}
== Определения Виды последовательностей =={{Определение|definition = Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''неубывающей''''' (англ. ''nondecreasing''), если каждый элемент этой последовательности не превосходит следующего за ним. <tex>\{x_n\}</tex> — '''''неубывающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n \leqslant x_{n+1}</tex>.}}
{{Определение|definition = Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''неубывающейневозрастающей''''' (англ. ''nondecreasingnonincreasing''), если каждый следующий элемент этой последовательности не превосходит следующего за нимпредыдущего. <tex>\{x_n\}</tex> — '''''невозрастающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n \geqslant x_{n+1}</tex>.}}
{{Определение
|definition =
Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''убывающей''''' (англ. ''decreasing''), если каждый элемент этой последовательности превышает следующий за ним. <tex>\{x_n\}</tex> — '''''убывающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n > x_{n+1}</tex>.
}}
{{Определение
|definition =
Последовательность называется '''монотонной''' (англ. ''monotonic''), если она является неубывающей, либо невозрастающей.
}}
{{Определение
|definition =
Последовательность называется '''строго монотонной''' (англ. ''strictly monotonic''), если она является возрастающей, либо убывающей.
}}
Очевидно, что строго монотонная последовательность является монотонной.
|about=
|statement=
Пусть <tex>a</tex> {{---}} перестановка чисел длины <tex>n, l</tex> {{---}} длина наибольшей возрастающей подпоследовательности ([[Задача о наибольшей возрастающей подпоследовательности|НВП]]), <tex>k</tex> {{---}} длина наибольшей убывающей подпоследовательности (НУП). Тогда <tex>l k \geqslant n</tex>.
|proof=
{{Утверждение
|statement=
Пусть <tex>n</tex> {{---}} длина последовательности, тогда длина наибольшей монотонной подпоследовательности не меньше <tex>\sqrt{n}</tex>.
}}
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]][[Категория: Комбинаторика Свойства комбинаторных объектов]]
