Дмитрий Кудрец - Занимательная комбинаторика

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

– Да. Пусть множество состоит из n 1элементов одного вида, n 2элементов другого вида и т. д. Всего элементов n 1+ n 2+…+ n k= n . Тогда число перестановок с повторением равно.

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

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

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

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

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

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

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