Перестановки
Однажды в выходной день Маша решила навести порядок в своих игрушках и рассадить в ряд медвежонка, куклу и львёнка.
Вначале она рассадила их так:
Но ей не понравилось, что медвежонок сидит рядом со львёнком. Тогда Маша пересадила игрушки следующим образом:
Но и тут Маша не смогла определиться, кто должен сидеть справа от куклы – львёнок или медвежонок?
Так бы Маша и продолжала бы переставлять игрушки с места на место, если бы в комнату не вошел Машин папа.
– Ты чем это занимаешься? – поинтересовался он у Маши.
– Да вот, – грустно вздохнула Маша, – пытаюсь расставить игрушки, но у меня что-то не получается. Столько много разных вариантов, а мне ни один не нравится.
– Допустим, – не согласился папа, – что вариантов не так уж и много. У тебя три игрушки, значит, вариантов всего шесть.
– Как ты так быстро посчитал? – удивилась Маша.
– Есть такая наука, – пояснил папа, – комбинаторика. Она и занимается подсчетом различных вариантов перестановок. Допустим у тебя всего две игрушки – медвежонок и кукла. Их можно переставить только двумя способами:
или
Если у тебя три игрушки, то это можно сделать уже шестью способами:
– А если у меня четыре игрушки? – спросила Маша.
– Тогда существует 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 пуговицы разного цвета. Мы уже считали, что возможных перестановок для трех элементов равно шести.
Второй ряд, он будет у нас вспомогательным, мы составим следующим образом:
– То есть мы добавили пуговицы других цветов? – предположила Маша.
– Совершенно верно. В третьем ряду мы просто поменяем пуговицы местами. Вот так:
– А что мы будем делать с четвёртым рядом? – поинтересовалась Маша.
– А четвертого ряда не будет, – ответил папа. У нас три пуговицы, то есть три элемента множества, значит и рядов будет три. Осталось только, следуя сверху вниз, перечислить все варианты перестановок:
И совсем несложно. Главное быть внимательным.
– Как интересно! – воскликнула Маша. – А если у меня все-таки есть одинаковые игрушки, то количество перестановок считается точно также?
– Не совсем, – пояснил папа. – Если некоторые элементы множества повторяются, то такие перестановки называются перестановками с повторением.