🏁Из жизниТрое друзей выстроились в очередь в кино. Сколько существует способов их расставить? Первым может встать любой из трёх, вторым — любой из оставшихся двух, третьим — последний. Получаем $3 \cdot 2 \cdot 1 = 6$ разных очередей — и это тот самый счёт, который лежит в основе перестановок.
Факториал
Произведение всех натуральных чисел от $1$ до $n$ обозначают $n!$ (читают «эн факториал»):
Например, $2!=2$, $3!=6$, $4!=24$. По договорённости считают $1!=1$ и $0!=1$.
Определение и теорема
🔀ПерестановкаРасположение $n$ элементов в определённом порядке. Количество перестановок из $n$ элементов обозначают $P_n$ (от франц. permutation).
Теорема: для любого натурального $n$ справедливо $P_n = n!$.
1
База ($n=1$): один элемент можно расположить единственным способом: $P_1 = 1 = 1!$.
2
Переход: пусть верно $P_k=k!$. Чтобы получить перестановку из $(k{+}1)$ элементов — на первое место ставим один из $(k{+}1)$ элементов, а за ним располагаем оставшиеся $k$ элементов одним из $P_k=k!$ способов.
3
Значит $P_{k+1} = (k{+}1)\cdot k! = (k{+}1)!$ — верно и для $n=k{+}1$. По индукции формула верна для всех $n$. $\blacksquare$
Попробуй сам
На интерактиве справа выбери количество элементов $n$ ползунком — снизу появятся все их перестановки, а формула покажет, как растёт их число: $P_1=1$, $P_2=2$, $P_3=6$, $P_4=24$.
Запомни
🧠Перестановки
$n! = 1\cdot2\cdot\ldots\cdot n$, причём $0!=1!=1$ по договорённости;
$P_n$ — число способов расположить $n$ элементов в ряд, $P_n=n!$;
число перестановок быстро растёт: уже $P_{10}=10!=3\,628\,800$.