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

В соревнованиях участвуют 17 команд. Разыгрываются медали: золотые, серебряные, бронзовые. Сколькими способами они могут быть распределены?

Золотые медали может получить любая из 17 команд. Иными словами здесь у нас 17 возможностей. Но если золотые медали уже получены какой-то командой, то остаётся лишь 16 претендентов на серебряные медали. Повторения здесь быть не может. Точно также если уже вручены и золотые, и серебряные медали, то бронзовые медали может получить лишь одна из оставшихся 15 команд. По правилу произведения получаем, что медали могут быть распределены способами.

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

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

Имеются предметы различных типов. Сколько перестановок можно сделать из элементов первого типа, элементов второго типа, …, элементов - того типа.

Слово «». 2 типа букв и . Перестановки: - всего шесть.

Число элементов в каждой перестановке . Если все элементы различны, то число перестановок Первый можно переставить способами, второй - , …, -й – 1 способом. Но так как некоторые элементы совпадают, то мы имеем меньшее число перестановок. Элементы 1-го типа можно переставлять друг с другом способами, второго - и т.д. Эти перестановки можно делать независимо друг от друга. Так элементы перестановки можно переставлять между собой способами и она не меняется. перестановок распадается на части, состоящие из одинаковых перестановок каждая.

В нашем примере со словом «» число перестановок:

.

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

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

Например, число исходов полуфинала:

.

В частности:

.