Формула включений-исключений

Теорема Эрдеша.

Результат, доказанный Полом Эрдёшем и Дьёрдем (Джорджем) Секерешем таков: для данных r, s они показали, что любая последовательность длины по крайней мере (r -1)(s -1)+1 содержит или монотонно возрастающую подпоследовательность длины r, или монотонно убывающую длины s. Для r =3 и s =2, формула говорит, что любая переста новка трёх чисел имеет возрастающую подпоследовательность длиной три или убывающую подпоследовательность длиной два. Пример: Из шести перестановок чисел 1,2,3:

-1,2,3 имеет возрастающую подпоследовательность длиной три

-1,3,2 имеет убывающую подпоследовательность 3,2

-2,1,3 имеет убывающую подпоследовательность 2,1

-2,3,1 имеет две убывающие подпоследовательности, 2,1 и 3,1

-3,1,2 имеет две убывающие подпоследовательности, 3,1 and 3,2

-3,2,1 имеет три убывающие подпоследовательности длины 2, 3,2, 3,1, и 2,1.

Теорема Эрдёша-Секереша может быть доказана несколькими разными способами; Майкл Стил дает обзор шести разных доказательств теоремы, в том числе с использованием принципа Дирихле и теоремы Дилворта.^[2] Прочие способы доказательства, приводимые Стилом, включают оригинальное доказательство Эрдёша и Секереша и доказательство Блэквелла, Ловаса и самого Стила

Формула включений-исключений

Формула включений-исключений (или принцип включений-исключений) —комбинаторная формула, позволяющая определить мощность объединения конечного числа конечных множеств, которые в общем случае могут пересекаться друг с другом.

Например, в случае двух множеств формула включений-исключений имеет вид:

В сумме элементы пересечения учтены дважды, и чтобы компенсировать это мы вычитаем из правой части формулы.

Таким же образом и в случае множеств процесс нахождения количества элементов объединения состоит во включении всего, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении. Отсюда и происходит название формулы.

Впервые формулу включений-исключений опубликовал португальский математик Даниэль да Сильва в 1854 году. Но еще в 1713 году Николай Бернулли использовал этот метод для решения задачи Монмора, известной как задача о встречах, частным случаем которой является задача о беспорядках. Также формулу включений-исключений связывают с именами французского математика Абрахама де Муавра и английского математика Джозефа Сильвестра. В теории вероятностей аналог принципа включений-исключений известен как формула Пуанкаре.

5. Теорема о биекциях.

Биекция — это отображение, которое является одновременно и сюръективным и инъективным. При биективном отображении каждому элементу одного множества соответствует ровно один элемент другого множества, при этом, определено обратное отображение, которое обладает тем же свойством. Поэтому биективное отображение называют ещё взаимно-однозначным отображением (соответствием), одно-однозначным отображением. Если между двумя множествами можно установить взаимно-однозначное соответствие (биекция), то такие множества называются равномощными. С точки зрения теории множеств, равномощные множества неразличимы. Взаимно-однозначное отображение конечного множества в себя называется перестановкой (элементов этого множества). Функция называется биекцией (и обозначается ), если она:

Переводит разные элементы множества X в разные элементы множества Y (инъективность). Иными словами,

.

Любой элемент из Y имеет свой прообраз (сюръективность). Иными словами,

.