7. Сравнение последовательности чисел с помощью другой последовательности. Символы о, О, ~. Асимптотические решения некоторых рекуррентных соотношений.
8. Бином Ньютона.
9. Биномиальные коэффициенты. Их простейшие свойства.
10. Полиномиальная формула.
11. Правило произведения в комбинаторике.
12. Понятия k-размещений (с повторениями, без повторений) из n-множества. Формулы для вычислений.
13. Понятие перестановки элементов n-множества. Перестановки с повторениями элементов. Формулы для вычислений.
14. Понятие k-сочетания элементов n-множества. Сочетания с повторениями элементов. Формулы для вычислений.
15. Треугольник Паскаля. Основные его свойства.
16. Использование многочленов для доказательства комбинаторных тождеств.
17. Метод включения-исключения.
18. Основные понятия теории графов. Степень вершины графа. Теорема о сумме степеней вершин графа и ее следствие.
19. Связные графы. Компоненты связности графа.
20. Эйлеровы и полуэйлеровы графы. Критерий эйлеровости (полуэйлеровости).
21. Гамильтоновы и полугамильтоновы графы. Достаточные условия гамильтоновости.
23. Плоские графы. Формула Эйлера для плоских связных графов. Некоторые следствия.
24. Деревья. Лес. Теорема о числе ребер леса с n вершинами.
25. Раскраска вершин графа. Хроматическое число графа. Теорема о пяти красках.
Методические указания для студентов:
Материалы практических занятий (образцы решений, задания для аудиторной и домашней работы) в подробном виде представлены на стр. 43-73, 76-78 в учебном пособии:
Попов В.А. Задачник-практикум по математической логике и дискретной математике. – Сыктывкар: Коми пединститут, 2003. – 90 с.
На учебном сервере КГПИ выложен для свободного использования pdf-файл этого пособия.
4. Линейные рекуррентные последовательности вида .
5. Числа Фибоначчи. Формула Бине.
6. Целочисленные функции лxы , йxщ и их свойства.
7. Сравнение последовательности чисел с помощью другой последовательности. Символы о, О, ~. Асимптотические решения некоторых рекуррентных соотношений.
8. Бином Ньютона.
9. Биномиальные коэффициенты. Их простейшие свойства.
10. Полиномиальная формула.
11. Правило произведения в комбинаторике.
12. Понятия k-размещений (с повторениями, без повторений) из n-множества. Формулы для вычислений.
13. Понятие перестановки элементов n-множества. Перестановки с повторениями элементов. Формулы для вычислений.
14. Понятие k-сочетания элементов n-множества. Сочетания с повторениями элементов. Формулы для вычислений.
15. Треугольник Паскаля. Основные его свойства.
16. Использование многочленов для доказательства комбинаторных тождеств.
17. Метод включения-исключения.
18. Основные понятия теории графов. Степень вершины графа. Теорема о сумме степеней вершин графа и ее следствие.
19. Связные графы. Компоненты связности графа.
20. Эйлеровы и полуэйлеровы графы. Критерий эйлеровости (полуэйлеровости).
21. Гамильтоновы и полугамильтоновы графы. Достаточные условия гамильтоновости.
, s = 1, 2, 3, ... .
.
.