Русская Википедия:Размещение
В комбинаторике размеще́нием (из n по k) называется упорядоченный набор из k различных элементов из некоторого множества различных n элементов.
Пример 1: <math>\langle 1,3,2,5\rangle</math> — это 4-элементное размещение из 6-элементного множества <math>\{1,2,3,4,5,6 \}</math>.
Пример 2: некоторые размещения элементов множества <math>\{1,2,3,4,5,6 \}</math> по 2: <math>\langle 1,2\rangle</math> <math>\langle 1,3\rangle</math> <math>\langle 1,4\rangle</math> <math>\langle 1,5\rangle</math> … <math>\langle 2,1\rangle</math> <math>\langle 2,3\rangle</math> <math>\langle 2,4\rangle</math> … <math>\langle 2,6\rangle</math>…
В отличие от сочетаний, размещения учитывают порядок следования предметов. Так, например, наборы <math>\langle 2, 1, 3 \rangle</math> и <math>\langle 3, 2, 1 \rangle</math> являются различными размещениями, хотя состоят из одних и тех же элементов <math>\{1, 2, 3\}</math> (то есть совпадают как сочетания).
Заполнить ряд - значит надо поместить на каком-нибудь месте этого ряда какой-либо объект из данного множества (причём каждый объект можно использовать всего лишь один раз). Ряд, заполненный объектами данного множества, называется размещением , т. е. мы разместили объекты на данных местах. [1]
Число размещений
Число размещений из n по k, обозначаемое <math>A_n^k</math>, равно убывающему факториалу:
- <math>A_n^k = n^{\underline k} = (n)_k = n(n-1)\cdot\ldots\cdot(n-k+1) = \frac{n!}{(n-k)!} </math>.
Элементарным образом выражается через символ Похгаммера:
- <math>A_n^k=(n-k+1)_k</math>.
Последнее выражение имеет естественную комбинаторную интерпретацию: каждое размещение из n по k однозначно соответствует некоторому сочетанию из n по k и некоторой перестановке элементов этого сочетания; число сочетаний из n по k равно биномиальному коэффициенту <math>\tbinom{n}{k}</math>, в то время как перестановок на k элементах ровно k! штук.
При k = n число размещений равно числу перестановок порядка n:[2][3][4]
- <math>A_n^n=P_n=n!</math>.
Справедливо следующее утверждение:<math>A_n^{n-1} = A_n^n</math>. Доказывается тривиально:
- <math>A_n^{n-1} = \frac{n!}{(n-(n-1))!} = \frac{n!}{(n-n+1)!} = n! = A_n^n</math>.
Размещение с повторениями
Размещение с повторениями или выборка с возвращением[5] — это размещение «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз.
Число размещений с повторениями
По правилу умножения число размещений с повторениями из n по k, обозначаемое <math>\bar{A}_n^k</math>, равно:[6][2][5]
- <math>\bar{A}_n^k =n^k</math>.
Например, число вариантов 3-значного кода, в котором каждый знак является цифрой от 0 до 9 и может повторяться, равно:
- <math>\bar{A}_{10}^3 = 10^3 = 1000</math>.
Ещё один пример: размещений с повторениями из 4 элементов a, b, c, d по 2 равно 42 = 16, эти размещения следующие:
- aa, ab, ac, ad, ba, bb, bc, bd, ca, cb, cc, cd, da, db, dc, dd.
См. также
Ссылки
- ↑ ISBN 978-5-406-05433-8 Учебник по математике для СПО под редакцией Башмакова М.И. Шаблон:Wayback
- ↑ 2,0 2,1 Шаблон:Книга
- ↑ Шаблон:Cite web
- ↑ Глава 3. Элементы комбинаторики Шаблон:Wayback. // Лекции по теории вероятностей.
- ↑ 5,0 5,1 Шаблон:Книга
- ↑ Шаблон:Книга
