WikiSort.ru - Не сортированное

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

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

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

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

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

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

${\displaystyle 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 равно биномиальному коэффициенту ${\displaystyle {\tbinom {n}{k}}}$ , в то время как перестановок на k элементах ровно k! штук.

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

${\displaystyle A_{n}^{n}=P_{n}=n!}$ .

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

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

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

Размещение с повторениями или выборка с возвращением^[4] — это размещение «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз.

См. также

Имеется викиучебник по теме
«Программная генерация размещений»

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

Ссылки