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

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

Определение 2: Пусть имеется различных предметов. Расстановки из элементов по элементов () называются размещениями без повторений. Обозначают: . Здесь имеется в виду, что элементы в расстановках не повторяются.

В данном определении существенной является следующая позиция: две расстановки различны, если они отличаются хотя бы одним элементом или порядком элементов.

Теорема 1: Число всех размещений без повторений вычисляется по формуле:

.

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

Выбор элементов осуществляется поэтапно. Первый элемент расстановки можно выбрать различными способами. Тогда из оставшихся элементов множества второй элемент расстановки выбирается способом. Для выбора третьего элемента возможно способа и т.д. Тогда для выбора - го элемента имеем способ. Следовательно, согласно правилу умножения, количество таких расстановок будет равно:

.

По определению, такие расстановки являются размещениями. Что и требовалось доказать.

Пример: Собрание из 25 человек выбирает президиум из 3 человек. Сколько возможно вариантов выбора?

Решение. .

Замечание: Число размещений без повторений можно также находить по формуле:

.

Если в знаменателе дроби , то принято считать .

2) Размещения с повторениями.

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

Теорема 2: Число всех размещений из элементов по элементов с повторениями находится по формуле:

.

Доказательство. Если имеется упорядоченных мест, для каждого из которых можно выбрать любой из объектов, то согласно комбинаторному принципу умножения, существует способов выбора объектов. Таким образом, число перестановок с повторением, когда объектов выбираются из объектов, равно , что и требовалось доказать.

Доказать теорему можно также индукцией по числу .

Примеры: количество телефонных номеров, автомобильных номеров, комбинаций в секретном замке, генетический код. Во всех этих ситуациях в расстановках элементы могут повторяться.

Количество комбинаций в секретном замке, число телефонных номеров, число автомобильных номеров, код Морзе, генетический код.

Разгадка генетического кода – крупнейшее достижение биологии ХХ века. Информация записана в гигантских молекулах ДНК (дезоксирибонуклеиновой кислоты). Различные молекулы ДНК отличаются порядком 4-х азотистых оснований. Эти основания определяют порядок построения белков организма из двух десятков аминокислот, причём каждая аминокислота зафиксирована кодом из 3-х азотистых оснований.

В одной хромосоме содержится несколько десятков миллионов азотистых оснований. Число различных комбинаций, в которых они могут идти друг за другом столь велико, что ничтожной доли этих комбинаций хватит для зашифровки всего многообразия живых организмов за время существования жизни на земле, оно равно , где – число оснований в хромосоме.