6. Упорядоченные множества. Размещения без повторений.

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

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

Одно и то же множество можно упорядочить различными способами (например, множество школьников в классе можно упорядочить по возрасту, по росту, по весу, по алфавиту и даже по столь случайному признаку, как время его прихода в школу 1 сентября).

Если задано -множество то можно составить различные упорядоченные -множества, в которые входят лишь элементы множества Например, из элементов множества можно составить 12 упорядоченных -множеств:

Упорядоченные -множества, состоящие из элементов -множества X, называют упорядоченными -подмножествами этого множества или размещениями без повторений из элементов по Их число обозначают Найдем формулу, выражающую через пит.

Итак, пусть задано -множество Упорядоченное -подмножество можно получить, выбирая из X поочередно элементы

Но в качестве первого элемента можно выбрать любой из элементов множества Поэтому такой выбор может быть произведен способами. После того как первый элемент выбран, второй элемент можно выбрать лишь способами (можно взять любой элемент, исключая уже выбранный). После выбора первых двух элементов остаются лишь возможности выбрать третий

элемент и т. д. Последний, элемент можно выбрать способами — ведь до него уже выбраны элемент, а потому осталось лишь элементов.

По правилу произведения (см. с. 25) получаем, что число упорядоченных -подмножеств -множества X равно произведению чисел т. е. Мы доказали, таким образом, что

Произведение первых натуральных чисел, т. е. называют -факториал и обозначают Произведение можно записать в виде дроби

т. е. в виде Итак, мы доказали, что

В частности, при получаем из формулы (2)

Это означает, что существует единственное упорядоченное множество длины 0 — пустой кортеж, не имеющий ни одной компоненты.