Комбинаторика - это раздел математики, изучающий задачи о расположении или выборе элементов из множеств.
Группы, составленные из каких - либо предметов (любой, но одинаковой природы: буквы, числа, геометрические фигуры, детали и т. д.) называются соединениями (множествами). Сами предметы, их которых составляются соединения, называются элементами.
Различают три основных типа соединений: размещения, перестановки и сочетания.
Размещениями из различных элементов по () в каждом называются такие соединения, из которых каждое содержит элементов, взятых из числа данных элементов, и которые (соединения) отличаются друг от друга либо хотя бы одним элементом, либо порядком их расположения. Число размещений обозначается и вычисляется по формуле:
.
Такие размещения называются размещениями без повторений.
ПРИМЕР. В группе 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. При большом пользуются приближенной формулой Стирлинга .