Размещение

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

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

Пример 2: некоторые размещения элементов множества $\{1,2,3,4,5,6\}$ по 2: $\langle 1,2\rangle$ $\langle 1,3\rangle$ $\langle 1,4\rangle$ $\langle 1,5\rangle$ … $\langle 2,1\rangle$ $\langle 2,3\rangle$ $\langle 2,4\rangle$ … $\langle 2,6\rangle$ …

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

Заполнить ряд - значит надо поместить на каком-нибудь месте этого ряда какой-либо объект из данного множества (причём каждый объект можно использовать всего лишь один раз). Ряд, заполненный объектами данного множества, называется размещением , т. е. мы разместили объекты на данных местах. ^[1]

Число размещений

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

A_{n}^{k}=n^{\underline {k}}=(n)_{k}=n(n-1)\cdot \ldots \cdot (n-k+1)={\frac {n!}{(n-k)!}}

.

Элементарным образом выражается через символ Похгаммера:

A_{n}^{k}=(n-k+1)_{k}

.

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

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

A_{n}^{n}=P_{n}=n!

.

Справедливо следующее утверждение: $A_{n}^{n-1}=A_{n}^{n}$ . Доказывается тривиально:

A_{n}^{n-1}={\frac {n!}{(n-(n-1))!}}={\frac {n!}{(n-n+1)!}}=n!=A_{n}^{n}

.