Дискретка
11. Числа Фибоначчи. Вывод формулы n-го числа Фибоначчи решением линейного
однородного рекуррентного соотношения 2-го порядка.
Линейным однородным рекуррентным соотношением второго порядка с постоянными коэффициентами называется рекуррентное соотношение вида:
(2)
- нейкие коэффициенты, причем отлично от нуля. Уравнение вида
- характеристическое уравнение рекуррентного соотношения (2).
Теорема 1: Если характеристическое уравнение рекуррентного соотношения (2) имеет два различных корня , то общее решение рекуррентного соотношения (2) имеет вид
Если рекуррентное соотношение имеет два равных корня , то общее решение рекуррентного соотношения (2) имеет следующий вид
последовательность чисел Фибоначчи задается линейным рекуррентным соотношением:
Содержание
- 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. Полнота системы булевых функций. Теорема Поста (без доказательства).