Основы дискретной математики.

Алексей пастор.
1. элементарная комбинаторика.
Основные комбинаторные величины и простейшие комбинаторные формулы. Числа размещения и сочетания (с повторениями и без повторений. Бином ньютона и биномиальные коэффициенты. Простейшие соотношения на биномиальные коэффициенты. Треугольник паскаля. Обобщение бинома ньютона и мультиномиальные коэффициенты. Семейства подмножеств конечного множества.
2. принцип включений - исключений.
Формула включений - исключений (или принцип включений - исключений) - комбинаторная формула, позволяющая определить мощность объединения конечного числа конечных множеств, которые в общем случае могут пересекаться друг с другом. В теории вероятностей аналог принципа включений - исключений известен как формула пуанкаре.
3. частично упорядоченные множества.
Частично упорядоченное множество - математическое понятие, которое формализует интуитивные идеи упорядочения, расположения элементов в определённой последовательности. Неформально, множество частично упорядочено, если указано, какие элементы следуют за какими (какие элементы больше каких.

4. группа перестановок.
Четность перестановки, разложение в произведение транспозиций, разбиение на циклы, четность цикла, классы сопряженных и циклический тип перестановки.
5. разбиения числа в сумму слагаемых.
Задачи о разбиениях чисел на слагаемые. Упорядоченные и неупорядоченные разбиения. Диаграммы юнга. Рекуррентные соотношения для функций разбиения. Теоремы харди - рамануджана.
6. рекуррентные соотношения. Числа каталана и числа белла.
7. методы линейной алгебры в комбинаторике.
Использование линейной алгебры для доказательства комбинаторных результатов. Различные примеры использования этого метода (неравенство Фишера, (n, k) - плотные множества, множества с двумя расстояниями и т. д. ).