01. Тема 1. Элементы комбинаторики

Литература:[5, с.46-81], [8, c. 10-21], [7, c.32-37], [12, с. 5-32].

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

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

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

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

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

Определение 1. Множества , 1,2,…,M, называются различными Сочетаниями Из элементов по если каждое из них содержит ровно различных элементов множества , и все различаются между собой хотя бы одним элементом.

Число различных сочетаний из по Обозначают символом Или и

Рассмотрим пример составления различных сочетаний. Пусть множество - это группа из семи студентов. Мы пронумеруем студентов, тогда Различные неупорядоченные наборы по три студента будут являться примерами различных сочетаний из семи по три. Например, множества {1,2,3}, {1,2,4}, {1,7,8}, {3,5,6}, {4,6,7} есть различные сочетания из семи по три. Всего можно составить различных сочетаний из семи элементов по три. Если перед нами стоит задача вычисления числа различных способов, которыми можно выбрать трех студентов для дежурства по столовой, то ответом будет

Определение 2. Множества , 1,2,…,M, называют различными Размещениями Из элементов по если они упорядочены, содержат по различных элементов множества и различаются между собой либо хотя бы одним элементом, либо порядком следования элементов.

Число различных размещений из по обозначают символом и вычисляют по формуле

Примерами различных размещений из семи рассмотренных выше элементов по три могут служить следующие упорядоченные множества: (1,2,3), (2,1,3), (3,1,2), (1,5,7), (5,1,2) и т. д. Всего можно составить различных размещений из семи элементов по три. Число различных размещений из семи по три получилось в шесть раз больше, чем число различных сочетаний из семи элементов по три. Это связано с тем, что размещения учитывают порядок следования элементов, а сочетания нет. Три различных элемента можно упорядочить ровно шестью различными способами. Посчитаем сколько существует различных способов назначить трех студентов из семи на дежурство, если один должен дежурить в столовой, другой в библиотеке, а третий в университетском саду. Здесь можно использовать размещения из семи элементов по три, если условиться, что первый элемент размещения соответствует номеру студента, назначенному в столовую, второй элемент размещения – это номер студента, которому досталось дежурство в библиотеке, а третий элемент соответствует студенту, который пойдет работать в сад. Таким образом получим, что число различных таких назначений равно

Определение 3. Упорядоченные множества, 1,2,…,M, называют различными Перестановками из элементов, если каждое содержит все элементы множества , и различаются между собой порядком следования элементов.

Число различных перестановок из N элементов равно

В качестве примеров различных перестановок семи элементов можно рассмотреть следующие упорядоченные множества: (1,2,3,4,5,6,7), (3,1,2,4,5,6,7), (7,6,5,4,3,2,1), (4,5,6,1,2,3,7) и т. д. Всего можно придумать различных перестановок семи элементов. Используя эти стандартные комбинации можно посчитать, например, каким числом способов можно назначить семь студентов на дежурство в семь различных пунктов. Всего существует М=5040 различных таких назначений.

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

=, =,

Рассмотрим как применяется основное правило комбинаторики и стандартные комбинации при решении задач.

Следующая >