Размещение

В комбинаторике размещением называется расположение «предметов» на некоторых «местах» при условии, что каждое место занято в точности одним предметом и все предметы различны. Более формально, размеще́нием (из n по k) называется упорядоченный набор из k различных элементов некоторого n-элементного множества.

Например, $\langle 1,3,2,5\rangle$ — это 4-элементное размещение 6-элементного множества {1,2,3,4,5,6}.

В отличие от сочетаний, размещения учитывают порядок следования предметов. Так, например, наборы < 2,1,3 > и < 3,2,1 > являются различными, хотя состоят из одних и тех же элементов {1,2,3} (то есть совпадают как сочетания).

Количество размещений

Количество размещений из n по k, обозначаемое $A_n^k$, равно убывающему факториалу:

$A_n^k = n^{\underline k} = (n)_k = n(n-1)\cdots(n-k+1) = \frac{n!}{(n-k)!} = \binom{n}{k} k!.$

Последнее выражение имеет естественную комбинаторную интерпретацию: каждое размещение из n по k однозначно соответствует некоторому сочетанию из n по k и некоторой перестановке элементов этого сочетания; число сочетаний из n по k равно биномиальному коэффициенту $\binom{n}{k}$, в то время как перестановок на k элементах ровно k! штук.

При k=n количество размещений равно количеству перестановок порядка n:

$A_n^n=P_n=n!.$

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

Размещение с повторениями или выборка с возвращением — это размещение «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз. По правилу умножения количество размещений с повторениями из n по k равно:

$\bar{A}(n,k)= \bar{A}_n^k =n^k.$

Например, количество вариантов 3-x значного кода, в котором каждый знак является цифрой от 0 до 9 и может повторяться, равно:

$\bar{A}(10,3) = \bar{A}_{10}^3 = 10^3 = 1000.$

См. также

• Обобщённая схема размещения
• Сочетание
• Перестановка

Ссылки

• Видео о размещениях