Комбинаторика: факториалы и перестановки

      Оглавление:

Факториалы

Перестановки

Размещения

Сочетания

Факториалы

      Для произвольного натурального числа   n   формула

определяет факториал числа   n   ( n !   читается, как   n   – факториал).

      Например,

      Считается, что

0 ! = 1 ,     1 ! = 1.

Перестановки

      Рассмотрим следующую задачу.

      Задача.   6   карточек пронумерованы числами   1, 2, 3, 4, 5, 6.   Карточки наугад выкладываем в ряд. Сколько при этом можно получить различных шестизначных чисел?

      Решение. Сначала слева направо пронумеруем места в ряду, куда выкладываем карточки: первое место, второе, третье, четвертое, пятое, шестое. На первое место можно положить одну из 6 карточек. Для этого есть   6   способов. В каждом из этих 6 способов на второе место можно положить одну из оставшихся   5   карточек. Таким образом, существует

способов, чтобы положить карточки на первое и второе места. В каждом из этих   30   способов на третье место можно положить одну из оставшихся   4   карточек. Следовательно, существует

способов, чтобы положить карточки на первое, второе и третье места. В каждом из этих   120   способов на четвертое место можно положить одну из оставшихся   3   карточек. Отсюда вытекает, что существует

способов, чтобы положить карточки на первое, второе, третье и четвертое места. В каждом из этих   360   способов на пятое место можно положить одну из оставшихся   2   карточек. Следовательно, существует

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

      Ответ: 720.

      Замечание 1. В задаче мы рассмотрели   6   пронумерованных карточек и установили, что количество способов выкладывания этих карточек в ряд равно   6!

      Если бы у нас было n пронумерованных карточек, то количество способов выкладывания их в ряд равнялось бы   n ! .

      Замечание 2. Каждое расположение   n   пронумерованных карточек в ряд является перестановкой из n элементов, к изучению которых мы сейчас и переходим.

      Определение 1. Пусть   n   – натуральное число. Рассмотрим произвольное множество, содержащее n элементов. Говорят, что на этом множестве задано упорядочение (отношение порядка), если его элементы пронумерованы числами   1, 2, 3, … , n.

      Множество с заданным упорядочением называют упорядоченным множеством.

      Определение 2. Рассмотрим множество, содержащее n элементов. Перестановкой из n элементов называют любое упорядочение этого множества.

      Число перестановок из   n   элементов обозначают символом   P_n.

      В соответствии с Замечанием 1, справедлива формула:

P_n = n !

      В частности,

P₆ = 6! = 720 .

      Замечание 3. Введенные в данном разделе перестановки называют также перестановками без повторений.