Перестановки, сочетания и размещения с повторениями Перечисленные виды комбинаций законспектированы в пункте №5 справочного материалаОсновные формулы комбинаторики, однако некоторые из них по первому прочтению могут быть не очень понятными. В этом случае сначала целесообразно ознакомиться с практическими примерами, и только потом осмысливать общую формулировку. Поехали:
Перестановки с повторениями
В перестановках с повторениями, как и в «обычных» перестановках, участвует сразу всё множество объектов, но есть одно но: в данном множестве один или бОльшее количество элементов (объектов) повторяются. Встречайте очередной стандарт:
Задача 12
Сколько различных буквосочетаний можно получить перестановкой карточек со следующими буквами: К, О, Л, О, К, О, Л, Ь, Ч, И, К?
Решение: в том случае, если бы все буквы были различны, то следовало бы применить тривиальную формулу , однако совершенно понятно, что для предложенного набора карточек некоторые манипуляции будут срабатывать «вхолостую», так, например, если поменять местами любые две карточки с буквами «К» в любом слове, то получится то же самое слово. Причём, физически карточки могут сильно отличаться: одна быть круглой с напечатанной буквой «К», другая – квадратной с нарисованной буквой «К». Но по смыслу задачи даже такие карточки считаются одинаковыми, поскольку в условии спрашивается о буквосочетаниях.
Всё предельно просто – всего: 11 карточек, среди которых буква:
К – повторяется 3 раза; О – повторяется 3 раза; Л – повторяется 2 раза; Ь – повторяется 1 раз; Ч – повторяется 1 раз; И – повторяется 1 раз.
Проверка: 3 + 3 + 2 + 1 + 1 + 1 = 11, что и требовалось проверить.
По формуле количества перестановок с повторениями: различных буквосочетаний можно получить. Больше полумиллиона!
Для быстрого расчёта большого факториального значения удобно использовать стандартную функцию Экселя: забиваем в любую ячейку =ФАКТР(11) и жмём Enter.
На практике вполне допустимо не записывать общую формулу и, кроме того, опускать единичные факториалы: Но предварительные комментарии о повторяющихся буквах обязательны!
Ответ: 554400
Другой типовой пример перестановок с повторениями встречается в задаче о расстановке шахматных фигур, которую можно найти на складе готовых решенийв соответствующей pdf-ке. А для самостоятельного решения я придумал менее шаблонное задание:
Задача 13
Алексей занимается спортом, причём 4 дня в неделю – лёгкой атлетикой, 2 дня – силовыми упражнениями и 1 день отдыхает. Сколькими способами он может составить себе расписание занятий на неделю?
Формула здесь не годится, поскольку учитывает совпадающие перестановки (например, когда меняются местами силовые упражнения в среду с силовыми упражнениями в четверг). И опять – по факту те же 2 силовые тренировки могут сильно отличаться друг от друга, но по контексту задачи (с точки зрения расписания) они считаются одинаковыми элементами.
Двухстрочное решение и ответ в конце урока.
Сочетания с повторениями
Характерная особенность этого вида комбинаций состоит в том, что выборка проводится из нескольких групп, каждая из которых состоит из одинаковых объектов.
Сегодня все хорошо потрудились, поэтому настало время подкрепиться:
Задача 14
В студенческой столовой продают сосиски в тесте, ватрушки и пончики. Сколькими способами можно приобрести пять пирожков?
Решение: сразу обратите внимание на типичный критерий сочетаний с повторениями – по условию на выбор предложено не множество объектов как таковое, а различные видыобъектов; при этом предполагается, что в продаже есть не менее пяти хот-догов, 5 ватрушек и 5 пончиков. Пирожки в каждой группе, разумеется, отличаются – ибо абсолютно идентичные пончики можно смоделировать разве что на компьютере =) Однако физические характеристики пирожков по смыслу задачи не существенны, и хот-доги / ватрушки / пончики в своих группах считаются одинаковыми.
Что может быть в выборке? Прежде всего, следует отметить, что в выборке обязательно будут одинаковые пирожки (т.к. выбираем 5 штук, а на выбор предложено 3 вида). Варианты тут на любой вкус: 5 хот-догов, 5 ватрушек, 5 пончиков, 3 хот-дога + 2 ватрушки, 1 хот-дог + 2 + ватрушки + 2 пончика и т.д.
Как и при «обычных» сочетаниях, порядок выбора и размещение пирожков в выборке не имеет значения – просто выбрали 5 штук и всё.
Используем формулу количества сочетаний с повторениями: способом можно приобрести 5 пирожков.
Приятного аппетита!
Ответ: 21
Какой вывод можно сделать из многих комбинаторных задач?
Порой, самое трудное – это разобраться в условии.
Аналогичный пример для самостоятельного решения:
Задача 15
В кошельке находится достаточно большое количество рублей, 2-, 5- и 10-рублёвых монет. Сколькими способами можно извлечь три монеты из кошелька?
В целях самоконтроля ответьте на пару простых вопросов:
1) Могут ли в выборке все монеты быть разными? 2) Назовите самую «дешевую» и самую «дорогую» комбинацию монет.
Решение и ответы в конце урока.
Из моего личного опыта, могу сказать, что сочетания с повторениями – наиболее редкий гость на практике, чего не скажешь о следующем виде комбинаций:
Размещения с повторениями
Из множества, состоящего из элементов, выбирается элементов, при этом важен порядок элементов в каждой выборке. И всё бы было ничего, но довольно неожиданный прикол заключается в том, что любой объект исходного множества мы можем выбирать сколько угодно раз. Образно говоря, от «множества не убудет».
Когда так бывает? Типовым примером является кодовый замок с несколькими дисками, но по причине развития технологий актуальнее рассмотреть его цифрового потомка:
Задача 16
Сколько существует четырёхзначных пин-кодов?
Решение: на самом деле для разруливания задачи достаточно знаний правил комбинаторики: способами можно выбрать первую цифру пин-кода и способами – вторую цифру пин-кода и столькими же способами – третью и столькими же – четвёртую. Таким образом, по правилу умножения комбинаций, четырёхзначный пин-код можно составить: способами.
А теперь с помощью формулы. По условию нам предложен набор из цифр, из которого выбираются цифры и располагаются в определенном порядке, при этом цифры в выборке могут повторяться (т.е. любой цифрой исходного набора можно пользоваться произвольное количество раз). По формуле количества размещений с повторениями:
Ответ: 10000
Что тут приходит на ум… …если банкомат «съедает» карточку после третьей неудачной попытки ввода пин-кода, то шансы подобрать его наугад весьма призрачны.
И кто сказал, что в комбинаторике нет никакого практического смысла? Познавательная задача для всех читателей mathprofi.ru:
Задача 17
Согласно государственному стандарту, автомобильный номерной знак состоит из 3 цифр и 3 букв. При этом недопустим номер с тремя нулями, а буквы выбираются из набора А, В, Е, К, М, Н, О, Р, С, Т, У, Х (используются только те буквы кириллицы, написание которых совпадает с латинскими буквами).
Сколько различных номерных знаков можно составить для региона?
Нет так их, кстати, и много. В крупных регионах такого количества не хватает, и поэтому для них существуют по несколько кодов к надписи RUS.
Решение и ответ в конце урока. Не забываем использовать правила комбинаторики ;-) …Хотел похвастаться эксклюзивом, да оказалось не эксклюзивом =) Заглянул в Википедию – там есть расчёты, правда, без комментариев. Хотя в учебных целях, наверное, мало кто прорешивал.
Наше увлекательное занятие подошло к концу, и напоследок я хочу сказать, что вы не зря потратили время – по той причине, что формулы комбинаторики находят ещё одно насущное практическое применение: они встречаются в различных задачах по теории вероятностей, и в задачах на классическое определение вероятности – особенно часто.
Решения и ответы:
Задача 2:Решение: найдём количество всех возможных перестановок 4-х карточек: Когда карточка с нулём располагается на 1-м месте, то число становится трёхзначным, поэтому данные комбинации следует исключить. Пусть ноль находится на 1-м месте, тогда оставшиеся 3 цифры в младших разрядах можно переставить способами.
Примечание: т.к. карточек немного, то здесь несложно перечислить все такие варианты: 0579 0597 0759 0795 0957 0975
Таким образом, из предложенного набора можно составить: 24 – 6 = 18 четырёхзначных чисел Ответ: 18
Задача 4:Решение: способами можно выбрать 3 карты из 36. Ответ: 7140
Задача 6:Решение: способами. Другой вариант решения: способами можно выбрать двух человек из группы и способами распределить должности в каждой выборке. Таким образом, старосту и его заместителя можно выбрать способами. Ответ: 506
Задача 9:Решение: способами может быть сдана десятка и туз («каждая десятка с каждым тузом»); способами может быть сдана пара тузов. Итого: выигрышные комбинации. Ответ: 22
Задача 11:Решение: 1) способами можно выбрать этаж для выхода всех пассажиров.
2) способами можно выбрать 2 этажа для выхода пассажиров (например, 6-ой и 11-й этаж). способами можно выбрать двух человек для выхода на одном этаже (третий выйдет на другом этаже). Например: Кроме того, любую пару и «одинокого человека» можно поменять этажами: Таким образом,для каждойпары этажей (55 уникальных сочетаний) возможно способов выхода пассажиров. По правилу умножения комбинаций: способами 2 пассажира могут выйти на одном этаже, а третий – на другом этаже.
3) способами пассажиры могут выйти на разных этажах. Второй вариант решения: способами можно выбрать 3 этажа для выхода и способами переставить пассажиров по каждойтройке этажей; следовательно, пассажиры могут выйти на разных этажах способами.
4)Способ первый: суммируем комбинации первых трёх пунктов: способом пассажиры могут выйти из лифта. Способ второй: в общем случае он более рационален, более того, позволяет обойтись без результатов предыдущих пунктов. Рассуждения таковы: способами может выйти 1-й пассажир из лифта и способами может выйти 2-й пассажир и способами может выйти 3-й пассажир. По правилу умножения комбинаций: способом могут выйти три человека
Ответ: 1) 11; 2) 330; 3) 990; 4) 1331
Задача 13:Решение: по формуле количества перестановок с повторениями: способами можно составить расписание занятий на неделю. Ответ: 105
Задача 15:Решение: используем формулу сочетаний с повторениями: способами можно выбрать 3 монеты из кошелька. Ответ: 20 Ответы на вопросы: 1) Да (т.к. количество извлекаемых монет (3 шт.) меньше видов монет (4 вида)); 2) Самый «дешёвый» набор содержит 3 рублёвые монеты, а самый «дорогой» – 3 десятирублёвые.
Задача 17:Решение: способами можно составить цифровую комбинацию автомобильного номера, при этом одну из них (000) следует исключить: . способами можно составить буквенную комбинацию автомобильного номера. По правилу умножения комбинаций, всего можно составить: автомобильных номера (каждаяцифровая комбинация сочетаетсяс каждойбуквенной комбинацией). Ответ: 1726272
|