23-05-2023
В комбинаторике размещением называется расположение «предметов» на некоторых «местах» при условии, что каждое место занято в точности одним предметом и все предметы различны. Более формально, размеще́нием (из n по k) называется упорядоченный набор из k различных элементов некоторого n-элементного множества.
Например, — это 4-элементное размещение 6-элементного множества .
В отличие от сочетаний, размещения учитывают порядок следования предметов. Так, например, наборы и являются различными, хотя состоят из одних и тех же элементов (то есть совпадают как сочетания).
Содержание |
Количество размещений из n по k, обозначаемое , равно убывающему факториалу:
Последнее выражение имеет естественную комбинаторную интерпретацию: каждое размещение из n по k однозначно соответствует некоторому сочетанию из n по k и некоторой перестановке элементов этого сочетания; число сочетаний из n по k равно биномиальному коэффициенту , в то время как перестановок на k элементах ровно k! штук.
При k=n количество размещений равно количеству перестановок порядка n:[1][2][3]
Размещение с повторениями или выборка с возвращением[4] — это размещение «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз.
По правилу умножения количество размещений с повторениями из n по k, обозначаемое , равно:[5][1][4]
Например, количество вариантов 3-x значного кода, в котором каждый знак является цифрой от 0 до 9 и может повторяться, равно:
Размещение.
