Размещение

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

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

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

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

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

Число размещенийПравить

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

$A_n^k=n^{\underset{\_<!--\; \_\; -->}{k}}=(n{)}_k=n(n-<!--\; -\; -->1)\cdot <!--\; \cdot \; -->\dots <!--\; \dots \; -->\cdot <!--\; \cdot \; -->(n-<!--\; -\; -->k+1)=\frac{n!}{(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$$A_{n}^{k}=(n-k+1)_{k}$ .

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

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

$A_n^n=P_n=n!$$A_{n}^{n}=P_{n}=n!$ .

Справедливо следующее утверждение:$A_n^{n-<!--\; -\; -->1}=A_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$$A_{n}^{n-1}={\frac {n!}{(n-(n-1))!}}={\frac {n!}{(n-n+1)!}}=n!=A_{n}^{n}$ .

 

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

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

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

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

По правилу умножения число размещений с повторениями из n по k, обозначаемое ${\stackrel{¯<!--\; ¯\; -->}{A}}_n^k$$\bar{A}_n^k$ , равно:

${\stackrel{¯<!--\; ¯\; -->}{A}}_n^k=n^k$${\bar {A}}_{n}^{k}=n^{k}$ .

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

${\stackrel{¯<!--\; ¯\; -->}{A}}_{10}^3={10}^3=1000$${\bar {A}}_{10}^{3}=10^{3}=1000$ .

Ещё один пример: размещений с повторениями из 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 вариантов с повторением трех из пяти чисел

См. такжеПравить

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