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

Их можно переставить только двумя способами:

или

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

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

– Тогда существует 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 пуговицы разного цвета. Мы уже считали, что возможных перестановок для трех элементов равно шести.

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

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

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

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