Теория: Размещения без повторений
В комбинаторике часто возникает необходимость определить число возможных способов выбора некоторой части элементов из имеющегося набора, при котором фиксируется не только состав этой группы, но и точный порядок их расположения.
- Размещением из $n$ элементов по $k$ (где $k \le n$) называется любой упорядоченное соединение (набор), состоящее из $k$ различных элементов, выбранных из данного множества, содержащего $n$ элементов.
Главным условием применения классической формулы является уникальность элементов исходного множества и отсутствие их повторения внутри одной комбинации. Два размещения считаются различными, если они отличаются своим компонентным составом, либо при одинаковом составе элементов отличаются порядком их расположения.
Вывод формулы на основе правила умножения
Для вывода формулы подсчета числа размещений воспользуемся комбинаторным правилом умножения. Представим задачу как последовательное заполнение $k$ имеющихся свободных позиций элементами из набора объемом $n$:
- На первую позицию можно выбрать любой из $n$ имеющихся элементов исходного множества.
- На вторую позицию можно поместить один из оставшихся $(n - 1)$ элементов.
- На третью позицию выбирается один из $(n - 2)$ элементов, и так далее.
- Для последней, $k$-й позиции количество доступных вариантов выбора сократится до выражения $(n - k + 1)$.
По правилу умножения общее число способов составить такое упорядоченное подмножество равно произведению вариантов для каждого места. Это число обозначают символом $A_n^k$ (от французского arrangement — размещение, приведение в порядок) и записывают в виде цепочки убывающих множителей:
$$A_n^k = n \cdot (n - 1) \cdot (n - 2) \cdot \dots \cdot (n - k + 1)$$
Если умножить и разделить это выражение на произведение натуральных чисел от $1$ до $(n - k)$, то с помощью символа факториала формулу для нахождения числа размещений без повторений можно записать в более компактном виде:
$$A_n^k = \frac{n!}{(n-k)!}$$
Если длина выборки совпадает с размером исходного множества ($k = n$), то размещение превращается в частный случай — перестановку. В этой ситуации знаменатель принимает значение $0! = 1$, а формула приобретает вид тождества $A_n^n = P_n = n!$.
Примеры решения задач
Рассмотрим практическое применение формулы на конкретных задачах.
Задача 1 (Составление кодов из заданных цифр). Сколько различных трехзначных кодовых комбинаций можно составить из цифр 1, 3, 5, 7 и 9 при условии, что цифры в записи кода не должны повторяться?
Исходное множество содержит $n = 5$ уникальных элементов, из которых требуется составить упорядоченные группы по $k = 3$ элемента в каждой. Так как порядок цифр в коде имеет значение, применим формулу размещений без повторений:
$$A_5^3 = \frac{5!}{(5-3)!} = \frac{5!}{2!} = 5 \cdot 4 \cdot 3 = 60$$
Из данного набора цифр можно составить ровно 60 уникальных трехзначных кодов.
Задача 2 (Выборы на руководящие должности). В совете директоров компании состоят 8 человек. Сколькими способами среди них можно распределить три разные должности: председателя, секретаря и аудитора?
В этой задаче порядок распределения критически важен, поскольку один и тот же состав людей на разных должностях образует разные структуры управления. Так как один человек не может занимать две должности одновременно, применим формулу для $n = 8$ и $k = 3$:
$$A_8^3 = \frac{8!}{(8-3)!} = \frac{8!}{5!} = 8 \cdot 7 \cdot 6 = 336$$
Существует ровно 336 вариантов распределения административных должностей среди членов совета.
Задача 3 (Распределение призовых мест). В турнире по шахматам участвуют 4 гроссмейстера — из России, Франции, Китая и Индии. Требуется определить, сколькими способами могут распределиться между ними золотая и серебряная медали.
Количество участников турнира $n = 4$, а число призовых мест $k = 2$. Подставим эти параметры в формулу:
$$A_4^2 = \frac{4!}{(4-2)!} = \frac{4!}{2!} = 4 \cdot 3 = 12$$
Существует ровно 12 вариантов исхода чемпионата. Полный список всех возможных распределений призовых мест (Золото — Серебро) выглядит следующим образом:
- Россия — Франция
- Россия — Китай
- Россия — Индия
- Франция — Россия
- Франция — Китай
- Франция — Индия
- Китай — Россия
- Китай — Франция
- Китай — Индия
- Индия — Россия
- Индия — Франция
- Индия — Китай
Зависимость числа размещений от количества элементов в выборке носит нелинейный характер. Для исходного множества из 5 элементов выборка из 1 элемента даст всего 5 вариантов, выборка из 2 элементов увеличит число исходов до 20, а при увеличении выборки до 3 элементов количество возможных размещений возрастет до 60.