Элементы комбинаторного анализа

   В этом равнобедренном треугольнике каждое число (кроме единиц на боковых сторонах) является суммой двух чисел, стоящих над ним. Число находится в ( ) ряду на ( ) месте.

   Упражнение 3. Показать, что последовательность , где обладает свойством:

и

   4. Размещения с повторениями. Размещением с повторениями элементов из по (или размещением с повторением из n элементов по k) упорядоченная -выборка с повторениями.

   Пример 4. Пусть и . Выпишем все размещения с повторениями из этого множества по два:

   Для подсчета числа размещений с повторениями из n элементов по k используем правило произведения. При построении конкретного размещения первым элементом в нем можно взять любой из элементов множества , вторым элементом – также любой из элементов множества т.д. Таким образом, число размещений из n элементов по k равно

   В частности, если в качестве множества  взято множество , то совокупность всех размещений с повторениями из по называется единичным -мерным кубом и обозначают . .

   Пример 5. 3-х мерный куб размера 2 состоит из следующих элементов: (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1).

   5. Сочетания с повторениями. Сочетанием с повторениями элементов из по (или сочетанием с повторением из n элементов по k) неупорядоченная -выборка с повторениями.

   Пример 5. Пусть и . Выпишем все сочетания с повторениями из этого множества по два:

   Можно показать, что число сочетаний  с повторениями из n элементов по k  равно .

   6. Булеан множества . Множество всех подмножеств называется булеаном множества и обозначается как .

   Пример 6. Пусть . Тогда множество есть булеан множества .

   Мощность  булеана множества  равна . Докажем это. Пусть . Возьмем произвольное множество и сопоставим ему взаимнооднозначным образом двоичный набор :

   Отсюда  получаем, что мощность булеана совпадает  с мощностью множества, образованного всеми двоичными наборами, т.е. с мощностью единичного -мерного куба. Таким образом, .

    7. Покрытие множества . Семейство подмножеств множества называют покрытием , если .

   8. Разбиение множества . Покрытие, образованное семейством  непустых, попарно непересекающихся подмножеств множества , называют разбиением . Множества называют блоками разбиения.

   Пример 7. Пусть . Тогда семейство подмножеств является как разбиением, так и покрытием. В то время как семейство  является покрытием, но не является разбиением.

   Явные формулы для числа покрытий и разбиений  множества  получаются довольно трудоемко.  За неимением времени в нашем курсе эти задачи не рассматриваются.

1.3. Производящие функции

   Для решения комбинаторных задач  в некоторых случаях можно  использовать методы математического анализа. В качестве примера рассмотрим основную идею метода производящих функций.

   Пусть имеется последовательность чисел и последовательность функций  . Этим последовательностям сопоставим формальный ряд (для конечных последовательностей этот ряд превращается в многочлен). В ряде случаев, например, при определенных ограничениях, данный ряд может оказаться сходящимся и задавать некоторую функцию : . Эта функция называется производящей для последовательности  относительно последовательности функций .

   В качестве обычно используют и . 

   В качестве примера применения производящих функций установим с их использованием следующее комбинаторное тождество:

   Прежде  всего, заметим, что из формулы бинома Ньютона следует, что функция является производящей для биномиальных коэффициентов. Возьмем тождество и разложим функции и в левой и правых частях этого тождества по формуле бинома Ньютона:

   Сравнивая коэффициенты при  в левой и правой частях последнего тождества, получаем