Размещение

В комбинаторике размеще́нием (из 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)\cdot \ldots \cdot (n-k+1)={\frac {n!}{(n-k)!}}}$.

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

${\displaystyle A_{n}^{k}=(n-k+1)_{k}}$.

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

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

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

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

${\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}}$.

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

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

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

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

${\displaystyle {\bar {A}}_{n}^{k}=n^{k}}$.

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

${\displaystyle {\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.

См. также

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

Примечания

1. ISBN 978-5-406-05433-8 Учебник по математике для СПО под редакцией Башмакова М.И. Архивная копия от 9 декабря 2019 на Wayback Machine
2. Виленкин Н.Я. Глава III. Комбинаторика кортежей и множеств. Размещения с повторениями // Популярная комбинаторика. — М.: Наука, 1975. — С. 80. — 208 с. Архивировано 14 октября 2010 года.
3. Теория конфигураций и теория перечислений  (неопр.). Дата обращения: 30 декабря 2009. Архивировано 23 января 2010 года.
4. Глава 3. Элементы комбинаторики Архивная копия от 4 января 2010 на Wayback Machine. // Лекции по теории вероятностей.
5. Корн Г., Корн Т. Табл. 18.7-2(2.b), 18.7-3(2.b) // Справочник по математике для научных работников и инженеров. — М.: Наука, 1973. — С. 568. — 832 с. Архивировано 30 декабря 2021 года.
6. Комбинаторный анализ // Математическая энциклопедия / Под ред. И. М. Виноградова. — М., 1977. — Т. 2. — С. 974. — (Сов. энциклопедия). Архивировано 20 ноября 2012 года.

Ссылки