Размещения, перестановки, сочетания

При решении комбинаторных задач мы имеем дело с комбинациями из некоторых предметов. Эти комбинации могут отличаться одна от другой числом предметов, их составом или порядком.

Пример 1. Пять бойцов сержанта Сбруева.

В отделении сержанта Сбруева проходят службу 5 новобранцев: Белкин, Пенкин, Фенькин, Свечкин и Овечкин. В свободное от нарядов время сержант обучает их, как рассчитаться по порядку. По команде «В одну шеренгу становись!» солдаты выстраиваются справа от Сбруева и по команде «По порядку номеров рассчитайсь!» производят расчет: «первый-второй-третий-четвертый-пятый». После этого сержант перестраивает новобранцев по-новому и расчет повторяется. Сколько раз может Сбруев повторить это упражнение, используя только разные способы построения солдат?

Решение. Договоримся указывать порядок расположения солдат первыми буквами их фамилий. Например, комбинация ПСОФБ означает, что первым является Пенкин, вторым — Свечкин и т.д. Все комбинации отличаются одна от другой порядком букв и называются перестановками из пяти букв. Нам нужно найти число всех таких перестановок. Сначала мы выведем общую формулу, а потом закончим обсуждение примера.

Пусть дано множество из п элементов. Занумеруем все элементы каким-нибудь способом от 1 до п (в случае с новобранцами п = 5). Ясно, что занумеровать можно многими способами.

Определение. Перестановкой из п элементов называется всякий способ нумерации этих элементов.

Теорема 2. Число всех различных перестановок из п элементов равно п!

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

Первый элемент можно выбрать п различными способами; второй выбирается из оставшихся п - 1 элементов, поэтому число всех способов выполнения второго действия будет п - 1. После выбора второго элемента их останется п - 2, следовательно, число способов, которыми можно выполнить третье действие, будет п - 2. Таким образом, число способов, которыми выполняется очередное действие, будет на единицу меньше предыдущего. Следовательно, четвертое действие можно выполнить (п - 2) способами, пятое — (п - 4) способами и т.д., наконец, последнее действие — одним способом.

По правилу умножения (теорема 1) число всех способов выполнения действий, т.е. число всех перестановок, равно п(п - 1)(п - 2) •... • 1 = п!. Теорема доказана.

Число всех перестановок из п элементов обозначают Р_п. Согласно теореме 1 его можно найти по формуле

Р_п = п!. (4)

Например, в случае с новобранцами (п = 5) мы получим Р₅ = 5! = 120.