Правила комбинаторики.

Начнем с основных принципов комбинаторики, т.е. с правил.

Существует два общих правила комбинаторики: правило сложения и правило умножения.

Правило сложения.

Если множество содержит различных элементов, а множество - разных элементов и , тогда множество содержит элементов.

Доказательство. Пересчитаем элементы объединения непересекающихся множеств и , т.е. . Элементы множества получат номера от 1 до . Множества и не содержат одинаковых элементов, поэтому элементы множества получат номера от до . С помощью этой процедуры подсчета элементов множества все они будут исчерпаны, следовательно, множество содержит элементов.

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

Замечание: Правило сложения можно индуктивно обобщить на случай слагаемых.

Пример 1. Сколькими способами студенту филфака можно выбрать одну книгу, если на полке находятся 15 книг по философии, 10 книг по информатике и 5 книг по математике.

Решение. Книгу по философии можно выбрать 15 способами, книгу по информатике – 10 способами, а книгу по математике – 5 способами. Студент должен выбрать только одну книгу. Он может выбрать или книгу по философии, или по информатике, или по математике. Поэтому, согласно принципу сложения, он может ее взять числом способов, равным способов.

Правило умножения.

Если множество содержит различных элементов, т.е. , а множество - разных элементов, т.е. , то тогда множество , составленное из всевозможных пар, т.е. , содержит элементов.

Доказательство. Покажем, что множество можно разбить на непересекающиеся подмножества вида:

,

,

. . . . . . . . . . . . . . . . . . . .

,

. . . . . . . . . . . . . . . . . . . .

.

Заметим, что , поскольку подмножество состоит из пар, содержащих , а подмножество - только из пар, содержащих . Аналогично можно показать, что при .

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

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

Замечание: Правило умножения, как и правило сложения, можно индуктивно обобщить на случай сомножителей.

Можно также отметить, что знак умножения в соответствующем правиле соответствует союзу «и» русского языка. А знак сложения – союзу «или». Причём, союз «или» применяется во взаимоисключающем смысле.

Пример 2. Сколькими способами можно выбрать гласную и согласную буквы из слова процент.

Решение. Гласную букву можно выбрать двумя способами (о или е), а согласную – пятью способами (п, р, ц, н или т). Следовательно, согласно комбинаторному принципу умножения, пару букв (гласную и согласную) можно выбрать способами.

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

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

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