Число размещений. Выбор без возвращения

Предположим, что r различных предметов размещаются по некоторым ячейкам. При этом ячейки различимы для наблюдателя и число их равно n. Предположим, что предметы размещаются таким образом, что в каждую ячейку попадает не более одного предмета. Занумеруем все имеющиеся предметы и ячейки. Тогда каждое размещение можно описать комбинацией вида (l ₁, l ₂,..., l_r), где l ₁ — номер ячейки, в которую попадает 1-й предмет, l ₂ — номер ячейки, в которую попадает 2-й предмет и т.д., l_r — номер ячейки, в которую попадает последний, r -й, предмет. В комбинации (i ₁, i ₂,..., i_r) i ₁ — один из n элементов (ячеек), i ₂ — один из n - 1 оставшихся элементов и т.д., i_r — один из n - r + 1 возможных элементов. Согласно общей формуле (5.1) всего существует

различных размещений r предметов по n ячейкам.

Предположим, что имеется совокупность nразличных элементов а ₁, а ₂,..., а_n. Из этой совокупности выбирается r элементов. Можно считать, что они выбираются одновременно и располагаются в определенном порядке, а можно считать, что элементы выбираются последовательно один за другим, причем выбранный предмет обратно не возвращается. В результате такого выбора образуется комбинация (а_{i 1}, а_{i 2},..., а_ir), где a_{i 1} — первый из выбранных элементов, a_{i 2} — второй из выбранных элементов и т.д., a_ir — последний из выбранных элементов; a_{i 1} может быть любым из n имеющихся элементов, a_{i 2} — любым из оставшихся n - 1 элементов и т.д., а_ir — любым из n - r + 1 возможных элементов. Всего существует

N = n (n - 1)...(n - r + 1) различных выборок (а_{i 1}, а_{i 2},..., а_ir) по r предметов, выбираемых без возвращения из совокупности объема n.

При r = n число размещений совпадает с числом перестановок из n элементов:

Пример.

Сколько различных списков (отличающихся порядком фамилий) можно составить из 7 различных фамилий?

Решение. N 7 = 7! = 2 ´ 3 ´ 4 ´ 5 ´ 6 ´ 7 = 5040.