Теорема. Количество упорядоченных k-элементных подмножеств n-элементного множества, все k элементов которого различны

Количество упорядоченных k-элементных подмножеств n-элементного множества, все k элементов которого различны, равно

Пример 1:

Студенту необходимо сдать три экзамена на протяжении семи дней. Сколькими способами это можно сделать?

Решение: Искомое число способов равно количеству трехэлемент­ных упорядоченных подмножеств множества из семи элементов, т. е. существует = 7 * 6 * 5 = 210 способов.

Если известно, что последний экзамен будет сдаваться на седьмой день, то число способов равно З * = 3 * 6 * 5 = 90.

Пример 2:

Сколькими разными способами можно разместить пять студентов в ауди­тории, которая имеет 20 мест?

Решение: Искомое число способов равно числу размещений из 20 элементов по 5 элементов, т. е. = 20 * 19 * 18 * 17 * 16 = 1 860 480.

Решение второго варианта задачи.

Пусть B={b₁, b₂,..., b_k} - некоторое конечное k-элементное множество, а А={а₁,а₂,...,а_n}- n-элементное множество и f: - функция из В в А. Как известно, функцию f можно задать с помощью таблицы значений

где . Теперь нашу задачу можно сформулировать так: сколько существует функций из множества В в множество А? В такой формулировке задача решается достаточно просто.

Условимся называть кортежем длины k элементы вида (а₁, а₂,..., a_k), где а; - не обязательно различные элементы некоторого конечного множест­ва А. Поскольку каждый элемент a_ij может быть любым элементом мно­жества А, то число различных кортежей вида (a_i1,a_i2,...,a_ik) может быть n^k.