Имея дело с большим количеством чисел, фигур, событий или просто предметов, часто приходится составлять из них различные комбинации. Эти комбинации трудно упорядочивать или пересчитывать непосредственно — их очень много. Нужно научиться устраивать систематический перебор, чтобы не запутаться, не забыть что-то важное или не посчитать одно и то же дважды.
Методы перечисления и упорядочивания множеств, составленных из чисел, фигур или предметов, изучаются в специальном разделе математики, который называется комбинаторика. Типичной задачей комбинаторики является перечисление комбинаций, составленных из нескольких предметов. В теории вероятностей комбинаторика применяется тогда, когда случайный опыт обширный и количество событий в нем настолько велико, что их невозможно выписать или даже просто перечислить без применения специальных методов.
Комбинаторное правило умножения. Чтобы найти число различных упорядоченных пар, составленных из предметов двух типов, нужно число предметов первого типа умножить на число предметов второго типа. Если число предметов первого типа равно m, а число предметов второго типа равно n, то число всевозможных их комбинаций равно mn. |
Комбинаторное правило умножения для нескольких типов предметов. Чтобы найти число различных упорядоченных комбинаций из предметов нескольких типов, нужно перемножить количества предметов каждого типа. |
Понятие «предмет» тут условное. В качестве предмета может выступать элемент некоторого множества.
Определение. Перестановкой n элементов называют упорядоченную последовательность чисел, в которой каждое натуральное число от 1 до n встречается ровно один раз. |
Найдем количество перестановок трех элементов. На первое место мы можем записать любое из трех чисел, на второе — одно из двух, а на последнее — оставшееся число. Пользуясь правилом комбинаторного умножения, получаем .
А если томов четыре? Рассуждения могут быть разные. Например, можно по аналогии с тремя томами воспользоваться правилом умножения и получить перестановки.
Можно рассуждать иначе: если томов четыре, то первый том мы можем выбрать четырьмя способами, а оставшиеся три тома можно поставить шестью способами: итого перестановки.
В каждом из пунктов ответ вычислялся как произведение всех чисел от 1 до n, где n — количество книг.
Такое произведение называется факториалом числа.
Определение. Факториалом натурального числа n называется произведение всех натуральных чисел от 1 до n. Обозначается факториал n!: |
Определение перестановки можно дать иначе, говоря не о самих последовательностях, а только о нумерациях.
Определение. Перестановкой порядка n называется способ нумерации элементов множества, в котором n элементов. |
Предыдущие рассуждения привели нас к способу подсчета числа перестановок. Этот способ можно сформулировать в виде теоремы.
Теорема. Число перестановок порядка n равно n! |