10. Размещения

Упорядоченная (n,k) выборка, в которой элементы могут повторяться, называется (n,k) размещением с повторениями.

Иными словами размещениями с повторениями из n элементов по k называют векторы длины k, составленные из n элементов множества Х.

Число размещений с повторениями из n элементов по k определяется оценкой соответствующего декартова произведения Х^k n-элементного множества, обозначается (по-видимому от английского словаAssing – назначать) и вычисляется следующим образом:

=n^k.

Таким образом, первый элемент вектора длины k выбирается n способами, второй – n способами и т.д.: nn...n=n^k.

Пример. Сколькими способами можно оснастить две различные фирмы компьютерами трех типов?

Каждый способ оснащения есть выборка (3,2), вектор длины 2, составленный из 3-х элементного множества типов Т={t₁,t₂,t₃}. Поэтому число способов оснащения – число размещений с повторениями из 3 по 2:

.

Рассмотрим подробнее:

1) (t₁,t₁); 2) (t₁,t₂); 3) (t₁,t₃);

4) (t₂,t₂); 5) (t₂,t₃); 6) (t₂,t₁);

7) (t₃,t₃); 8) (t₃,t₂); 9) (t₃,t₁).

Получили различные упорядочения двухэлементных векторов из 3-х элементного множества, т.е. множество Т².

Здесь каждый вектор соответствует способу оснащения. Видно, что, например, (t₁,t₂), (t₂,t₁) считаются разными способами, так как фирмы предполагаются различными («первая – первым типом», «вторая – вторым» и т.д.). Имеются повторения: (t₁,t₁), (t₂,t₂), (t₃,t₃).

В ряде задач необходимо определить число векторов длины k из n элементов данного множества без повторения элементов.

Если элементы упорядоченной (n,k) выборки попарно различны, то они называются (n,k) размещением без повторений или просто (n,k) размещением.

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

Каждое (n,k) размещение без повторения является упорядоченной последовательностью длины k, элементы которой попарно различны и выбираются из множества с n элементами. Тогда первый элемент этой последовательности может быть выбран n способами, после каждого выбора первого элемента последовательности второй элемент может быть выбран n-1 способами и т.д., k-й элемент выбирается n-(k-1) способом:

=(n-1)(n-2)...[n-(k-1)].

Преобразуем эту формулу, умножая и деля ее на произведение чисел 12(n-k):

В частности, при k=0 . Очевидно, что приk>n =0.

Пример. Сколькими способами из 3-х студентов можно назначить группу на прополку клубники в составе начальника и подчиненного?

Речь идет о выборе упорядоченных двухэлементных подмножеств множества студентов, состоящего из трех элементов (K={1,2,3}), т.е. о размещениях без повторений из 3 элементов по 2, поэтому:

.

Подробнее, в виде векторов из номеров студентов, например, по журнальному списку, первая компонента которого обозначает номер студента-начальника, вторая – подчиненного:

(1,2), (1,3), (2,1), (2,3), (3,1), (3,2).

Ясно, что здесь существенен порядок следования компонент и не может быть повторений (один студент не может быть начальником и подчиненным одновременно), поэтому это множество – подмножество декартового произведения.

Пример. Сколькими способами можно провести распределение 10 механизаторов по 3 сушильным установкам? Один механизатор назначается на одну сушильную установку.

Распределение механизаторов – размещение без повторений из 10 элементов по 3, поэтому:

.