Перестановки и размещения без повторений различных объектов

Перестановкой длины n называют расположение n различных объектов на n различных местах. Общее количество всех воз­можных попарно различных перестановок длины n обозначают как Р(n), А(n,n) либо .

Размещением без повторений из n по k (n³k) называют расположение k неодинаковых объектов на n различных местах (не более одного объекта на место). Общее количество мест n не меньше числа объектов k. Полное количество всех различных вариантов размещений без повторений из k по n обозначают как А (k, n) либо . Очевидно, что перестановки – частный случай размещений без повторений при равном количестве объектов и мест: k=n.

Подсчет общего числа вариантов расположения объектов в этом случае проще всего производить при помощи чисел вариантов L₁, L₂, …, L_k расположения каждого из объектов 1, 2,..., k.

Первый из размещаемых объектов можно разместить на любом из n имеющихся мест (число вариантов выбора L₁=n). Для второго размещаемого объекта число вариантов выбора L₂=n–1, поскольку 1 место уже занято. Для третьего по порядку размещаемого объекта L₃=n–2, …, для k-го – L_k=(n–k+1). По правилу умножения общее количество вариантов размещений без повторений из n по k равно произведению чисел вариантов L₁, L₂, ×××, L_k: =n×(n – 1)× …×(n–k+1)=n!/(n–k)!.

Общее число перестановок длины n: =n!.

Пример 5. Определить, сколькими вариантами можно разместить четырех гостей за столом, если число стульев, занимающих различные положения, равно: 1) 4; 2) 6?

Решение. В случае 1) имеет место расчет перестановок, так как количестве объектов равно числу мест для размещения: k=n. Поэтому L==4!=24.

В случае 2) число мест для размещения больше, чем число объектов (n>k), поэтому необходимо использовать формулу для расчета размещений без повторений из 6 по 4:

L==6!/(6–4)!=6×5×4×3=360.

Ответ. 1) 24; 2) 360.

Замечание. Обычно при расчете размещений без повторений полагают, что мест n не меньше, чем объектов k (n³k). Однако на практике количество объектов k может быть больше, чем мест для размещения n (k>n). Данный случай можно рассматривать аналогично предыдущему, представив его как распределение n мест по k объек­там. При этом количество возможных размещений без повторений равно k!/(k–n)!.

Таким образом, в задаче о распределении k неодинаковых объектов на n различных местах количество возможных размещений всегда можно представить в виде:

=M!/(M–m)!, где M=max(k, n); m=min(k, n).

Пример 6. Найти число вариантов размещения на 6 пронумерованных рабочих позициях станка различных инструментов, общее число которых равно 8.

Решение. Так как места и инструменты различны и k=8>n=6, то M=max(k, n)=8; m=min(k, n)=6.

Общее число вариантов размещения ==8!/(8–6)!=8×7×6×5×4×3=20160.

Ответ. 20160.

Дата добавления: 2014-01-20