В комбинаторике размеще́нием (из n по k) называется упорядоченный набор из k различных элементов из некоторого множества различных n элементов.
Пример № 1: — это 4-элементное размещение из 6-элементного множества .
Пример № 2: некоторые размещения элементов множества по 2: … … …
В отличие от сочетаний, размещения учитывают порядок следования предметов. Так, например, наборы и являются различными размещениями, хотя состоят из одних и тех же элементов (то есть совпадают как сочетания).
Заполнить ряд - значит надо поместить на каком-нибудь месте этого ряда какой-либо объект из данного множества (причём каждый объект можно использовать всего лишь один раз). Ряд, заполненный объектами данного множества, называется размещением , т. е. мы разместили объекты на данных местах. ISBN 978-5-406-05433-8 Учебник по математике для СПО под редакцией Башмакова М.И.
Число размещений Число размещений из n по k, обозначаемое , равно убывающему факториалу: . Элементарным образом выражается через символ Похгаммера: .
Последнее выражение имеет естественную комбинаторную интерпретацию: каждое размещение из n по k однозначно соответствует некоторому сочетанию из n по k и некоторой перестановке элементов этого сочетания; число сочетаний из n по k равно биномиальному коэффициенту , в то время как перестановок на k элементах ровно k! штук.
При k = n число размещений равно числу перестановок порядка n:Глава 3. Элементы комбинаторики . // Лекции по теории вероятностей. .
Справедливо следующее утверждение:. Доказывается тривиально: .
Размещение с повторениями Размещение с повторениями или выборка с возвращением — это размещение «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз.
Число размещений с повторениями По правилу умножения число размещений с повторениями из n по k, обозначаемое , равно: .
Например, число вариантов 3-значного кода, в котором каждый знак является цифрой от 0 до 9 и может повторяться, равно: .
Ещё один пример: размещений с повторениями из 4 элементов a, b, c, d по 2 равно 42 = 16, эти размещения следующие: aa, ab, ac, ad, ba, bb, bc, bd, ca, cb, cc, cd, da, db, dc, dd.
См. также
Обобщённая схема размещения Сочетание Перестановка
Примечания
Ссылки
Категория:комбинаторика