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

Правило умножения отвечает на вопрос «сколько всего получится наборов», когда набор собирают по шагам. Чаще всего в набор попадают сразу все предметы, и меняется только порядок: кто за кем стоит в шеренге, в каком порядке лыжники уходят со старта, какому хоккеисту достанется какой номер. У таких задач ответ записывается одним коротким значком, и весь параграф про него.

Начнём с трёх человек: Андрея, Бориса и Владимира надо построить в шеренгу. На первое место годится любой из троих. Кого бы мы туда ни поставили, для второго места остаётся выбор из двоих, а последнему достаётся единственное свободное место. Перемножаем числа вариантов по шагам: 3 · 2 · 1 = 6. Все шесть шеренг выписаны в таблице (рис. 1) — каждая строка один способ, и ни один не повторяется дважды.

Тот же перебор удобно нарисовать деревом (рис. 2). Из корня выходят три ветви: кто встанет первым. Из каждой ветви растут ещё две: кто из оставшихся встанет вторым. Третьего называть уже не нужно — он определён однозначно. Внизу шесть концов, по одному на шеренгу. Дерево показывает то, чего не видно в готовом ответе «шесть»: множители убывают, потому что после каждого выбора людей остаётся на одного меньше.

Если людей четверо, первым может оказаться любой из четверых, а троих оставшихся, как мы уже знаем, расставляют шестью способами: 4 · 6 = 24. Дальше так же: семерых расставляют 7 · 6 · … · 2 · 1, а это уже 5040 способами. Уже здесь видно главное: выписать все способы невозможно, а сосчитать их легко.

Перестановкой из n предметов называют любой способ расположить эти предметы в ряд, то есть присвоить им номера с первого по n-й.

Произведение убывающих чисел от n до единицы встречается так часто, что для него завели отдельное обозначение.