Элементы комбинаторного анализа (стр. 4 из 4)
Мощность булеана множества 
равна 
. Докажем это. Пусть
. Возьмем произвольное множество 
и сопоставим ему взаимнооднозначным образом двоичный набор 
: 
Отсюда получаем, что мощность булеана совпадает с мощностью множества, образованного всеми двоичными наборами, т.е. с мощностью единичного 
-мерного куба. Таким образом,
. 7. Покрытие множества . Семейство подмножеств
множества называют покрытием , если 
.8. Разбиение множества . Покрытие, образованное семейством
непустых, попарно непересекающихся подмножеств множества , называют разбиением . Множества называют блоками разбиения.Пример 7. Пусть
. Тогда семейство подмножеств 
является как разбиением, так и покрытием. В то время как семейство 
является покрытием, но не является разбиением.Явные формулы для числа покрытий и разбиений множества получаются довольно трудоемко. За неимением времени в нашем курсе эти задачи не рассматриваются.
1.3. Производящие функции
Для решения комбинаторных задач в некоторых случаях можно использовать методы математического анализа. В качестве примера рассмотрим основную идею метода производящих функций.
Пусть имеется последовательность чисел
и последовательность функций 
. Этим последовательностям сопоставим формальный ряд 
(для конечных последовательностей этот ряд превращается в многочлен). В ряде случаев, например, при определенных ограничениях, данный ряд может оказаться сходящимся и задавать некоторую функцию 
: 
. Эта функция называется производящей для последовательности 
относительно последовательности функций .В качестве
обычно используют 
и 
.В качестве примера применения производящих функций установим с их использованием следующее комбинаторное тождество:
.Прежде всего, заметим, что из формулы бинома Ньютона
следует, что функция 
является производящей для биномиальных коэффициентов. Возьмем тождество 
и разложим функции 
и в левой и правых частях этого тождества по формуле бинома Ньютона: 
.Сравнивая коэффициенты при
в левой и правой частях последнего тождества, получаем 
.