Лекция № 14. Комбинаторика.

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

1. Правила суммы и произведения.

Будем в дальнейшем оперировать только с множествами, содержащими конечное число элементов. На бесконечные множества все нижеприведённые правила и формулы не распространяются.

Теорема 13.1. Пусть даны непересекающиеся конечные множества . Тогда мощность объединения этих множеств равна сумме мощностей данных множеств:

.

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

Если некоторый элемент можно выбрать способами, а элемент - способами, причём любой способ выбора элемента отличается от любого способа выбора элемента , то выбор “или ” можно сделать способами. Это правило называется правилом суммы.

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

Теорема 13.2. Число элементов в декартовом произведении множеств равно произведению мощностей этих множеств:

.

Как и в предыдущем случае, сформулируем данную теорему упрощённым образом для двух множеств. Если элемент можно выбрать способами, а элемент - способами, причём любой способ выбора элемента отличается от любого способа выбора элемента , то выбор “и ” (то есть, пары ) можно сделать способами. Это правило называется правилом произведения, или умножения.

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