Размещением называется упорядоченная выборка фиксированного числа попарно различных элементов конечного множества. При этом считается, что количество размещаемых элементов m не превосходит мощность n образующего множества, откуда они выбираются. Различными считаются любые размещения, которые не совпадают по составу или взаимному расположению своих элементов. Например, выбирая по два числа из множества натуральных чисел от 1 до 4 можно составить всего 12 различных размещений из n=4 по m=2 элемента, которые образуют следующие упорядоченные пары чисел:

В общем случае систематическое перечисление размещений из n элементов по m элементов при произвольных целочисленных значениях n>m>0 обеспечивает следующий итерационный процесс, который можно назвать лексиграфическим алгоритмом размещения. Итерации этого алгоритма формируют размещения в лексиграфическом порядке, используя соответствующую лексиграфическую технику генерации перестановок. Для описания данного алгоритма, как обычно, удобно рассматривать множество последовательных целых чисел от 1 до n. На каждой итерации из этого диапазона выбираются m<n различных целых чисел, с целью сформировать лексиграфически упорядоченную последовательность числовых векторов, которые образуют искомые размещения. Этот итерационный процесс должен начинаться с лексиграфически наименьшего размещения, которое образует выборка первых m натуральных чисел указанного диапазона, которые располагаются в порядке возрастания своих величин:

На каждой следующей итерации очередное размещение строится по предыдущему. Для этого нужно выполнить следующие 3 операции. Сначала следует дополнить (+) текущее размещение до перестановки n чисел, приписав к нему справа, в порядке убывания своих величин все целые числа из диапазона от 1 до n, которые отсутствуют в этом размещении. Затем, по полученной перестановке требуется найти следующую в лексиграфическом порядке (L) перестановку. Для этого можно использовать соответствующий фрагмент алгоритма перечисления перестановок в лексиграфическом порядке. Наконец, необходимо исключить (−) из полученной перестановки (n−m) хвостовых чисел. Оставшиеся m чисел образуют очередное размещение, которое будет лексиграфически больше любого из предыдущих.

Выполнение всех рассмотренных операций алгоритма иллюстрирует следующий пример, где по размещению (4, 1, 5) из множества целых чисел от 1 до 5 строится очередное размещение (4, 2, 1):

Аналогичные итерации должны продолжаться до получения лексиграфически наибольшего размещения из m максимальных чисел диапазона от 1 до n, которые располагаются в порядке убывания своих величин:

Рассмотренный лексиграфический алгоритм можно приспособить для порождения размещений в обратном лексиграфическом порядке. В этом случае последовательность размещений должна начинаться с лексиграфически наибольшего, а каждое следующее размещение лексиграфически меньше предыдущего. Обратный лексиграфический порядок всех промежуточных размещений может обеспечить соответствующее изменение процедуры генерации очередной перестановки, полученной дополнением текущего размещения.

Во многих практических случаях важно иметь возможность найти общее число размещений, не перечисляя их все. В общем случае число размещений из n элементов по m дает значение убывающего m-факториала от n, которое можно вычислить по следующим мультипликативной и факториальной формулам:

(n)_m = n(n−1)(n−2) … (n−m+1) = n!(n-m)! = Amn

Например, вычисление числа размещений для случая n=5 и m=3 по любой из этих формул дает следующий результат:

Аналогичным образом можно определить число размещений из n элементов по m для любых целых значений n≥m≥0. При m=0 число размещений не имеет комбинаторного смысла и формально принимается равным 1. При m=n оно равно n! и совпадает с числом перестановок из n элементов. Кроме того, при m=1 число размещений равно n. Все эти граничные значения числа размещений непосредственно следуют из его факториальной формулы:

Факториальная формула позволяет также установить соотношение между числами сочетаний и размещений. Его можно получить, если умножить числитель и знаменатель факториальной формулы числа размещений на m! и использовать факториальную формулу числа сочетаний:

Это формальное соотношение имеет следующую комбинаторную трактовку. Любое сочетание, которое образуется неупорядоченной выборкой m элементов, можно упорядочить, переставляя его элементы m! различными способами, порождая, соответственно, m! различных размещений этих элементов. Таким образом, общее число размещений, которое может быть получено этим способом, должно быть в m! раз больше числа сочетаний. Кроме того, это соотношение имеет конструктивный характер, предоставляя возможность систематической генерации размещений комбинированным применением алгоритмов перечисления сочетаний и перестановок.

Следует отметить, что для определения числа размещений вместо мультипликативной или факториальной формулы, также применяются различные рекуррентные соотношения, которые основаны на свойствах убывающих факториалов. Наиболее очевидным является следующее рекуррентное соотношение, которое непосредственно получается из рекурсивного определения убывающего факториала:

Использование этого рекуррентного соотношения иллюстрирует следующий пример, где нужно найти число размещений из n=5 элементов по m=3 элемента:

Еще одно полезное рекуррентное соотношение для числа размещений можно легко проверить подстановкой мультипликативной или факториальной формул. Оно похоже на аналогичные рекуррентные соотношения для чисел Стирлинга или биномиальных коэффициентов и имеет следующий вид:

Использование этого рекуррентного соотношения для определения числа размещений из n=5 элементов по m=3 поясняет следующий пример: