Rambler's Top100





4
ГЛАВА I
ТЕОРИЯ КОНЕЧНЫХ МНОЖЕСТВ
(КОМБИНАТОРИКА)
§1. Принципы сложения и умножения
Комбинаторика занимается подсчетом количеств разных комбина-
ций, которые можно получить различными способами из тех или иных
конечных множеств.
Классический пример задачи подобного сорта (задача о беспоряд-
ках): n джентльменов собрались на званный ужин. Уходя, они перепу-
тали свои шляпы и каждый одел не свою шляпу. Сколько всего таких
возможностей существует.
Более актуальный и содержательный пример: сейф закрывается че-
тырьмя разными замками. Доступ к сейфу имеет семь человек. Какое
минимальное количество и каких ключей должен иметь каждый, чтобы
сейф можно было открыть в присутствии не менее трех из этих семи.
Несмотря на кажущуюся простоту, довольно сложно решить эти
задачи без разработки соответствующего аппарата.
Сначала остановимся на понятии конечного множества. Любая по-
пытка дать «простое» определение конечного множества, которая смог-
ла бы реализовать наше интуитивное понимание конечного, обречена на
неудачу. Все они так или иначе будут сводиться к «определению» тако-
го типа: множество называется конечным, если оно состоит из конечно-
го числа элементов ("масло масляное") или множество называется ко-
нечным, если оно не является бесконечным что такое бесконечное
множество?). «Определение» такого типа относится к разделу «логиче-
ских кругов» - определять через определение.
Строгое определение конечного множества сделаем позже, когда
будем изучать бесконечные множества. А сейчас будем опираться на
наше очевидное интуитивного понимания конечного.
Если конечное множество A состоит из m элементов, то мы будем
писать: |A| = m или n(A) = m. Например, если A множество цифр,
то n(A) =10.
Все обилие сложных комбинаторных формул базируется на двух
очень простых принципах: принципе сложения и принципе умножения.
Теорема 1 (принцип сложения). Пусть A B = . Тогда
n(A B) = n(A) + n(B).
Следствие 2. Пусть A
1
, A
2
….A
l
система попарно непересекаю-
щихся конечных множеств.
Тогда n(A
1
A
2
A
l
) = n(A
1
)+n(A
2
)+…+n(A
l
).