Перестановки, сочетания и размещения без повторений

Задачи по комбинаторике. Примеры решений

Автор: Емелин Александр

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! = 6 способами.

Вопрос второй: сколькими способами можно выбрать а) один фрукт, б) два фрукта, в) три фрукта, г) хотя бы один фрукт?

а) Один фрукт можно выбрать, очевидно, тремя способами – взять либо яблоко, либо грушу, либо банан. Формальный подсчёт проводится по формуле количества сочетаний:

Запись в данном случае следует понимать так: «число способов, которыми можно выбрать один фрукт из трёх»

б) Перечислим все возможные сочетания двух фруктов:

яблоко и груша;
яблоко и банан;
груша и банан.

Количество комбинаций легко проверить по той же формуле:
Запись понимается аналогично: «число способов, которыми можно выбрать два фрукта из трёх»

в) И, наконец, три фрукта можно выбрать единственным способом:

Кстати, формула количества сочетаний сохраняет смысл и для пустой выборки: способом можно выбрать ни одного фрукта – собственно, ничего не взять и всё.

г) Сколькими способами можно взять хотя бы один фрукт? Условие «хотя бы один» подразумевает, что нас устраивает 1 фрукт (любой) или 2 любых фрукта или все 3 фрукта:

+ + = 3 + 3 + 1 = 7 способами можно выбрать хотя бы один фрукт.

Читатели, внимательно изучившие вводный урок по теории вероятностей, уже кое о чём догадались. Но о смысле знака «плюс» позже.

Вопрос третий: сколькими способами можно раздать по одному фрукту Даше и Наташе?

Для того чтобы раздать два фрукта, сначала нужно их выбрать. Согласно пункту «бэ» предыдущего вопроса, сделать это можно способами, перепишу их заново:

яблоко и груша;
яблоко и банан;
груша и банан.

Но комбинаций сейчас будет в два раза больше. Рассмотрим, например, первую пару фруктов:
яблоком можно угостить Дашу, а грушей – Наташу;
либо наоборот – груша достанется Даше, а яблоко – Наташе.

И такая перестановка возможна для каждой пары фруктов.

В данном случае работает формула количества размещений:
Она отличается от формулы тем, что учитывает не только количество способов, которым можно выбрать несколько объектов, но и все перестановки объектов в каждой возможной выборке. Так, в рассмотренном примере, важно не только то, что можно просто выбрать, например, грушу и банан, но и то, как они будут распределены (размещены) между Дашей и Наташей.

Пожалуйста, внимательно прочитайте пункт №2 методички Основные формулы комбинаторики и постарайтесь хорошо уяснить разницу между перестановками, сочетаниями и размещениями. В простейших случаях можно пересчитать все возможные комбинации вручную, но чаще всего это становится неподъемной задачей, именно поэтому и нужно понимать смысл формул.

Остановимся на каждом виде комбинаций подробнее:

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

Перестановками называют комбинации, состоящие из одних и тех же n различных объектов и отличающиеся только порядком их расположения. Количество всех возможных перестановок выражается формулой Р_n = n!.

Отличительной особенностью перестановок является то, что в каждой из них участвуетВСЁ множество, то есть, всеn объектов.

Задача 1

Сколькими способами можно рассадить 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! = 6 способами:

КП, 9Ч, 7Ч;
КП, 7Ч, 9Ч;
9Ч, КП, 7Ч;
9Ч, 7Ч, КП;
7Ч, КП, 9Ч;
7Ч, 9Ч, КП.

Такое количество перестановок имеется для любого уникального набора из 3-х карт. А таких наборов, не забываем, мы насчитали . Не нужно быть профессором, чтобы понять, что найденное количество сочетаний следует умножить на шесть и тогда мы получим количество всех способов раздачи по одной карте трем игрокам. Итак: способами можно сдать по одной карте 3-м игрокам. Этот результат равен тому, который получили, решая задачу по формуле размещения.

По существу, получилась наглядная проверка формулы . Конкретный смысл этой формуле более подробно рассмотрен в конце решения задачи 8.

Ответ: 42840 способов.

Задача 6

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

Задача о «размещении» должностей в коллективе встречается очень часто. Краткое решение и ответ в конце урока.