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

Основные законы комбинаторики.

Введение

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

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

Рассмотрим элементарный жизненный пример.

Пусть некоторое агентство недвижимости располагает базой данных из n записей, каждая запись содержит одно предложение (что имеется) и один запрос (что требуется). Требуется найти все такие пары записей, в которых предложение первой записи совпадает с запросом второй (осуществить подбор вариантов обмена). Допустим, что используемая СУБД позволяет проверить вариант за одну миллисекунду. При «лобовом» алгоритме поиска вариантов (каждая запись сравнивается с каждой) потребуется n(n-1)/2 сравнений. Если n=100, то ответ будет получен через 4,95 секунд; но если n=100000, то ответ будет получен за 4 999 950 секунд, что составляет почти 1389 часов и вряд ли это может считаться приемлемым. При этом мы оценили только трудоемкость прямых вариантов, но есть варианты, когда число участников сделки больше двух …

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

Задача: на блюде лежат 5 яблок и 2 груши. Сколькими способами можно выбрать один плод?

Решение: плод можно выбрать семью способами (5+2=7).

Если некоторый элемент a может быть выбран из множества элементов m способами, а другой элемент b может быть выбран n способами, причем любой выбор элемента b отличен от любого выбора элемента a, то выбрать либо a, либо b можно m + n способами.

На языке теории множеств это правило формулируется следующим образом:

Теорема1: если пересечение конечных множеств пусто, то число элементов в их объединении равно сумме чисел элементов множеств А и В.

АВ = | АВ | = |A| + |B|

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

Теорема2: для любых конечных множеств верно равенство:

| АВ | = |A| + |B| - | АВ |.

Задача: среди студентов первого курса 30 человек имеют дома компьютер, 35 – учебник по информатике; оказалось, что 10 студентов имеют и компьютер, и учебник по информатике. Сколько студентов на первом курсе?

Решение: пусть множество А составляют студенты, имеющие компьютер, множество В – студенты, имеющие учебник по информатике; по условию задачи:

|A| = 30 |B| = 35 | АВ | = 10 | АВ | =?

| АВ | = |A| + |B| - | АВ | = 30 + 35 – 10 = 55.