Тема 3.2. Основные принципы комбинаторики

Теорема (принцип умножения)

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

Замечание: В теореме считается, что даже если все элементы в -й группе неразличимы, выбрать один из них можно способами.

Замечание: Результат выбора, описанного в теореме, представим в виде набора в котором – выбранный из - й группы элемент. Тогда общее число различных наборов также равняется .

Доказательство:

Занумеруем элементы - ой группы числами от 1 до . Элемент из первой группы можно выбрать способами. Если мы выбрали элемент , , то выбрать элемент из второй группы мы можем способами. Получаем, что с первым элементом возможно составить пар , где .

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

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

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

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

Рассмотрим некоторые примеры применения принципа умножения.

Пример 3.3: Даны два конечных множества и с числом элементов и соответственно. Требуется определить число элементов декартова произведения этих множеств, т.е. .

Решение:

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

Следствие – обобщение: Аналогично, или используя метод математической индукции, можно доказать, что если даны конечные множества с то .

В частности, если – конечное множество с , то .

Пример 3.4: Пусть дано множество и множество и пусть на множестве с областью значений задана функция . Спрашивается: сколько всего имеется различных функций указанного вида?

Решение: Каждую функцию можно задать следующей таблицей:

		…		…

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

Теорема (принцип сложения)

Если некоторое действие №1 можно осуществить способами, а действие №2 – способами, то осуществить «либо действие №1, либо действие №2» можно способами.

Справедливость теоремы очевидна. Например, если студенту необходимо попасть в лекционный корпус, к которому можно подъехать либо на одном из трёх автобусных маршрутов, либо на одном из четырёх трамвайных, то студент обязательно окажется около корпуса, воспользовавшись одним из семи маршрутов городского транспорта.

Пример 3.5: Сколькими способами из 28 костей домино можно выбрать две кости одну за другой так, чтобы вторую можно было приложить к первой?

Решение:

Если первой костью является дубль , то вторую можно приложить к первой способами. Если первая кость не дубль , то вторую можно приложить к первой способами. Теперь, последовательно применяя принцип умножения и принцип сложения, для искомого числа получаем

Теорема: Если и конечные подмножества некоторого универсального множества , то

Доказательство: Применим метод полной индукции. Рассмотрим последовательно все пять различных случаев «взаимного расположения» двух множеств и .

1. , тогда

формула даёт – т.е. верное равенство;

2. , тогда

формула даёт – т.е. верное равенство;

3. аналогично случаю 2;

4. , тогда и формула даёт верное равенство .

5. , тогда в силу того, что общие элементы будут посчитаны дважды .

Установим общую формулу для определения числа элементов объединения конечного числа конечных множеств.

Теорема. Если конечные подмножества универсального множества , то

или

где есть сумма чисел по всем возможным пересечениям ровно различных множеств из множеств .

Доказательство:

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

Пусть формула верна для всех тогда последовательно получаем

Для того чтобы отсюда получить искомую формулу, остаётся принять во внимание, что

Следовательно, согласно принципу математической индукции, формула верна для любого натурального .

Следствие. Если , то

Пример 3.6: Каждый студент в группе - либо девушка, либо блондин, либо говорит по-английски. В группе 16 девушек, из них 6 блондинок, и 4 блондинки знают английский язык. Всего в группе 11 блондинов, по-английски из них говорят 8. Всего студентов, которые могут общаться на английском языке 20, из них 12 девушек. Сколько студентов в данной группе?

Решение:

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

– множество блондинок;

– множество девушек, которые говорят по-английски;

– множество всех блондинов (юношей и девушек), которые знают английский язык;

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

Теперь по формуле при получаем

.

Таким образом, в группе 25 студентов.

Дата добавления: 2015-10-28