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

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

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

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

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

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

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

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

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

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

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

– Да. Пусть множество состоит из n

элементов одного вида, n

элементов другого вида и т. д. Всего элементов n

+n

+…+n

=n. Тогда число перестановок с повторением равно.

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

– Нисколько, – возразил папа. – И ты сама сейчас в этом убедишься. Пусть у нас есть карандаши. Два красных, один зеленый и один синий.

=2, n

=1, n

=1. Всего карандашей n

+n

+n

=2+1+1=4. Следовательно, число перестановок с повторением равно.

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

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

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

– Давай посмотрим, – папа разложил на столе карточки.

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

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

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

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

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

– Конечно.