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

Перестановки Еще одна типичная для комбинаторики ситуация: даны N объектов; нужно составить из них все возможные комбинации, переставляя их между собой. Такие комбинации называются перестановками из N элементов. Таким образом, перестановки отличаются друг от друга только порядком расположения элементов.

Их количество также легко найти с помощью правила умножения:

N·(N-1)·(N-2)·...·2·1 = N!

В самом деле, на первое место мы можем выбрать любой из N имеющихся элементов, после чего на второе - любой из (N-1) оставшихся, на третье - любой из (N-2) оставшихся и так далее до последнего элемента.

 
Факториал Обратите внимание на новое обозначение - N! Так в математике обозначают произведение всех натуральных чисел от 1 до N. Это произведение называется факториалом числа N, а само обозначение читается "эн факториал".

Заметим, что 1!=1. Интересно, что удобства (вы оцените его чуть позже) полагают и 0!=1.

 
Рост факториала Отметим одну важную особенность этой замечательной функции - ее быстрый рост. Приведем для примера несколько значений факториала для возрастающих значений N: