Пример 14
О драконах – ни слова!
Итак, мы собрались вместе! – промолвил Торин. Видимо, мы должны благодарить за это судьбу и мистера Бэггинса. Он безусловно заслужил нашу благодарность, хотя и жаль, что он не подготовил более удобный способ транспортировки. Тем не менее еще раз к вашим услугам, мистер Бэггинс. По-настоящему мы почувствуем благодарность, когда поедим и придем в себя. А пока – что делать дальше?
- Предлагаю идти в Озерный город, – ответил Бильбо. – Что же еще? Ничего другого не оставалось, и, покинув остальных на берегу, Торин, Фили, Кили и хоббит направились вдоль озера к мосту.
Я думаю, вы помните, что вместе с хоббитом Бильбо Бэггинсом путешествовали 13 гномов. Сколькими способами мог Бильбо выбрать себе трех спутников для визита к мэру Озерного города?
Решение.
Вам может показаться, что эту задачу мы уже решили – это число размещений из 13 по 3. Однако, между этими задачами есть существенная разница – в задаче о размещениях был важен порядок, в котором следуют элементы. Здесь же все три выбранных в спутники гнома будут равноправны. Любая выбранная тройка называется сочетанием из 13 по 3. Количество сочетаний обозначается C313.
Решать эту задачу мы будем, сравнивая ее с задачей о размещениях: что-то общее между этими задачами все-таки есть.
Пусть троица гномов уже выбрана, и, построившись в колонну по одному, марширует в Озерный город. Мы знаем, сколькими способами можно выбрать 3 гномов из 13 и построить их по порядку: это – количество размещений, оно равно A313.
С другой стороны, каждое размещение можно получить, сначала выбрав соответствующее сочетание (одним из C313 способов), а потом построив этих троих гномов в колонну (одним из P3 способов). Т.е. число размещений равно C313∙P3.
Приравниваем эти две величины:
Отсюда можем найти число сочетаний:
Как найти число размещений и перестановок, мы уже знаем:
(Произведение 3 последовательных убывающих сомножителей, начиная с 13);
(Произведение первых 3 чисел, т.е. 3!).
Поэтому
Бильбо Бэггинс может выбрать себе трех спутников 286 способами.
Пример 15
Еще раз вспомним волейбольного тренера, у которого есть 10 игроков, способных сыграть на любой позиции. На этот раз спросим, сколькими способами он может выбрать на игру 6 игроков (как они будут расставлены по площадке – не важно).
Решение.
Мы знаем, что количество способов выбрать из 10 игроков шестерых и расставить их по площадке равно по формуле (2)
С другой стороны, можно сначала выбрать стартовую шестерку (одним из C610 способов), а затем расставить этих игроков по площадке (одним из P6 способов). Следовательно:
Обобщение. Вывод рабочей формулы.
Сформулируем общую задачу. Пусть у вас есть множество из n элементов, из которых нужно выбрать k штук, при этом порядок этих k элементов не имеет значения.
Мы знаем, сколькими способами можно выбрать k элементов и расставить их по порядку: это число равно Akn . Этот выбор можно разбить на два этапа: выбор сочетания из n элементов по k (мы как раз и ищем количество таких сочетаний Ckn ) и перестановка элементов этого сочетания в определенном порядке (их количество равно Pn . Поэтому:
(6).
(7).То есть, чтобы найти количество сочетаний из n элементов по k, нужно произведение k последовательных убывающих сомножителей, начиная с n – разделить на произведение первых k натуральных чисел.
Как и формулы для размещений и перестановок, формулу для количества сочетаний можно записать короче:
(2).
(3).
(8).