Доказательство. Действительно, на первом шаге можно выбрать любой из n имеющихся предметов

Действительно, на первом шаге можно выбрать любой из n имеющихся предметов. Если этот выбор уже сделан, то на втором шаге приходится выбирать из n – 1 предметов – ведь повторный выбор сделать уже нельзя. Точно так же на третьем шаге для выбора остается n – 3 предмета и т. д. Используя правило произведения, получим требуемую формулу.

Задача.

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

Решение.

Переформулируем задачу: Сколько существует комбинаций из 17 элементов по 3, если важны порядок элементов в комбинации, состав элементов и в комбинацию не могут входить элементы одного типа. (Повторения здесь быть не может – одна и та же команда не может получить и золотую и серебреную медаль.)

Эта задача относится к задачам на размещения без повторения. По формуле получаем: медали могут распределиться =17×16×15=4 080 способами.

Задача.

Автомобильные номера некоторой страны состоят из 3 букв (все буквы различны) и четырех цифр (цифры могут повторяться). Сколько максимально машин может быть в этой стране, если в её алфавите 26 букв?

Решение.

Число комбинаций по 3 буквы из данных 26, при условии, что буквы не могут повторяться, определим с помощью формулы для вычисления количества размещений без повторений: =26×25×24=15 600.

Число комбинаций по 4 цифры из данных 10, если в комбинацию могут входить одинаковые цифры, найдем с помощью формулы для вычисления количества размещений с повторениями: =10⁴.

Тогда по правилу произведения различных автомобильных номеров – × =15600×10⁴=156×10⁶.

Перестановки

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

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

Число n-перестановок обозначают через Р_n. Общее правило вычисления количества перестановок:

Р_n=Аⁿ_n=n× (n-1) × (n-2) ×...×2×1=n!

Рассмотрим несколько задач, решаемых с применением этой формулы.

Задача

Сколькими способами можно расположить на книжной полке 6 томов детской энциклопедии?

Решение

Так как на полке располагаем все 6 томов, то различные расположения отличаются только порядком, но не составом. По формуле перестановок имеем 6!=720.

Задача.

Сколькими способами можно расположить на шахматной доске 8 ладей так, чтобы они не могли бить друг друга.

Решение.

На каждой вертикали и горизонтали должно стоять по одной ладье. Введем обозначения: перестановка (13256487) означает, что на первой горизонтали ладья стоит в первом поле, на второй – в третьем, на третьем – во втором и т.д. Таким образом, число искомых расположений равно количеству перестановок чисел 1, 2, 3, 4, 5, 6, 7, 8, то есть Р₈=8!=40320.

Задача.

Сколько способов разбить 6 мужчин и 6 женщин на пары для танцев?

Решение.

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

Задача.

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

Решение.

Если бы девушки стояли на месте, то получилось бы 7! способов. Так как танцующие кружатся, то их положение относительно окружающих предметов не существенно, а важно лишь взаимное расположение. Поэтому перестановки, переходящие друг в друга при кружении танцовщиц, необходимо считать одинаковыми. Из каждой перестановки можно получить еще шесть новых путем вращения. Значит, число 7! необходимо разделить на 7. Получаем 7!:7=6!=720 различных перестановок девушек в хороводе.

Перестановки с повторениями

Рассмотрим, как изменится количество перестановок, если некоторые из переставляемых предметов одинаковы.

Задача.

Сколько слов можно получить, переставляя буквы слова «март»? Сколько слов можно получить, если переставлять буквы слова «мама»?

Переставляя буквы слова «март» получим 24 различные перестановки, так как все переставляемые элементы различны.

Если же некоторые переставляемые предметы одинаковы, то получается меньше перестановок – некоторые перестановки совпадают друг с другом.

При перестановке букв слова «мама» имеем две пары одинаковых букв мм и аа. Сделаем их различными, дописав к одинаковым буквам различные индексы: м₁а₁м₂а₂. Рассмотрим все возможные перестановки:

м₁а₁м₂а₂ м₁м₂а₁а₂ а₁а₂м₁м₂ м₁а₁м₂а₂ м₁а₁а₂м₂ а₁м₁м₂а₂ а₁м₁а₂м₂

м₂а₁м₁а₂ м₂м₁а₁а₂ а₂а₁м₁м₂ м₂а₁м₁а₂ м₂а₁а₂м₁ а₁м₂м₁а₂ а₁м₂а₂м₁

м₁а₂м₂а₁ м₁м₂а₂а₁ а₁а₂м₂м₁ м₁а₂м₂а₁ м₁а₂а₁м₂ а₂м₁м₂а₁ а₂м₁а₁м₂

м₂а₂м₁а₁ м₂м₁а₁а₁ а₂а₁м₂м₁ м₂а₂м₁а₁ м₂а₂а₁м₁ а₂м₂м₁а₁ а₂м₂а₁м₁

Получили 24 различные перестановки, которые разбиваются на четверки одинаковых слов, если убрать индексы при буквах «м» и «а». Значит, всего различных перестановок .

Общая задача формулируется следующим образом:

Перестановками с повторениями из n₁ элементов первого типа, n₂ элементов второго типа,..., n_k элементов k-го типа называются всевозможные комбинации из этих элементов, каждая из которых содержит n_i элементов i-го вида. Комбинации отличаются друг от друга лишь порядком элементов.

Число перестановок с повторениями обозначают через Р(n₁, n₂,..., n_k). Общее правило вычисления количества перестановок с повторениями:

Р(n₁, n₂,..., n_k)=. .

Дата добавления: 2015-01-03