Дискретка
17. Упорядоченные и неупорядоченные разбиения чисел. Рекуррентные соотношения для количества неупорядоченных разбиений натурального числа на фиксированное число слагаемых.
Разбие́ние числа́ n — это представление n в виде суммы положительных целых чисел, называемых частями. При этом порядок следования частей не учитывается (в отличие откомпозиций), то есть разбиения, отличающиеся только порядком частей, считаются равными. В канонической записи разбиения части перечисляются в невозрастающем порядке.
Количество разбиений числа n на слагаемые, используя числа не превышающие k:
Количество разбиений натурального числа n на k слагаемых:
---------------------------------------------------------------------------------------------------------------------------------------
Содержание
- 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. Полнота системы булевых функций. Теорема Поста (без доказательства).