Размещение

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

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

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

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

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

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

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

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

.

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

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

.

Последнее выражение имеет естественную комбинаторную интерпретацию: каждое размещение из n по k однозначно соответствует некоторому сочетанию из n по k и некоторой перестановке элементов этого сочетания; число сочетаний из n по k равно биномиальному коэффициенту $(\binom{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}

.