Размещения. Пусть имеется некоторое множество, содержащее конечное число членов

Пусть имеется некоторое множество, содержащее конечное число членов. Например, множество учебных групп в университете, множество книг на полке, множество населенных пунктов в данной области или, например, множество целых положительных чисел, меньших 10, и т.д. Все элементы такого множества можно пронумеровать, т. е. каждому элементу множества поставить в соответствие одно из чисел: 1, 2, 3, 4,..., п; в результате получается некоторая последовательность элементов данного множества, которые обычно записывают в виде a1, a2, а3,..., аn. Такие «занумерованные» множества будем называть упорядоченными. Таким образом, упорядоченное множество можно представить в виде некоторой последовательности, что будет использовано в дальнейшем. Очевидно, если в упорядоченном множестве поменять местами хотя бы два его элемента, то получим новое упорядоченное множество, которому будет соответствовать новая последовательность элементов данного множества.

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

Пример. Пусть имеется множество, содержащее четыре буквы: {А; В; С; D}. Запишем все возможные размещения из четырех указанных букв по две. Таких размещений 12: АВ; АС;.AD, BС; BD; CD; ВА; СА: DA; СВ; DB; DC.

Заметим, что размещения отличаются порядком входящих в них элементов и их составом. Размещения АВ и ВА содержат одинаковые буквы, но порядок их расположения различен. Поэтому эти размещения считаются разными.

Пример. Следующие последовательности цифр являются размещениями по 4 элемента из 10 элементов множества: {0; 1; 2; 3: 4: 5; 6; 7: 8: 9}: 3021, 4590; 8612; 7485; 1234.

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

На практике чаще представляет интерес количество раз­мещений, а не их конкретный вид. Число размещений из п элементов по т будем обозначать символом , где .

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

Первую фотографию можно поместить на любую из 12 страниц, т. е. 12 способами, вторую на любую из оставшихся 11 страниц, т. е. 11 способами. Для размещения третьей фотографии имеется 10 способов, а для последней - 9 способов. По правилу умножения четыре фотографии можно разместить на 12 страницах способами.

Найденное число размещений четырех фотографий на 12 страницах газеты - это число . Действительно, для раз­мещения фотографий следует отобрать 4 различных страницы газеты из 12 имеющихся. Затем необходимо отобранные страницы упорядочить, не обращая внимания на их номера, т.е. определить, на какую страницу поместить первую фо­тографию, на какую - вторую, и т.д.

Полученная упорядоченная совокупность страниц является согласно определению размещением из 12 элементов по 4, а число таких размещений является ответом.

Таким образом, . Последнее произведение можно представить в другом виде, если использовать символ факториала, для чего умножим и разделим его на 8! Имеем

Итак, .

Следующая теорема дает общую формулу для вычисления числа размещений, которая позволяет значительно упростить решение задач.

Теорема. Число размещений из n элементов по m равно

. (1)

Для доказательства воспользуемся правилом умножения. Чтобы составить какое-либо размещение, следует выбрать m элементов из множества, содержащего п элементов, и упорядочить полученную совокупность. Это означает, что надо заполнить т мест элементами рассматриваемого множества. На 1-е место можно поместить любой из п элементов. После этого останется п-1 элемент, каждый из которых может помещен на 2-е место. Поэтому 1-е место можно заполнить п способами, а 2-е – п-1 способами. Рассуждая аналогично получаем, что 3-е место можно заполнить n-2 способами, 4-е – n-3 способами и т. д. Последнее m-e место можно заполнить п-(т-1) способами. Все т мест по правилу умножения можно заполнить способами. Таким образом,

, (2)

Запишем выражение в правой части равенства (2) в более удобном виде, для чего умножим и разделим его на (п-т)!. Полагая, что , имеем

.

Формулы (1) и (2) при т< п совпадают, причем формула (2) имеет место для всех . Если п=т, то формула (1) принимает вид , а формула (2) - следующий вид: . В дальнейшем будем считать что позволяет использовать формулу (1) для случая п=m.