МАЛЫЙ МЕХМАТ МГУ

Перестановки. Факториал

Два элемента a и b могут быть выписаны в строчку всего двумя способами: ab и ba. Для трёх элементов, как мы знаем из четвёртого примера, существует 6 вариантов. Нетрудно посчитать и число перестановок множества из 4 элементов:

1234, 1243, 1324, 1342, 1423, 1432,
2134, 2143, 2314, 2341, 2413, 2431,
3124, 3142, 3214, 3241, 3412, 3421,
4123, 4132, 4213, 4231, 4312, 4321.

Всего 24 перестановки, расположенные в 4 столбца по 6 перестановок в каждом. Очевидно, перестановки на 5 элементах можно расположить в 5 столбцов, по 24 в каждом. Значит, всего существует 5 · 24 = 120 таких перестановок.

Для числа перестановок n элементов есть обозначение: n! (читаем: «эн факториал»). Факториал равен произведению всех натуральных чисел от 1 до n. Например,

4! = 1 · 2 · 3 · 4.

Функция n! возрастает очень быстро. Так, 1! = 1, 2! = 2, 3! = 6, ..., 10! = 3 628 800. Факториалы возникают в комбинаторике очень часто. Поэтому принято считать, что если ответ выражен через факториалы, то всё сделано. (Этому в немалой степени способствует открытая в 1730 году английским математиком Дж. Стирлингом формула для приближённого вычисления:

n! ~ (2pn)^1/2nⁿ/eⁿ.

Относительная ошибка при пользовании этой формулой очень невелика и стремится к нулю при увеличении числа n. Что такое e и почему верна формула Стирлинга, семикласснику объяснить совершенно невозможно.)

Главное свойство факториала очевидно из определения:

(n + 1)! = (n + 1) · n!.

Подставим в эту формулу n = 0. Получим: 1! = 1 · 0!, откуда 0! = 1. И действительно, во многих формулах для единообразной записи очень удобно пользоваться обозначением 0! = 1. А вот определить (–1)! никак нельзя: равенство 0! = 0 · (–1)! невозможно ни при каком значении (–1)!.

Размещения

Следующее важное понятие комбинаторики — размещение. Давайте рассмотрим такую ситуацию: в классе, в котором 25 учеников, нужно выбрать старосту, его заместителя и помощника заместителя. Сколькими способами это можно сделать?

Очевидно, сначала 25 способами можно выбрать любого ученика в старосты. Затем из 24 оставшихся — заместителя старосты, а после этого любой из 23 оставшихся может оказаться помощником заместителя. По правилу произведения, всего имеем A₂₅³=25·24·23 вариантов.

Вообще, через A_n^k (читаем: «а из эн по ка») обозначают число способов выбрать из данных n элементов сначала первый элемент, потом второй, третий,..., k-й. Вычисляют его по формуле

A_n^k = n (n – 1) ... (n – k + 1).

Заметьте: в правой части ровно k множителей, и последний из них равен n – k + 1, а вовсе не n – k, как могло показаться на первый взгляд. Формулу можно записать и через факториалы:

A_n^k = n!/(n-k)!.

Числа сочетаний

Представьте себе, что в классе из 25 человек нужно выбрать не старосту, его заместителя и помощника его заместителя, а тройку начальников, которые, обладая равными правами, будут управлять и судить класс, не выясняя, кто из троих главный, кто менее главный, а кто так себе. Тогда способов будет не A₂₅³, а в 6 раз меньше. (Подумайте об этом хорошенько! Здесь 6 = 3! — количество способов ранжировать трёх начальников, то есть количество всех перестановок на множестве из 3 элементов.)

Вообще, очень важные для комбинаторики и теории вероятностей числа сочетаний C_n^k (читаем: «число сочетаний из эн по ка» или «це из эн по ка») можно вычислить по формуле C_n^k=A_n^k/k!=n!/(k!(n-k)!).

К сожалению, ни для точного определения, ни для свойств чисел сочетаний здесь места не нашлось. Но для первого знакомства с комбинаторикой сказанного и так предостаточно. Вернёмся лучше к нашим обычным задачам, оставив теорию на будущее.