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

Глава I. Основные комбинаторные конфигурации и
комбинаторные числа
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. Задача об ожерельях
§ 1.12. Разбиения множеств
1.12.1. Разбиения и их виды
1.12.2. Упорядоченные разбиения
1.12.3. Неупорядоченные разбиения
§ 1.13. Разбиения чисел
1.13.1. Раскладки по различимым ящикам
1.13.2. Раскладки по неразличимым ящикам
1.13.3. Диаграммы Ферре-Юнга
§ 1.14. Примеры разбиения мультимножеств
§ 1.15. Конечные разности
1.15.1. Операторы конечной разности и сдвига
1.15.2. Факториальные степени
1.15.3. Полиномиальные последовательности
1.15.4. Суммирование конечных разностей
Глава II. Метод рекуррентных соотношений
§ 2.1. Примеры задач, приводящих к рекуррентным
соотношениям
2.1.1. Задание комбинаторных чисел
рекуррентными соотношениями
2.1.2. Числа Фибоначчи
2.1.3. Разбиения чисел с ограничениями
2.1.4. Сумма m-ых степеней натуральных чисел
2.1.5. Анализ алгоритмов типа "разделяй и
властвуй"
§ 2.2. Рекуррентное соотношение как уравнение
2.2.1. Понятие решения рекуррентного
соотношения
2.2.2. Решение линейных рекуррентных
соотношений
§ 2.3. Линейные однородные рекуррентные
соотношения с постоянными коэффициентами V
2.3.1. Основные теоремы. Линейные неоднородные
рекуррентные соотношения с постоянными
коэффициентами
2.4.1. Основные теоремы и примеры
2 4.2. Рекуррентные соотношения и вычисление
конечных сумм
Глава III. Производящие функции
§ 3.1. Алгебра формальных степенных рядов
3.1.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.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
Литература
Предметный указатель