Комбинаторные алгоритмы для программистов



             

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


Имеется

n
различных предметов. Сколько из них можно составить
k
-расстановок? При этом две расстановки считаются различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке. Такие расстановки называют размещениями без повторений, а их число обозначают
A_n^k
. При составлении
k
-размещений без повторений из
n
предметов нам надо сделать
k
выборов. На первом шагу можно выбрать любой из имеющихся
n
предметов. Если этот выбор уже сделан, то на втором шагу приходится выбирать из оставшихся
n - 1
предметов. На
k
- м шагу
n-k+1
предметов. Поэтому по правилу произведения получаем, что число
k
-размещений без повторения из
n
предметов выражается следующим образом:
A_n^k = n(n - 1)\ldots (n - k + 1).




Содержание    Вперед