Очевидно, что множество, содержащее более одного элемента, можно упорядочить не единственным способом.
Например, из двух букв и можно построить упорядоченное множество двумя различными способами:
и .
Три буквы , и можно расположить в виде последовательности шестью способами:
, , , , , .
Для четырех букв путем перебора получим уже 24 различных упорядоченных последовательностей.
Упорядоченные последовательности элементов некоторого множества можно рассматривать как распределения или расстановки этих элементов в последовательности.
Определение 3: Пусть дано конечное множество из элементов. Всякий набор из элементов данного множества (при этом элементы в наборе могут и повторяться) будем называть - расстановками.
Через понятие расстановки вводятся основные определения комбинаторики: сочетания, размещения и перестановки. При этом каждое из этих понятий может быть с повторениями и без повторений. В данном параграфе будут рассмотрены комбинаторные формулы без повторений.
Перестановки без повторений.
Определение 4: Пусть - конечное множество из элементов. Перестановками из различных элементов множества называются все расположения элементов в определенном порядке. Обозначается: (от французского слова permutation - перестановка).
Упорядоченные множества считаются различными, если они отличаются либо своими элементами, либо их порядком.
Определение 5: Различные упорядоченные множества, которые отличаются лишь порядком элементов, называются перестановками этого множества.
Последнее определение сформулировано с позиции теории множеств.
Определение 6: Произведение последовательных натуральных чисел в математике обозначают и называют факториалом.
Выбор для обозначения восклицательного знака, возможно, связан с тем, что даже для сравнительно небольших значений число очень велико. Например, , , , , , , и т.д.
Теорема 1: Число перестановок из различных элементов вычисляется по формуле:
(1)
Доказательство. Рассмотрим произвольное множество из элементов. Построим всевозможные расстановки из этих элементов. На первое место расстановки можно поставить любой из элементов (способов выбора первого элемента). После того, как первый элемент выбран и независимо как он выбран, второй элемент можно выбрать способом. Для выбора третьего элемента остается способа и т.д. Последний элемент выбирается соответственно одним способом. Тогда, в силу комбинаторного принципа умножения, количество таких расстановок будет равно:
Теорема доказана.
Пример 1: Сколькими способами трое друзей могут занять в кинотеатре места с номерами 1, 2 и 3.
Решение. Количество искомых способов будет равно числу перестановок без повторений из трех элементов: способов. При необходимости эти способы можно перебрать.
Перестановки букв некоторого слова называют анаграммами. Открытые еще в ІІІ веке до нашей эры греческим грамматиком Ликофроном анаграммы до сих пор привлекают внимание языковедов, поэтов и любителей словесности. Мастера словесных игр помимо эрудиции и большого запаса слов знают много секретов, связанных с комбинаторными навыками, один из которых – анаграммы. Часто требуется среди всех перестановок выбрать те, которые обладают определенным свойством. Например, среди анаграмм слова «крот», которых всего , только одна, не считая самого слова «крот», имеет смысл в русском языке – «корт».
Кроме линейных перестановок, можно рассматривать перестановки круговые (или циклические). В этом случае перестановки, переходящие друг в друга при вращении, считаются одинаковыми и не должны засчитываться.
Теорема 2: Число круговых перестановок из различных элементов равно
Пример 2: Сколькими способами 7 детей могут стать в хоровод?
Решение. Число линейных перестановок 7 детей будет равно . Если хоровод уже сформирован, тогда для него существует 7 круговых перестановок, переходящих друг в друга при повороте. Эти перестановки не должны быть засчитаны, поэтому круговых перестановок из 7 элементов будет .
Размещения без повторений.
Определение 7: Пусть имеется различных предметов. Расстановки из элементов по элементов () называются размещениями без повторений. Обозначают: . Здесь имеется в виду, что элементы в расстановках не повторяются.
В данном определении существенной является следующая позиция: две расстановки различны, если они отличаются хотя бы одним элементом или порядком элементов.
Приведем еще одно определение размещений, эквивалентное исходному, более простое для понимания.