Комбинаторика

Комбинаторика

Комбинаторика

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

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

Пусть мы имеем конечное множество Х={,,…,}, тогда набор элементов ,…,Называется Выборкой объема r из n элементов или, иначе, (n, r)-выборкой. Выборка называется Упорядоченной, если порядок следования элементов в ней фиксирован, и две выборки, различающиеся лишь порядком следования элементов, считаются различными.

Если X1,X2,…,Xn некоторые подмножества множества X, причем в общем случае , то справедлива формула (1.47), которая в комбинаторике называется Формулой включений и исключений:

Поставим такой вопрос: сколькими способами можно разложить множество A={a1,a2,…,an}на m подмножеств

,

Пусть задано конечное множество Х, такое, что . Тогда объект из Х может быть выбран n способами. Пусть множества Хi, где таковы, что и , если i¹j. Тогда выполняется равенство

Задачи и упражнения

1.  Сколько существует перестановок из n элементов, в которых между двумя данными элементами стоит r элементов?

2.  Сколькими способами можно разместить n гостей за круглым столом?

3.  Сколько различных слов можно составить, переставляя буквы слова «комбинаторика»?

4.  Сколько можно сделать костей домино, используя числа 0,1,...,r?

5.  Сколько целых положительных решений имеет уравнение x1+x2+...+xm=n?

6.  Доказать, что для биномиальных коэффициентов справедливо равенство

 Производящие функции. Рекуррентные соотношения

Пусть имеется некоторая последовательность чисел . Рассмотрим степенной ряд.

.

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