Правило суммы

МЕТОД ВКЛЮЧЕНИЙ И ИСКЛЮЧЕНИЙ

План лекции:

1. Краткий исторический очерк развития комбинаторики.

2. Правило суммы.

3. Правило произведения.

4. Правило биекции.

5. Метод включений и исключений.

Краткий исторический очерк развития комбинаторики

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

1) установление существования и подсчет числа подмножеств конечных множеств, обладающих заданными свойствами;

2) определение числа способов, которыми можно расположить элементы конечных множеств при заданных условиях на эти расположения и др.

Комбинаторика возникла в XVI веке в связи с проблемами азартных игр (игра в кости, карточные игры и лотереи). Одним из первых занялся подсчетом числа возможных комбинаций при игре в кости итальянский математик Тарталья. Первые теоретические исследования проблем комбинаторики были проведены в XVII веке французскими учеными Паскалем и Ферма. Дальнейшее развитие комбинаторики связано с именами Якова Бернулли, Лейбница и Эйлера. Тогда же сложилась и принятая в комбинаторике терминология (сочетания, размещения, перестановки и др.). К началу XX века комбинаторика считалась в основном завершенным разделом математики, лежащим вне основного русла развития математики и ее приложений. Но с середины XX века роль комбинаторики возросла в связи с развитием теории вычислительных систем и теории информации. В настоящее время комбинаторика является одним из наиболее интенсивно развивающихся разделов математики.

Правило суммы

Это правило позволяет найти число элементов в объединении двух конечных множеств и :

. (1)

Если множества и не пересекаются (), то

. (2)

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

если объект можно выбрать способами, а объект – способами, то выбор «либо , либо » можно осуществить способами.

Пример 1. Сколько имеется путей из вершины в вершину на решетке, показанной на рис. 1?

Рис.1. Решетка размером [4 5]

Обозначим множество всех путей из в через и разобьемего на два непересекающиеся подмножества: – множество путей, проходящих через вершину , – множество путей, проходящих через вершину . Тогда .

Очевидно, что искомое количество путей зависит только от размеров решетки. Обозначим через количество путей в решетке размером [ ], где , – соответственно количество горизонтальных и вертикальных путей. Тогда причем . Пользуясь этим соотношением для данного примера , , получим:

.