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

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

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

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

— Пусть у тебя есть два одинаковых медвежонка.

— Но у меня нет двух одинаковых медвежонка, — возразила Маша.

— Хорошо, — согласился папа. — Тогда возьмем два зеленых карандаша и один красный.

Карандашей всего 3, значит, число перестановок равно 6. Но нет разницы, если поменять зеленые карандаши местами. Мы получим тот же самый вариант. Поэтому число перестановок с повторением будет всего 3:

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

— Да. Пусть множество состоит из n₁ элементов одного вида, n₂ элементов другого вида и т. д. Всего элементов n₁+n₂+…+n_k=n. Тогда число перестановок с повторением равно.

— Какая сложная формула! — воскликнула Маша.

— Нисколько, — возразил папа. — И ты сама сейчас в этом убедишься. Пусть у нас есть карандаши. Два красных, один зеленый и один синий. То есть n₁=2, n₂=1, n₃=1. Всего карандашей n₁+n₂+n₃=2+1+1=4. Следовательно, число перестановок с повторением равно.

— Хорошо, — согласилась Маша. — А если у меня есть карточки с буквами из которых составляют слова? Буквы же в словах могут повторяться.

— И сколько ты хочешь взять карточек?

— Сейчас, — Маша открыла ящик стола и вытащила наружу карточки с буками. — Вот. Это у меня ещё с первого класса осталось.

— Давай посмотрим, — папа разложил на столе карточки. — У нас есть три буквы А, две буквы У и две буквы М.

— Всего семь, — подсказала Маша.

— Воспользуемся формулой для перестановок с повторением.. Значит, существует 210 вариантов перестановок.

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

— Так много, — подтвердил папа. — А если у нас есть имеются другие наборы элементов, то и число перестановок будет другим.

— А можно я теперь попробую сама?

— Конечно. А что мы будем считать?

— У меня есть цветные скрепки.

Три зеленых, три синих, три желтых и две красных. Всего 11 скрепок. Значит, число перестановок будет равно.

Вот так число! Это сколько же времени уйдет на то, чтобы переложить все скрепки?

— Перекладывать скрепки мы не будем, — возразил папа. — А ты мы на это дело потратим все выходные. А тебе еще уроки учить нужно. Да и у меня есть дела.

— Ну, папа! — заныла Маша. — Давай еще что-нибудь посчитаем!

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

Конец ознакомительного фрагмента.