19. Упорядоченные выборки без возвращения-размещения

Имеется урна, в которой ровно n разных шаров. Поскольку из невознобновляемой урны нельзя извлечь больше шаров, чем в ней содержится, то число извлекаемых шаров не больше n.

В составляемой комбинации шар можно выбрать n способами, после чего в урне осталось (n-1) шаров, поэтому второй шар можно выбрать (n-1) способами. Продолжая этот процесс, получаем, что на последнем k-ом шаге в урне останется n-(k-1)=n-k+1 шаров, поэтому, в

силу основного комбинаторного правила, число всевозможных комбинаций будет (n-0)(n-1)…(n-(k-1))=n(n-1)…(n-k+1).

Другими словами, отвлекаясь от вспомогательной урновой схемы, в общем случае получаем, что в выборке элемент

выбирается n-0=n способами,

выбирается (n-1) способами,

и, отсюда замечая, что при всех элемент выбирается n-(m-1) способами, в частности, заключаем, что последний элемент выборки

- выбирается n-(k-1)=n-k+1 способами,

поэтому всего способов будет .

Тем самым, нами решена следующая конкретизация общей комбинаторной задачи:

Даны натуральные числа n и k, причем . Сколько из генеральной совокупности (множества) объема n можно извлечь упорядоченных выборок без возвращения объема k?

Ответ: произведению из k множителей, каждое из которых есть разность между n и числами 0,1,…, k-1: .

Упорядоченные выборки без возвращения также называют размещениями. Число размещений из n элементов по k обозначают . Таким образом,

= n(n-1)…(n-k+1).