Занимательная комбинаторика

Дмитрий Кудрец

В книге популярно и доступно изложены основные сведения комбинаторики. Приводятся примеры решения задач на подсчет количества перестановок, размещений и сочетаний.Рекомендуется для учащихся и учителей школ, гимназий, а также для широкого круга читателей.

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

Однажды в выходной день Маша решила навести порядок в своих игрушках и рассадить в ряд медвежонка, куклу и львёнка.

Вначале она рассадила их так:

Но ей не понравилось, что медвежонок сидит рядом со львёнком. Тогда Маша пересадила игрушки следующим образом:

Но и тут Маша не смогла определиться, кто должен сидеть справа от куклы — львёнок или медвежонок?

Так бы Маша и продолжала бы переставлять игрушки с места на место, если бы в комнату не вошел Машин папа.

— Ты чем это занимаешься? — поинтересовался он у Маши.

— Да вот, — грустно вздохнула Маша, — пытаюсь расставить игрушки, но у меня что-то не получается. Столько много разных вариантов, а мне ни один не нравится.

— Допустим, — не согласился папа, — что вариантов не так уж и много. У тебя три игрушки, значит, вариантов всего шесть.

— Как ты так быстро посчитал? — удивилась Маша.

— Есть такая наука, — пояснил папа, — комбинаторика. Она и занимается подсчетом различных вариантов перестановок. Допустим у тебя всего две игрушки — медвежонок и кукла. Их можно переставить только двумя способами:

или

Если у тебя три игрушки, то это можно сделать уже шестью способами:

— А если у меня четыре игрушки? — спросила Маша.

— Тогда существует 24 варианта различных способов их перестановки. В комбинаторике такие упорядочения множества, состоящего из определенного количества элементов, так и называют — перестановками. Особенностью перестановок является то, что в них должны участвовать все элементы данного множества.

Количество всех возможных перестановок можно найти по формуле, где n — количество элементов данного множества.

Символ n! называется факториалом и обозначает произведение всех целых чисел от 1 до n.

.

Например, 3!=1∙2∙3=6. 4!=1∙2∙3∙4=24.

При вычислении факториала принято считать, что 0!=1, 1!=1.

— А если у меня пять игрушек? — не унималась Маша.

— В таком случае у тебя 1∙2∙3∙4∙5=120 вариантов перестановок.

— Так много? — удивилась Маша.

— А если множество состоит из 6 элементов, — продолжал папа, — то число перестановок будет равняться 720. Для 7 элементов число перестановок будет равно 5040, для 8 — 40320 и так далее. Чем больше число элементов, тем больше число перестановок.

— А если вместо пяти игрушек взять пять конфет? — спросила Маша. — Число перестановок изменится?

— Если конфеты все различные, то, как и в случае с игрушками число перестановок все равно будет 120.

— То есть, — заключила Маша, — число перестановок не зависит от того, что я переставляю — игрушки, конфеты или еще что-нибудь?

— Совершенно верно! — подтвердил папа. — Главное, чтобы в перестановках участвовали все элементы множества, и элементы должны быть различными.

— Посчитать число перестановок несложно, — согласилась Маша, — а вот переставить игрушки и не запутаться при этом гораздо сложнее.

— Для того чтобы не запутаться, — успокоил Машу папа, — можно использовать дерево возможных вариантов. Одолжим на время у мамы пуговицы.

В первый ряд положим 3 пуговицы разного цвета. Мы уже считали, что возможных перестановок для трех элементов равно шести.

Второй ряд, он будет у нас вспомогательным, мы составим следующим образом:

— То есть мы добавили пуговицы других цветов? — предположила Маша.

— Совершенно верно. В третьем ряду мы просто поменяем пуговицы местами. Вот так:

— А что мы будем делать с четвёртым рядом? — поинтересовалась Маша.

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

И совсем несложно. Главное быть внимательным.

— Как интересно! — воскликнула Маша. — А если у меня все-таки есть одинаковые игрушки, то количество перестановок считается точно также?

— Не совсем, — пояснил папа. — Если некоторые элементы множества повторяются, то такие перестановки называются перестановками с повторением.