- •Оглавление
- •Предисловие
- •1. Теоретико‑множественные основания дисциплины
- •1.1. Понятия и аксиомы теории множеств
- •1.2. Декартовы произведения, отношения и отношение эквивалентности
- •1.3. Понятия образа, прообраза, функции и отображения на конечном множестве. Аксиома выделения.
- •1.4. Аксиомы степени и бесконечности. Мощности и кардинальные числа множеств
- •1.5. Счетные и континуальные множества
- •1.6. Ординалы и трансфиниты. Аксиома выбора и континуум‑гипотеза
- •2. Основы математической логики
- •2.1. Высказывания и функции на высказываниях
- •2.2. Операции математической логики
- •2.3. Понятие формулы и свойства операций
- •2.4. Разложения булевых функций. Принцип двойственности. Совершенные нормальные формы.
- •2.5. Понятие полноты системы булевых функций
- •2.5. Исчисление предикатов
- •2.6. Введение в методы теории доказательств
- •1 Если X a,
- •0 Если X a.
- •1 Если X a,
- •0 Если X a.
- •3. Комбинаторика
- •3.1. Размещения
- •3.2. Размещения без повторений
- •3.3. Перестановки, подстановки и их свойства
- •3.4. Сочетания, структура соединений
- •3.5. Свойства биномиальных коэффициентов
- •Структура соединений
- •3.6. Понятие производящей функции
- •3.7. Соединения с повторениями
- •3.8. Разбиения множеств
- •3.9. Разбиения чисел
- •3.10. Композиции чисел
- •4. Основы теории графов
- •4.1. Основные понятия и определения
- •4.2. Графы и бинарные отношения
- •4.3. Понятие изоморфизма и изоморфизм плоских графов
- •4.4. Степени вершин графа
- •4.5. Представление графов матрицами
- •4.6. Представление графов списками инцидентности. Оценка пространственной сложности алгоритмов.
- •4.7. Маршруты, цепи, циклы и связность
- •4.7. Эйлеровы циклы и цепи
- •4.9. Гамильтоновы циклы. Оценка временной сложности алгоритмов
- •4.10. Деревья
- •4.11. Раскраска вершин и теорема Шеннона об информационной емкости графа
- •4.12. Раскраска ребер графа и теоремы о хроматическом классе
- •Ответы и решения
- •Список литературы
3.6. Понятие производящей функции
Из математического анализа хорошо известен ряд Маклорена:
φ(x) = ∑ k∞ = 0 akxk, (3.18)
где аk = φk(0) / k!.
В разложении (3.18) произвольной аналитической в окрестности нуля функции φ(x) ставится в биективное соответствие последовательность чисел аk.
В комбинаторном анализе часто приходится сталкиваться с задачами оперирования числовыми последовательностями, отвечающими различным комбинаторным конфигурациям. Например, может потребоваться вычисление суммы биномиальных коэффициентов с различными весами, как то:
∑ k∞ = 0 Cnk , ∑ k∞ = 0 kCnk,
а также вычисления произведений рядов, составленных из этих коэффициентов и другие.
В таком случае часто оказывается возможным упростить процесс получения результата, если сопоставить комбинаторной последовательности {ak} функцию, определяемую формальным рядом
f(x) = ∑ k∞ = 0 akxk (3.19)
Такая f(x) именуется производящей функцией.
Если в ряде (3.19) все ak, начиная с некоторого k равны нулю, то суммирование осуществляется в конечных пределах и построенная, таким образом, производящая функция носит название полиномиальной.
Для произвольных производящих функций
fа(x) = ∑ k∞ = 0 akxk и f b(x) = ∑ k∞ = 0 bkxk
определены операции сложения:
fа(x) + f b(x) = ∑ k∞ = 0(ak + bk) xk, (3.20)
умножения на число
λf(x) = ∑ k∞ = 0 λakxk (3.21)
и произведение Коши
fа(x) f b(x) = ∑ k∞ = 0 сkxk, (3.22)
где ck = ∑ ik = 0(aibk-i).
Поясним применение производящих функций на примере исследования свойств сочетаний.
Пусть x1, x2, …, xn — элементы n‑X множества. Составим произведение
f(x) = (1 + x1x)(1 + x2x)…(1 + xnx).
Раскрывая в этом произведении скобки, получим
f(x) = 1 + (x1 + x2 + …+ xn)x + (x1x2 + x1x3 +…+ xn-1xn)x2 +…
…+(x1x2…xn)xn. (3.23)
В этой формуле каждое слагаемое x1x2…xk (1 < k n) можно считать k‑сочетаниями из n элементов x1, x2, …, xn. Число таких сочетаний равно Cnk. Полагая в (3.23) значения x1 = x2 = … = xn = 1, получим
f(x) = ∑ kn = 0 Cnkxk = (1 + x)n . (3.24)
В данном случае производящей функцией последовательности Cnk есть функция (1 + x)n. Это частный случай бинома Ньютона, с которым мы встречались в 3.5.
Полагая x = 1, также как в (3.13) получим
∑ kn = 0 Cnk = 2n. (3.25)
Подставляя, например в формулу (3.24) x = -1, видим, что коэффициенты Cnk обладают следующим свойством
∑ kn = 0 ( -1)kCnk = 0. (3.26)
Это свойство вытекает из симметрии коэффициентов Cnk и Cnn-k, однако с помощью производящих функций оно доказывается проще, чем комбинаторными рассуждениями.
Докажем еще тождество
Cnk+m = ∑ sk = 0 CmsCnk-s. (3.27)
Для доказательства воспользуемся производящей функцией:
(1 + x)n+m = (1 + x)n(1 + x)m.
Перемножив соответствующие ряды по правилу произведения Коши, получим производящую функцию
∑ kn = 0 Cnkxk ∑ km = 0 Cmkxk = ∑km+ n = 0 ∑ sk = 0 CmsCnk-sxk,
для которой
Cnk+m = ∑ sk = 0 CmsCnk-s,
что в точности совпадает с (3.27).
Ниже приведено комбинаторное доказательство этого же факта, которое выглядит более громоздко.
Предположим, что в урне имеется n + m шаров: n — белых и m — красных. Выбор k шаров можно выполнить Cnk+m способами. При этом все k‑подмножества можно классифицировать по числу шаров одного цвета, например, красного. Любое k‑подмножество, содержащее s красных шаров можно получить, выбирая s красных шаров одним из Cms способов, а затем k-s белых шаров, одним из Cnk-s способов. Таким образом, число всех подмножеств, включающих s красных шаров равно Cms Cnk-s. Суммируя это произведение от 0 до k, получим тождество (3.27).
Эти примеры показывают, что производящие функции позволяют в ряде случаев упростить доказательства комбинаторных построений.