Школьнику: Комбинаторика - размещения, перестановки, сочетания

 Основные понятия

• Размещением из n элементов по k называется упорядоченный набор из k различных элементов некоторого n-элементного множества.
  Пример задачи: Сколько трехзначных чисел можно создать из цифр от 1 до 5?
  Комментарий: В данном случае n=5 (мы можем использовать пять вариантов элементов - числа 1...5), а k=3 (три позиции для размещения элементов, так как число трехзначное).
• Перестановкой из n элементов (например чисел 1, 2, … n) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n.
  Пример задачи: Сколькими способами можно создать числа, переставляя цифры в числе 12345?
  Комментарий: В данном случае n=5 (пять вариантов элементов - числа 1...5).
• Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.
  
  Пример задачи: В вазе есть тюльпаны пяти цветов: белые, желтые, оранжевые, красные и розовые. Сколькими способами можно создать букет из трех тюльпанов, если в букете должно быть по одному цветку каждого цвета?
  Комментарий: Очевидно, что данный вариант размещения элементов отличается от примера с размещением цифр в числе, так как цветы в букете не имеют своего номера (позиции) и совершенно неважно, в каком порядке мы добавляем в него цветы. В данном случае n=5 (пять вариантов цветов тюльпанов), а k=3 (букет нужно собрать из трех тюльпанов).

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

Обычно начинают объяснять с размещений, но я сознательно хочу начать с перестановок, так как на их примере проще понять логику вычисления.

Итак, вернемся к задаче из примера: Сколькими способами можно создать числа, переставляя цифры в числе 12345?

У нас есть пять цифр (пусть это будет пять кубиков с цифрами): 1,2,3,4,5.

У нас есть пять, пока еще свободных, позиций под их размещение (пусть это будут пустые коробочки): ▢▢▢▢▢.

Начинаем постепенно заполнять эти позиции: на первую позицию (в первую коробочку) мы можем поместить одну из пяти цифр (один из пяти кубиков). То есть у нас есть пять вариантов заполнения первой позиции.

Предположим, мы взяли кубик с номером 4.

Теперь у нас осталось четыре цифры (кубика): 1,2,3,5.

Позиций (коробочек) у нас осталось пять, но первая уже заполнена, то есть свободных позиций четыре: 4▢▢▢▢.

На размещение во второй коробочке у нас осталось 4 "претендента". Мы взяли кубик с номером 4. Но если бы мы взяли любой из других кубиков, у нас все равно было бы 4 варианта заполнения второй коробочки (просто мы выбирали бы из другого набора ставшихся кубиков), то есть на каждый вариант заполнения первой коробочки у нас приходится по четыре варианта заполнения второй.

Значит у нас есть 5⋅ 4 = 20 - двадцать вариантов заполнения первых двух позиций (коробочек).

Предположим, мы взяли кубик с номером 1.

У нас осталось три цифры (кубика): 2,3,5.

Позиций (коробочек) у нас осталось пять, но первые две уже заполнены: 41▢▢▢.

Продолжая по аналогии, мы получим, что у нас есть 5⋅ 4⋅ 3 = 60 - шестьдесят вариантов заполнения первых трех позиций (коробочек).

Заполнить первые четыре позиции мы можем 5⋅ 4⋅ 3⋅ 2 = 120 способами, а все пять - 5⋅ 4⋅ 3⋅ 2⋅ 1 = 120 - тоже ста двадцатью способами.

Почему последние два числа совпадают? Все просто: на последнем этапе у нас остается всего один кубик, но и одна пустая коробочка. То есть у нас уже нет вариантов размещения. Поэтому последний шаг уже не оказывает влияния на число перестановок.

Нетрудно догадаться, что сколько бы элементов (цифр, чисел, воздушных шариков и так далее) нам ни дали, мы можем узнать число из перестановок умножая последовательно число элементов на все целые числа меньше него.

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

6! = 6⋅ 5⋅ 4⋅ 3⋅ 2⋅ 1

3! = 3⋅ 2⋅ 1

Обозначается число перестановок из n так:

В итоге мы получаем следующую формулу для вычисления количества перестановок для n элементов:

Размещения

Размещение очень похоже на перестановку, с одной лишь разницей: у нас обычно "не хватает" позиций (коробочек) для размещения всех элементов (кубиков).

Обозначается размещение n из k так:

При k = n (то есть когда число "коробочек" равно числу "кубиков") количество размещений равно количеству перестановок порядка n.

Возьмем задачу из примера: Сколько трехзначных чисел можно создать из цифр от 1 до 5?

Если мы по аналогии с перестановками попробуем по шагам считать, то увидим, что мы остановились после заполения третьей (последней) "коробочки":

5⋅ 4⋅ 3 = 60

А множители 2 и 1 отсуствуют: 5⋅ 4⋅ 3⋅ 2⋅ 1. То есть, число в 2! раз меньше.

Мы можем записать так: 

а в общем виде так:

Размещение с повторением

Существует вариант, когда мы можем повторно использовать один и тот же элемент, независимо от того, использовали мы его до этого, или нет. В случае с кубиками и коробочками это будет выглядеть так: у нас есть не по одному кубику с каждым номером, а неограниченное число кубиков с каждым из чисел. Это называется размещение n из k с повторением и обозначается:

Начнем заполнять "коробочки".

У нас есть пять кубиков с цифрами: 1,2,3,4,5.

У нас есть пять, пока еще свободных, позиций под их размещение (пусть это будут пустые коробочки): ▢▢▢▢▢.

Положим, в первую мы кладем номер 4.

Значит у нас осталось четыре свободных "коробочки": 4▢▢▢▢.

Начинаем заполнять вторую коробочку. Их у нас четыре, как я уже сказал. Но кубиков у нас, в отличии от размещения без повторения осталось всё равно пять. Значит у нас на каждый вариант заполения первой коробочки приходится пять вариантов заполения второй.

Соотвественно две первые коробочки мы можем заполнить 5⋅ 5 = 25 способами (а не 5⋅ 4 = 20, как в случае без повторения).

Повторяя рассуждения мы вычислим, что три коробочки мы можем заполнить 5⋅ 5⋅ 5 = 125 способами.

В общем случае число размещений равно числу элементов (кубиков) в степени числа возможных позиций для размещения (коробочек).

Сочетания

Сочетания похожи на размещения, однако для сочетаний совершенно не важно, в каком порядке расположены коробочки. Обозначаются сочетания так:

Как нам вывести формулу для сочетаний? Для начала возьмем число размещений и разделим на число всех вариантов "перемешивания" каждого набора (ведь при "перемешивании" получается тот же набор, просто расположенный в другом порядке). Но чему равно число этих "перемешиваний", спросите вы? А если не спросите, то значит я не зря писал эту статью, потому что внимательный читатель сам заметит, что в данном случае речь идет о перестановках. Обратите внимание, что тут мы переставляем не кубики, а коробочки, которых k штук, поэтому речь идет не о P_n, а о P_k. В итоге мы получаем формулу:

А теперь вернемся к задаче из примера: В вазе есть тюльпаны пяти цветов: белые, желтые, оранжевые, красные и розовые. Сколькими способами можно создать букет из трех тюльпанов, если в букете должно быть по одному цветку каждого цвета?

Сочетания с повторениями

Я думаю, вы уже догадались, что такое сочетания с повторениями. Это сочетания, при которых можно использовать элементы повторно. Обозначается сочетание с повторением так:

Чтобы вывести общую формулу сделаем такой "фокус": представим, что у нас есть n пронумерованных кубиков и еще k-1 - не пронумерованных (нам по сути уже неважно, в каком порядке лягут кубики в коробки и какие номера на них будут). Вычитаем единичку мы потому, что в одну коробочку у нас гарантированно ляжет кубик из основного набора. И теперь вычислим сочетание из этого набора:

А теперь задание для особо внимательных: могли ли мы совершить такой же "фокус" в случае с размещением с перестановками? Если могли, то почему не сделали? А если не могли, то почему? Жду ответов в комментариях.

Ну и пара примеров задач.

Есть гвоздики двух цветов. Нужно собрать букеты из трех цветков так, чтобы у каждого был уникальный набор. Скольким букетов можно собрать?

Есть гвоздики четырех цветов. Нужно собрать букеты из трех цветков так, чтобы у каждого был уникальный набор. Скольким букетов можно собрать?

Сколько решений в неотрицательных числах имеет уравнение x+y+z=6?x+y+z+q=8?

Проведем аналогию с кубиками и коробочками. Можно преобразовать эту задачу к виду "Нужно разместить шесть кубиков в трех коробочках". И решение: