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