- •1. Предмет комбинаторики. Логические правила комбинаторики.
- •2. Число r-перестановок (с повторениями и без повторений) из n элементов. Число всех подмножеств n-элементного множества.
- •3. Число r-сочетаний из n элементов. Биномиальная теорема и следствия из нее. Основныe свойства биномиальных коэффициентов. Треугольник Паскаля.
- •4. Число ( r1, ...,rk ) -разбиений конечного множества. Другая комбинаторная интерпретация этого числа. Полиномиальная теорема.
- •5. Число r-сочетаний с повторениями из n элементов.
- •6. Метод включения и исключения (формула для числа элементов, не обладающих ни одним из заданных свойств).
- •9. Понятие рекуррентного соотношения. Рекуррентное соотношение k-го порядка для функции одной переменной, его общее решение.
- •10. Общее решение линейного однородного рекуррентного соотношения с постоянными коэффициентами.
- •11. Числа Фибоначчи. Вывод формулы n-го числа Фибоначчи решением линейного
- •12. Общее решение линейного неоднородного рекуррентного соотношения с постоянными коэффициентами.
- •13. Разбиение подстановки на циклы. Число подстановок n-элементного множества, имеющих предписанных циклический тип.
- •14. Число Стирлинга 1-го рода. Рекуррентное соотношение для числа Стирлинга 1-го рода.
- •15. Упорядоченные и неупорядоченные разбиения множеств. Число Стирлинга 2-го рода. Формула и рекуррентное соотношение для числа Стирлинга 2-го рода.
- •16. Число Белла. Рекуррентное соотношение для числа Белла.
- •17. Упорядоченные и неупорядоченные разбиения чисел. Рекуррентные соотношения для количества неупорядоченных разбиений натурального числа на фиксированное число слагаемых.
- •18. Система различных представителей. Теорема Холла (без доказательства).
- •19. Система общих представителей, критерий существования.
- •20. Теорема Рамсея.
- •26.Задача минимизации булевых функций в классе днф. Полная и приведенная системы импликант булевой функции. Связь между минимальной и тупиковой днф.
- •27. Алгоритм Квайна нахождения минимальной днф булевой функции.
- •28. Полиномиальная нормальная форма. Полином Жегалкина. Теорема о единственности представления булевой функции посредством полинома Жегалкина.
- •29. Замкнутые классы булевых функций.
- •30. Полнота системы булевых функций. Теорема Поста (без доказательства).
5. Число r-сочетаний с повторениями из n элементов.
Сочетания с повторениями — комбинаторные соединения из n элементов по m, составленные из этих элементов без учета порядка с возможностью многократного повторения предметов.
формула для нахождения количества сочетаний с повторениями:
---------------------------------------------------------------------------------------------------------------------------------------
6. Метод включения и исключения (формула для числа элементов, не обладающих ни одним из заданных свойств).
n(0) = n – + - … - + … +
---------------------------------------------------------------------------------------------------------------------------------------
7. Метод включения и исключения (формула для числа элементов, обладающих в точности t (t ≥ 1) свойствами из числа заданных свойств).
n(t) = - + … + +…+
---------------------------------------------------------------------------------------------------------------------------------------
8. Применение метода включения и исключения (задача о беспорядках, задача о числе сюръективных отображений).
Задача о беспорядках
Требуется найти число перестановок множества таких что для всех . Такие перестановки называются беспорядками.
Пусть — множество всех перестановок и пусть свойство перестановки выражается равенством . Тогда число беспорядков есть . Легко видеть, что — число перестановок, оставляющих на месте элементы , и таким образом сумма содержит одинаковых слагаемых. Формула включений-исключений дает выражение для числа беспорядков:
Это соотношение можно преобразовать к виду
Нетрудно видеть, что выражение в скобках является частичной суммой ряда . Таким образом, с хорошей точностью число беспорядков составляет долю от общего числа перестановок:
Число сюръективных отображений конечного
множества X; |X|= n, на конечное множество Y ; |Y | = m, то
есть число функций f : X Y , таких, что f (X) = Y ,
равно cогласно принципу включения-исключения:
f(n,m) = + ^n = + ^n
---------------------------------------------------------------------------------------------------------------------------------------
9. Понятие рекуррентного соотношения. Рекуррентное соотношение k-го порядка для функции одной переменной, его общее решение.
Рекуррентноe соотношениe- соотношение между элементами последовательности, в которой следующий элемент выражается через несколько предыдущий.
Рекурентная формула — формула вида , выражающая каждый член последовательности через p предыдущих членов. Например - числа Фибоначчи
Линейным рекуррентным соотношением k - го порядка(k - фиксировано) с постоянными коэффициентами называется рекуррентное соотношение следующего вида:
(3)
- постоянные .
Характеристическим уравнением рекуррентного соотношения (3) является уравнение вида
Теорема 2: Пусть - все попарно различные корни характеристического уравнения рекурретного соотношения (3) - кратность корня . Тогда общее решение рекуррентного соотношения (3) имеет следующий вид:
.
В частности, если , то
---------------------------------------------------------------------------------------------------------------------------------------