Введение в перечислительную комбинаторику. Учебное пособие

Предисловие
Глава 1. Основные комбинаторные конфигурации и
комбинаторные числа
§ 1.1. Вводные понятия
1.1.1. Комбинаторные конфигурации
1.1.2. Комбинаторные числа и способы их
вычисления
1.1.3. Комбинаторные схемы
§ 1.2. Основные правила комбинаторики
1.2.1. Правило суммы
1.2.2. Правило включения-исключения
1.2.3. Правило произведения
§ 1.3. Вычисление конечных сумм
1.3.1. Преобразования конечных сумм
1.3.2. Кратные суммы, произведения сумм
1.3.3. Методы вычисления конечных сумм
§ 1.4. Размещения и перестановки
1.4.1. Размещения
1.4.2. Перестановки
§ 1.5. Сочетания
1.5.1. Сочетания
1.5.2. Сочетания с повторениями
§ 1.6. Бином Ньютона
1.6.1. Вывод формулы
1.6.2. Свойства биномиальных коэффициентов
1.6.3. Треугольник Паскаля и его обобщения
1.6.4. Частный случай формулы
включения-исключения
§ 1.7. Полиномиальная формула
1.7.1. Вывод полиномиальной формулы
1.7.2. Свойства полиномиальных коэффициентов
§ 1.8. Формулы обращения
1.8.1. Теорема обращения
1.8.2. Биномиальное обращение
§ 1.9. Специальные целочисленные функции
1.9.1. Целочисленные округления
1 9.2. Число и сумма натуральных делителей.
Функция Эйлера
1.9.3. Функция Мебиуса
§ 1.10. Отображения и подстановки конечных
множеств
1.10.1. Число отображений конечных множеств
1.10.2. Перечисление подстановок
1.10.3. Задача о беспорядках
§ 1.11. Групповые методы в комбинаторике
1.11.1. Действие группы на множестве
1.11.2. Лемма Бернсайда
1.11.3. Задача об ожерельях I
§ 1.12. Разбиения множеств
1.12.1. Разбиенияиих виды
1.12.2. Упорядоченные разбиения
1.12.3. Неупорядоченные разбиения
§ 1.13. Разбиения чисел
1.13.1. Раскладки по различимым ящикам
1.13.2. Раскладки по неразличимым ящикам.
Диаграммы Ферре - Юнга
§ 1.14. Примеры разбиения мультимножеств
Глава 2. Метод рекуррентных соотношений
§ 2.1. Примеры задач, приводящих к рекуррентным
соотношениям
2.1.1. Задание комбинаторных чисел
рекуррентными соотношениями
2.1.2. Числа Фибоначчи
2.1.3. Сумма m-x степеней натуральных чисел
2.1.4. Анализ алгоритмов типа "разделяй и
властвуй"
§ 2.2. Рекурсия в задачах о разбиении чисел
2.2.1 Раскладка одинаковых предметов по
неразличимым ящикам
2.2.2 Разбиения чисел с ограничениями
§ 2.3. Числа Стирлинга
2.3.1 Числа Стирлинга первого рода
2.3.2 Числа Стирлинга второго рода. Числа Белла
§ 2.4. Рекуррентное соотношение как уравнение
2.4.1. Понятие решения рекуррентного
соотношения
2.4.2. Решение линейных рекуррентных
соотношений
§ 2.5. Линейные однородные рекуррентные
соотношения с постоянными коэффициентами
2.5.1. Основные теоремы
2.5.2. Характеристическое уравнение и вид общего
решения
§ 2.6. Линейные неоднородные рекуррентные
соотношения с постоянными коэффициентами
2.6.1. Основные теоремы и примеры
2.6.2. Рекуррентные соотношения и вычисление
конечных сумм
§ 2.7. Конечные разности
2.7.1. Операторы конечной разности и сдвига
2.7.2. Факториальные степени
2.7.3. Полиномиальные последовательности
2.7.4. Суммирование конечных разностей
Глава 3. Производящие функции
§ 3.1. Алгебра формальных степенных рядов
3.1.1. Идеи, приводящие к понятию производящей
функции
3.1.2. Алгебра Коши
3.1.3. Кольцо формальных степенных рядов
3.1.4. Подстановка ряда в ряд.
Дифференцирование и интегрирование
формальных степенных рядов
3.1.5. Алгебра Блиссара
§ 3.2. Производящие функции
3.2.1. Понятие производящей функции
3.2.2. Степенные производящие функции
3.2.3. Экспонента
3.2.4. Логарифм
§ 3.3. Приложения метода производящих функций
3.3.1. Доказательство биномиальных тождеств
3.3.2. Еще раз о биномиальном обращении
3.3.3. Решение рекуррентных соотношений
3.3.4. Числа Каталана
3.3.5. Числа Бернулли
§ 3.4. Производящие функции и выборки
3.4.1. Неупорядоченные выборки
3.4.2. Упорядоченные выборки
§ 3.5. Производящие функции и разбиения
множеств
§ 3.6. Производящие функции и разложения чисел
3.6.1. Разложения, в которых не учитывается
порядок слагаемых
3.6.2. Разложения, в которых учитывается
порядок слагаемых
§ 3.7. Теорема Пойа
3.7.1. Цикловой индекс группы
3.7.2. Производящая функция классов
эквивалентности
3.7.3. Задача об ожерельях II
Список использованной и рекомендуемой
литературы
Предметный указатель