Размещения и перестановки

ЛЕКЦИЯ 2

Размещения и перестановки. Сочетания. Комбинации с повторениями. Комбинаторный способ вычисления вероятностей по классической схеме. Геометрическое определение вероятности. Статистическое определение вероятности.

Размещения и перестановки

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

Размещением из n элементов по k элементов называется любое упорядоченное подмножество из k элементов исходного множества, содержащего n различных элементов.

Число размещений можно найти из принципа умножения. Первый элемент размещения можно выбрать n способами. Как только такой выбор будет сделан, останется (n –1) возможностей, чтобы выбрать второй элемент; после этого останется (n –2) возможностей для выбора третьего элемента и т.д.; для выбора k- го элемента будет (n–k+ 1) возможностей. По принципу умножения находим

. (1.1)

Легко понять, что .

Пример 1.7. В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить 4 фотографии. Сколькими способами это можно сделать, если ни одна страница газеты не должна содержать более одной фотографии?

Решение. Для размещения фотографий следует отобрать 4 различных страницы из 12 имеющихся. Затем нужно отобранные страницы упорядочить, т.е. определить, на какую страницу поместить первую фотографию, на какую – вторую и т.д. Полученная упорядоченная совокупность страниц является, согласно определению, размещением из 12 элементов по 4, а число таких размещений является искомым результатом:

.

Рассмотрим частный случай, когда k=n. Соответствующее этому случаю размещение называется перестановкой.

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

Отметим, что перестановки состоят из одних и тех же элементов, но отличаются между собой порядком. Число перестановок n различных элементов обозначают символом P _n и равно

(1.2)

Пример 1.8. Сколькими способами можно расставить девять различных книг на полке, чтобы определенные четыре книги стояли рядом?

Решение. Будем считать выделенные книги за одну книгу. Тогда уже для шести книг существует P₆=6!=720 перестановок. Однако четыре определенные книги можно переставить между собой P₄=4!=24 способами. По принципу умножения имеем

P₆P₄ = 720×24 = 17280.