Размещения

Упорядоченная (n,k) выборка, в которой элементы могут повторяться, называется (n,k) размещением с повторениями.
Иными словами размещениями с повторениями из n элементов по k на-зывают векторы длины k, составленные из n элементов множества Х.
Число размещений с повторениями из n элементов по k определяется оценкой соответствующего декартова произведения Хk n-элементного множества, обозначается   (по-видимому от английского слова Assing – назначать) и вычисляется следующим образом:
=nk.
Таким образом, первый элемент вектора длины k выбирается n спосо-бами, второй – n способами и т.д.: nn...n=nk.
Пример. Сколькими способами можно оснастить две различные фир-мы компьютерами трех типов?
Каждый способ оснащения есть выборка (3,2), вектор длины 2, состав-ленный из 3-х элементного множества типов Т={t1,t2,t3}. Поэтому число способов оснащения – число размещений с повторениями из 3 по 2:
.
Рассмотрим подробнее:
1) (t1,t1); 2) (t1,t2); 3) (t1,t3);
4) (t2,t2); 5) (t2,t3); 6) (t2,t1);
7) (t3,t3); 8) (t3,t2); 9) (t3,t1).
Получили различные упорядочения двухэлементных векторов из 3-х элементного множества, т.е. множество Т2.
Здесь каждый вектор соответствует способу оснащения. Видно, что, например, (t1,t2), (t2,t1) считаются разными способами, так как фирмы пред-полагаются различными («первая – первым типом», «вторая – вторым» и т.д.). Имеются повторения: (t1,t1), (t2,t2), (t3,t3).
В ряде задач необходимо определить число векторов длины 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, поэтому:
.