Элементы комбинаторики

Комбинаторика - это раздел математики, изучающий задачи о расположении или выборе элементов из множеств.

Группы, составленные из каких - либо предметов (любой, но одинаковой природы: буквы, числа, геометрические фигуры, детали и т. д.) называются соединениями (множествами). Сами предметы, их которых составляются соединения, называются элементами.

Различают три основных типа соединений: размещения, перестановки и сочетания.

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

.

Такие размещения называются размещениями без повторений.

ПРИМЕР. В группе 25 студентов. Выбирают старосту, физорга и профорга. Каково число всех возможных вариантов выбора «треугольника» группы?

Решение. Получаемые комбинации (т.е. соединения) из 25 - и элементов по 3 в каждом являются размещениями, так как в них важен не только состав элементов «треугольника», но и расположение внутри него. Следовательно

.

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

.

ПРИМЕР 1. Известно, что 4 студента сдали экзамен. Сколько возможно различных исходов экзамена (распределений оценок)?

Решение. Число элементов =3 («3», «4», «5»); . Последовательность, т. е. порядок элементов, существенна, повторения неизбежны. Следовательно .

ПРИМЕР 2. Сколькими способами 10 пассажиров могут распределиться по 13 вагонам, если для каждого существенным является только № вагона, а не занимаемое место в нем?

Решение. Пусть - номер вагона, выбранного первым пассажиром, - номер вагона, выбранного вторым пассажиром,..., - номер вагона, выбранного десятым пассажиром. Соединение (комбинация) полностью характеризует распределение пассажиров по вагонам. Здесь каждое из чисел может принимать любое целое значение от 1 до 13. Значит, различных распределений по вагонам будет столько, сколько подобных соединений (длиной 10) можно составить из элементов множества . Следовательно .

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

.

Так как число перестановок из элементов - это то же самое, что и число размещений из элементов по в каждом, то можем записать:

.

ПРИМЕР. Для проведения испытаний выбрано 5 различных моделей автомобилей. Сколькими способами они могут быть распределены между пятью испытателями?

Решение. Число способов, которыми можно распределить 5 автомобилей, равно числу комбинаций из 5 элементов по пять. Причем, сами комбинации отличаются друг от друга только порядком элементов, т.е. применимы перестановки. Следовательно .

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

.

Если из элементов имеется две различные группы, состоящие соответственно из одинаковых элементов:

,

тогда

.

ПРИМЕР. Каким числом способов можно распределить 9 цитрусовых между 9 студентами, если имеются 4 мандарина, 3 апельсина и 2 лимона?

Решение. Пусть - мандарины, - апельсины и - лимоны. Тогда

.

Следовательно .

Сочетаниями из различных элементов по () в каждом называются такие соединения, из которых каждое содержит элементов, взятых из числа данных элементов, и которые отличаются друг от друга, по крайней мере, одним элементом. Число сочетаний из различных элементов по в каждом обозначают символом и вычисляют по формуле:

Уверены, вы отлично понимаете, что это определение является определением числа сочетаний без повторений.

Число сочетаний обладает следующими свойствами:

1. .

Этим свойством удобно пользоваться в случаях, когда . Например: .

2. .

3. (см. первое свойство).

4. .

ПРИМЕР. На строительство общежития из 25 студентов требуется выбрать 3 человек. Каково число всех возможных вариантов выбора этой тройки?

Решение. Число возможных вариантов равно числу комбинаций (соединений) из 25 элементов по 3 в каждом. Причем комбинации отличаются друг от друга только составляющими их элементами, а порядок их расположения не имеет значения. Следовательно .

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

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

Число сочетаний с повторениями вычисляется по формуле:

ПРИМЕР. Каким числом способов можно составить расписание занятий из 3-х пар на один день, если изучается 10 предметов, которые могут повторяться в расписании. Расписания считаются различными, если отличаются друг от друга, хотя бы одним предметом (т.е. порядок предметов в расписании роли не играет)?

Решение. .

Замечания.

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

Например. Сколькими способами можно выбрать четырехзначное число, все цифры которого различны?

2. При большом пользуются приближенной формулой Стирлинга .