Размещение

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

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

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

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

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

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

Число размещений из n по k, обозначаемое [math]\displaystyle{ A_n^k }[/math], равно убывающему факториалу:

[math]\displaystyle{ A_n^k = n^{\underline k} = (n)_k = n(n-1)\cdot\ldots\cdot(n-k+1) = \frac{n!}{(n-k)!} }[/math].

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

[math]\displaystyle{ A_n^k=(n-k+1)_k }[/math].

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

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

[math]\displaystyle{ A_n^n=P_n=n! }[/math].

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

[math]\displaystyle{ A_n^{n-1} = \frac{n!}{(n-(n-1))!} = \frac{n!}{(n-n+1)!} = n! = A_n^n }[/math].

Все 60 вариаций без повторения трех из пяти чисел

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

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

Число размещений с повторениями

По правилу умножения число размещений с повторениями из n по k, обозначаемое [math]\displaystyle{ \bar{A}_n^k }[/math], равно:

[math]\displaystyle{ \bar{A}_n^k =n^k }[/math].

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

[math]\displaystyle{ \bar{A}_{10}^3 = 10^3 = 1000 }[/math].

Ещё один пример: размещений с повторениями из 4 элементов a, b, c, d по 2 равно 4² = 16, эти размещения следующие:

aa, ab, ac, ad, ba, bb, bc, bd, ca, cb, cc, cd, da, db, dc, dd.

Все 125 вариантов с повторением трех из пяти чисел

См. также

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