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

Общее число размещений без повторений из n элементов по k элементов обычно обозначается так: .

Теорема 7.1.

. (7.1)

Доказательство. Задача сводится к заполнению k пустых мест символами элементов (рис. 7.1).

Рис. 7.1.

Первое место можно заполнить n различными способами, поскольку имеется n элементов, и повторения не допускаются. Второе место n – 1 способами, поскольку один элемент уже задействован. Третье место n – 2 способами, поскольку два элемента уже задействованы и т. д. Последнее k-тое место можно заполнить различными способами. Общее количество размещений будет равно произведению способов заполнения каждого из k мест.

Следствие. При n = k

Размещение (при n = k) называется перестановкой.

Пример 7.2. Если дано множество, состоящее из трех элементов: a, b и c, то количество размещений по два элемента равно , что соответствует результату, приведенному в примере 7.1.