Перестановки, сочетания и размещения без повторений Задачи по комбинаторике. Примеры решений
http://www.mathprofi.ru/zadachi_po_kombinatorike_primery_reshenij.html
Автор: Емелин Александр
Будут рассмотрены элементы комбинаторики, которые потребуются для дальнейшего изучения теории вероятностей.
Комбинаторика – самостоятельный раздел высшей математики
В узком смысле комбинаторика – это подсчёт различных комбинаций, которые можно составить из некоторого множества дискретных объектов. Под объектами понимаются какие-либо обособленные предметы или живые существа – люди, звери, грибы, растения, насекомые и т.д. При этом комбинаторику совершенно не волнует, что множество состоит из тарелки манной каши, паяльника и болотной лягушки. Принципиально важно, что эти объекты поддаются перечислению – их три (дискретность) и существенно то, что среди них нет одинаковых.
С множеством разобрались, теперь о комбинациях. Самыми распространёнными видами комбинаций являются перестановки объектов, их выборка из множества (сочетание) и распределение (размещение). Давайте прямо сейчас посмотрим, как это происходит:
Перестановки, сочетания и размещения без повторений
Начнём с хвоста заголовка – что значит «без повторений»? Это значит, что в данном параграфе будут рассматриваться множества, которые состоят из различныхобъектов. Например, … нет, кашу с паяльником и лягушкой предлагать не буду, лучше что-нибудь повкуснее =) Представьте, что перед вами на столе материализовалось яблоко, груша и банан (при наличии таковых ситуацию можно смоделировать и реально). Выкладываем фрукты слева направо в следующем порядке:
яблоко / груша / банан
Вопрос первый: сколькими способами их можно переставить?
Одна комбинация уже записана выше и с остальными проблем не возникает:
яблоко / банан / груша груша / яблоко / банан груша / банан / яблоко банан / яблоко / груша банан / груша / яблоко
Итого: 6 комбинаций или 6 перестановок.
Хорошо, здесь не составило особого труда перечислить все возможные случаи, но как быть, если предметов больше? Уже с четырьмя различными фруктами количество комбинаций значительно возрастёт!
Пожалуйста, откройте справочный материал Основные формулы комбинаторики(методичку удобно распечатать) и в пункте №2 найдите формулу количества перестановок.
Никаких мучений – 3 объекта можно переставить Р3=3!=6 способами.
Вопрос второй: сколькими способами можно выбрать а) один фрукт, б) два фрукта, в) три фрукта, г) хотя бы один фрукт?
Зачем выбирать? Так нагуляли же аппетит в предыдущем пункте – для того, чтобы съесть! =)
а) Один фрукт можно выбрать, очевидно, тремя способами – взять либо яблоко, либо грушу, либо банан. Формальный подсчёт проводится по формуле количества сочетаний:
Запись С13 в данном случае следует понимать так: «сколькими способами можно выбрать 1 фрукт из трёх?»
б) Перечислим все возможные сочетания двух фруктов:
яблоко и груша; яблоко и банан; груша и банан.
Количество комбинаций легко проверить по той же формуле:
Запись С23 понимается аналогично: «сколькими способами можно выбрать 2 фрукта из трёх?».
в) И, наконец, три фрукта можно выбрать единственным способом:
Кстати, формула количества сочетаний сохраняет смысл и для пустой выборки: способом можно выбрать ни одного фрукта – собственно, ничего не взять и всё.
г) Сколькими способами можно взять хотя бы одинфрукт? Условие «хотя бы один» подразумевает, что нас устраивает 1 фрукт (любой) или 2 любых фрукта или все 3 фрукта: способами можно выбрать хотя бы один фрукт.
Читатели, внимательно изучившие вводный урок по теории вероятностей, уже кое о чём догадались. Но о смысле знака «плюс» позже.
Для ответа на следующий вопрос мне требуется два добровольца… …Ну что же, раз никто не хочет, тогда буду вызывать к доске =)
Вопрос третий: сколькими способами можно раздать по одному фрукту Даше и Наташе?
Для того чтобы раздать два фрукта, сначала нужно их выбрать. Согласно пункту «бэ» предыдущего вопроса, сделать это можно способами, перепишу их заново:
яблоко и груша; яблоко и банан; груша и банан.
Но комбинаций сейчас будет в два раза больше. Рассмотрим, например, первую пару фруктов: яблоком можно угостить Дашу, а грушей – Наташу; либо наоборот – груша достанется Даше, а яблоко – Наташе.
И такая перестановка возможна для каждой пары фруктов.
В данном случае работает формула количества размещений
Она отличается от формулы тем, что учитывает не только количество способов, которым можно выбрать несколько объектов, но и все перестановки объектов в каждойвозможной выборке. Так, в рассмотренном примере, важно не только то, что можно просто выбрать, например, грушу и банан, но и то, как они будут распределены (размещены) между Дашей и Наташей.
В простейших случаях можно пересчитать все возможные комбинации вручную, но чаще всего это становится неподъемной задачей, именно поэтому и нужно понимать смысл формул.
Также напоминаю, что сейчас речь идёт о множестве с различнымиобъектами, и если яблоко/грушу/банан заменить на 3 яблока или даже на 3 очень похожих яблока, то в контексте рассмотренной задачи они всё равно будут считаться различными.
Остановимся на каждом виде комбинаций подробнее:
Перестановки
Перестановками называют комбинации, состоящие из одних и тех же nразличныхобъектов и отличающиеся только порядком их расположения. Количество всех возможных перестановок выражается формулой Pn=n!
Отличительной особенностью перестановок является то, что в каждой из них участвует ВСЁ множество, то есть, все n объектов. Например, дружная семья:
Задача 1
Сколькими способами можно рассадить 5 человек за столом?
Решение: используем формулу количества перестановок:
P5=5!=120
Ответ: 120 способами
Невероятно, но факт. Обратите внимание, что здесь не имеет значения круглый ли стол, квадратный, или вообще все люди сели встали, легли на скамейку вдоль одной стены – важно лишь количество объектов и их взаимное расположение. Помимо перестановок людей, часто встречается задача о перестановках различных книг на полке, но это было бы слишком просто даже для чайника:
Задача 2
Сколько четырёхзначных чисел можно составить из четырёх карточек с цифрами 0, 5, 7, 9?
Для того чтобы составить четырёхзначное число нужно задействовать все четыре карточки(цифры на которых различны!), и это очень важная предпосылка для применения формулы Очевидно, что, переставляя карточки, мы будем получать различные четырёхзначные числа, … стоп, а всё ли тут в порядке? ;-)
Хорошенько подумайте над задачей! Вообще, это характерная черта комбинаторных и вероятностных задач – в них НУЖНО ДУМАТЬ. И зачастую думать по-житейски, как, например, в разборе вступительного примера с фруктами.
Решение и ответ в конце урока.
Сочетания
В учебниках обычно даётся лаконичное и не очень понятное определение сочетаний, поэтому, в моих устах формулировка будет не особо рациональной, но, надеюсь, доходчивой:
Сочетаниями называют различные комбинации из объектов, которые выбраны из множества различных объектов, и которые отличаются друг от друга хотя бы одним объектом. Иными словами, отдельно взятое сочетание – это уникальная выборка из элементов, в которой не важен их порядок (расположение). Общее же количество таких уникальных сочетаний рассчитывается по формуле .
Задача 3
В ящике находится 15 деталей. Сколькими способами можно взять 4 детали?
Решение: прежде всего, снова обращаю внимание на то, что по логике условия, детали считаются различными– даже если они на самом деле однотипны и визуально одинаковы (в этом случае их можно, например, пронумеровать).
В задаче речь идёт о выборке из 4 деталей, в которой не имеет значения их «дальнейшая судьба» – грубо говоря, «просто выбрали 4 штуки и всё». Таким образом, у нас имеют место сочетания деталей. Считаем их количество:
Здесь, конечно же, не нужно ворочать огромные числа . В похожей ситуации я советую использовать следующий приём: в знаменателе выбираем наибольший факториал (в данном случае ) и сокращаем на него дробь. Для этого числитель следует представить в виде . Распишу очень подробно:
способами можно взять 4 детали из ящика.
Ещё раз: что это значит? Это значит, что из набора 15 различных деталей можно составитьодну тысячу триста шестьдесят пять уникальных сочетания 4 деталей. То есть, каждая такая комбинация из четырёх деталей будет отличаться от других комбинаций хотя бы одной деталью.
Ответ: 1365 способами
Формуле необходимо уделить самое пристальное внимание, поскольку она является «хитом» комбинаторики. При этом полезно понимать и без всяких вычислений записывать «крайние» значения: . Применительно к разобранной задаче:
– единственным способом можно взять ни одной детали; способами можно взять 1 деталь (любую из пятнадцати); способами можно взять 14 деталей (при этом какая-то одна из 15 останется в ящике); – единственным способом можно взять все пятнадцать деталей.
Рекомендую внимательно ознакомиться с биномом Ньютона и треугольнтком Паскаля, по которому, к слову, очень удобно выполнять проверку вычислений Cnm при небольших значениях «эн».
Задача 4
Сколькими способами из колоды в 36 карт можно выбрать 3 карты?
Это пример для самостоятельного решения. Чем приятны многие комбинаторные задачи, так это краткостью – главное, разобраться в сути. И суть, бывает, открывается с различных сторон. Разберём весьма поучительный пример:
Задача 4*
В шахматном турнире участвует человек и каждый с каждым играет по 1-й партии. Сколько всего партий сыграно в турнире?
Поскольку я сам играю в шахматы и неоднократно принимал участие в круговых турнирах, то сразу же сориентировался по турнирной таблице размером клеток, в которой результат каждой партии учитывается дважды и, кроме того, затушёвываются клетки «главной диагонали» (т.к. участники не играют сами с собой). Исходя из проведённых рассуждений, общее количество сыгранных партий рассчитывается по формуле .
Здесь можно руководствоваться самыми что ни на есть банальными сочетаниями: различных пар можно составить из соперников (кто играет белыми, кто чёрными – не важно).
Эквивалентной является задача о рукопожатиях: в отделе работает мужчин и каждый с каждым здоровается за руку, сколько рукопожатий они совершают? К слову, шахматисты тоже пожимают друг другу руку перед каждой партией.
Ну а вывода тут два: – во-первых, не всё очевидное – очевидно; – и во-вторых, не бойтесь решать задачи «нестандартно»!
Большое спасибо за ваши письма, они помогают улучшить качество учебных материалов!
Размещения
Или «продвинутые» сочетания. Размещениями называют различные комбинации из m объектов, которые выбраны из множества n различных объектов, и которые отличаются друг от друга как составом объектов в выборке, так и их порядком. Количество размещений рассчитывается по формуле
Что наша жизнь? Игра:
Задача 5
Боря, Дима и Володя сели играть в «очко». Сколькими способами им можно сдать по одной карте? (колода содержит 36 карт)
Решение: ситуация похожа на Задачу 4, но отличается тем, что здесь важно не только то, какие три карты будут извлечены из колоды, но и то, КАК они будут распределены между игроками. По формуле размещений:
способами можно раздать 3 карты игрокам.
Есть и другая схема решения, которая, с моей точки зрения, даже понятнее:
способами можно извлечь 3 карты из колоды.
Теперь давайте рассмотрим, какую-нибудь одну из семи тысяч ста сорока комбинаций, например: король пик, 9 червей , 7 червей. Выражаясь комбинаторной терминологией, эти 3 карты можно «переставить» между Борей, Димой и Володей P3=3!=6 способами:
КП, 9Ч, 7Ч; КП, 7Ч, 9Ч; 9Ч, КП, 7Ч; 9Ч, 7Ч, КП; 7Ч, КП, 9Ч; 7Ч, 9Ч, КП.
И аналогичный факт справедлив для любого уникального набора из трёх карт. А таких наборов, не забываем, мы насчитали C363=7140. Найденное количество сочетаний следует умножить на шесть:
способами можно сдать по одной карте трём игрокам.
По существу, получилась наглядная проверка формулы , окончательный смысл которой мы проясним в следующем параграфе.
Ответ: 42840
Возможно, у вас остался вопрос, а кто же раздавал карты? …Наверное, преподаватель =) И чтобы никому не было обидно, в следующей задаче примет участие вся студенческая группа:
Задача 6
В студенческой группе 23 человека. Сколькими способами можно выбрать старосту и его заместителя?
Задача о «размещении» должностей в коллективе встречается очень часто и является самым настоящим баяном. Краткое решение и ответ в конце урока.
|