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

Научимся грамотно менять элементы местами и с этими знаниями откроем тайну Сатурна, расшифруем секретные послания ученых и разгадаем загадки Галилея.

В кругу семьи

В большом доме проживает семья из 6 человек. Днем все они собираются в гостиной на обед. Кушать стоя не хочет никто, поэтому нужно обязательно рассадить всех членов семьи за стол. Сколькими способами это можно сделать?

Итак, имеем 6 стульев и 6 человек, каждого из которых обязательно надо посадить. Первого человека можно посадить 6 способами — на любой из 6 стульев. Вне зависимости от того, куда посадили первого человека, второго можно посадить 5 способами и так далее. По правилу умножения находим все способы рассадить членов семьи:

6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 6! = 720

Можно пойти другим путем. В сущности, здесь мы размещаем людей по стульям, поэтому задачу можно решить с помощью размещений. Количество таких размещений без повторений из 6 человек по 6 стульям можно посчитать по формуле:

A_6^6 = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 6! = 720

Обратите внимание, что по условию задачи мы должны рассадить всех членов семьи за стол, то есть задействовать все элементы при составлении комбинаций. Такой тип задач часто встречается в комбинаторике.

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

В комбинаторике часто приходится работать с комбинациями, для составления которых надо в разном порядке расставить все имеющиеся элементы. Как и в случае с размещениями, такие комбинации математики выделили в отдельную группу и дали им отдельное название:

Перестановка из n элементов — упорядоченная комбинация размером n, составленная с использованием элементов всех n видов.

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

Все перестановки из цифр 1 и 3:

(1, 3) \qquad (3, 1)

Все перестановки из букв a, b и c:

(a,b,c) \quad (b,a,c) \quad (c,a,b) \\ (a,c,b) \quad (b,c,a) \quad (c,b,a)

Почему такие комбинации назвали «перестановками»? Потому что в них всегда используются все n элементов, а отличаются эти комбинации друг от друга только положением элементов. Можно менять их местами, переставлять и получать новые перестановки:

Все 6 перестановок трех букв

Составляя любую перестановку, мы расставляем n элементов по n вакантным местам. Причем каждый элемент используется только один раз. В этом смысле перестановку можно рассматривать как размещение без повторений.

Перестановки — частный случай размещений без повторений из n элементов по n вакантным местам ( $A_n^n$ ), то есть когда размещении задействованы все имеющиеся элементы!

Количество всех возможных перестановок из n элементов записывают как $P_n$ . Буква P обозначает английское слово permutation — «перестановка». Выведем формулу для подсчета количества всех перестановок:

Число перестановок

P_n = n!

Через размещения

Так как перестановки являются лишь частным случаем размещений без повторений, то для подсчета их количества будут работать соответствующие формулы, например факториальная:

P_n = A^n_n = \frac{n!}{(n-n)!} = \frac{n!}{0!} = \frac{n!}{1} = n!

$\blacksquare$

Если вас смущает, что факториал нуля вдруг оказался равен 1, этот вопрос подробно и понятно рассматривался в теме про факториалы. Обязательно ознакомьтесь!

Через правило умножения

Можно доказать формулу и по старинке. Есть n вакантных мест. На первое место можно поставить любой из n элементов. Вне зависимости от сделанного выбора, на второе место можно поставить $n-1$ элементов и так далее. Значит, мы можем применить правило умножения:

P_n = n \cdot (n-1) \cdot \ldots \cdot 2 \cdot 1 = n!

$\blacksquare$

На передовой науки

В научной конференции принимают участие 9 ученых. Они по порядку выступают со своими докладами. Сколькими способами организатор конференции может составить расписание этих докладов?

Решение

Выступить должен каждый ученый, значит в каждом варианте расписания (комбинация) участвуют все элементы (ученые). Сами же расписания отличаются только порядком докладов. Значит, каждое расписание по сути своей есть перестановка. Найдем их количество с помощью выведенной формулы:

P_9 = A_9^9 = 9! = 362 \ 880

Числовой мастер

Сколько различных семизначных чисел можно составить, используя все цифры следующего числа:

4 \ 309 \ 125

Решение

Имеем 7 цифр в распоряжении, все из которых придется использовать, чтобы составлять семизначные числа. Каждое такое число по сути есть перестановка 7 цифр. Найдем их количество с помощью выведенной формулы:

P_7 = 7! = 5040

Но есть нюанс. Если число начинается с 0, то оно уже не семизначное, а шестизначное. Например:

0 \ \boxed{ 349 \ 125 } \qquad 0 \ \boxed{ 125 \ 394 }

Найдем количество шестизначных чисел, которые можно составить из данных цифр. Для этого убираем из рассмотрения 0, так как он уже по умолчанию стоит в начале числа и находим перестановки из оставшихся 6 цифр:

P_6 = 6! = 720

Теперь из всех найденных «семизначных» чисел вычтем шестизначные, начинающиеся с цифры 0:

P_7 - P_6 = 5040 - 720 = 4320

Итак, из числа $4 \ 309 \ 125$ можно составить 4320 семизначных числа, включая само это число.

Перестановки по методу Юрия

— Число перестановок из трех элементов равно 3! = 6.

— А по-человечески можешь объяснить?

— Юрий будет дуть, Дуть будет Юрий, Будет Юрий дуть, Дуть Юрий будет, Юрий дуть будет, Будет дуть Юрий.

Первое слово в жизни

«Мама» — первое слово, которое мы учимся выговаривать... наверное. Оно состоит из 4 букв. А сколько вообще слов можно составить из этих букв? «Элементарно», скажете вы. Имеем 4 элемента, все из которых надо задействовать. Звучит как работа для перестановок, значит можно составить $P_4 = 4! = 24$ слов!

Этот ответ мог бы быть верным, если бы не один важный нюанс. До этого в размещениях и перестановках все элементы у нас отличались друг от друга, поэтому и комбинации из них по умолчанию были уникальными.

Но в этом примере одинаковые буквы «м» и «а» повторяются дважды, хотя в математическом смысле это по-прежнему уникальные элементы: $м_1, м_2, а_1, а_2$ . Из-за этого одно и то же слово «мама» среди наших 24 перестановок встретится целых 4 раза:

м_1 \ а_1 \ м_2 \ а_2 \quad м_1 \ а_2 \ м_2 \ а_1 \quad м_2 \ а_1 \ м_1 \ а_2 \quad м_2 \ а_2 \ м_1 \ а_1

Как так получилось? В слове «мама» есть 2 вакантных места для буквы «м». По этим двум вакантным местам мы можем расставить элементы $м_1$ и $м_2$ . Сделать это можно $P_2 = 2!$ способами: $м_1$ , потом $м_2$ и наборот, сначала $м_2$ , потом $м_1$ . Точно также есть 2! способов расставить элементы $а_1$ и $а_2$ на место букв «а».

Расстановка букв «м» никак не влияет на расстановку букв «а», поэтому, по правилу произведения есть всего $2! \cdot 2! = 4$ способа составить слово «мама», в чем мы уже выше убедились.

Точно такие же рассуждения можно провести и для других уникальных слов: «маам», «ммаа» и так далее. И каждое из этих уникальных слов или шаблонов в 24 перестановках будет представлено $2!\cdot 2! = 4$ одинаковыми словами:

\def\arraystretch{1.5} \begin{array}{c|c|c|c|c|c} \textbf{мама} & \textbf{маам} & \textbf{ммаа} & \textbf{аамм} & \textbf{амма} & \textbf{амам} \\ \hline м_1 \ а_1 \ м_2 \ а_2 & м_1 \ а_1 \ а_2 \ м_2 & \ldots & \ldots & \ldots & \ldots \\ м_1 \ а_2 \ м_2 \ а_1 & м_1 \ а_2 \ а_1 \ м_2 \\ м_2 \ а_1 \ м_1 \ а_2 & м_2 \ а_1 \ а_2 \ м_1 \\ м_2 \ а_2 \ м_1 \ а_1 & м_2 \ а_1 \ а_2 \ м_1 \\[3px] \hline 2! \cdot 2! = 4 & 4 & 4 & 4 & 4 & 4 \end{array}

В итоге мы вручную нашли все 6 уникальных перестановок или шаблонов (верхняя строка таблицы), каждый из которых представлен в виде 4 одинаковых перестановок.

Для того, чтобы математически получить эти 6 уникальных перестановок, надо поделить все перестановки (4!) на количество дубликатов, образующих каждый шаблон ( $2! \cdot 2!$ ):

\frac{4!}{2! \ 2!} = \frac{24}{4} = 6

Из этого примера становится понятно, что обычная формула перестановок не всегда работает. Чтобы вручную не считать все эти шаблоны и прочее, нужно придумать формулу и для таких задач.

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

Порой среди исходных элементов встречаются дубликаты, то есть некоторые элементы повторяются. В этом случае формула обычных перестановок перестает давать правильные ответы, ведь она повторяющиеся элементы считает уникальными. Поэтому вместно нее надо использовать модифицированную формулу:

Число перестановок с повторениями

Пускай n элементов разбиты на k групп дубликатов: в первой группе $n_1$ одинаковых элементов, во второй $n_2$ одинаковых элементов, ..., в k-той $n_k$ одинаковых элементов.

Количество уникальных перестановок из этих элементов рассчитывается по формуле:

P(n_1, \ n_2, \ \ldots, \ n_k) = \frac{n!}{n_1! \ n_2! \ \ldots \ n_k!}

Доказательство

В этом доказательстве мы обобщим уже рассмотренный пример. Обязательно изучите его и убедитесь, что во всем разобрались!

Из имеющихся элементов можно составить $n!$ перестановок. Среди них каждая уникальная перестановка будет представлена в виде кучи дубликатов, которые друг от друга отличаются только положением одинаковых элементов из своей группы.

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

Возьмем какую-нибудь уникальную перестановку (шаблон), например такую, в которой элементы из своих групп стоят рядом друг с другом.

\underbrace{aa \ldots a}_{\small n_1} \ \ \underbrace{bb \ldots b}_{\small n_2} \ \ldots \ \underbrace{cc \ldots c}_{\small n_k}

Элементы первой группы можно свободно менять местами друг с другом $n_1!$ способами. Так как элементы этой группы одинаковые, то такие «новые» перестановки шаблон никак не меняют. По такой же логике между собой можно менять местами элементы второй группы $n_2!$ способами, да хоть k-ой группы $n_k!$ способами, и от этих перестановок сам шаблон останется точно таким же.

Итак, одинаковые элементы первой группы можно расставить $n_1!$ способами. Вне зависимости от выбранной расстановки элементов первой группы, одинаковые элементы второй группы можно расставить $n_2!$ способами и так далее. По правилу умножения находим все способы составить шаблон:

n_1! \cdot n_2! \cdot \ldots \cdot n_k!

Можно рассмотреть какой-нибудь другой шаблон, например, когда элементы первых двух групп идут попарно:

ab \ ab \ldots ab \ \ldots \ cc\ldots c

Все те же рассуждения можно применить и к нему, а значит его тоже можно составить $n_1! \cdot \ldots \cdot n_k!$ способами. Да и вообще, любой шаблон можно составить этим одинаковым количеством способов.

Получается, что среди всех $n!$ перестановок каждое уникальное расположение элементов (шаблон) всегда представлено в виде $n_1!\cdot\ldots\cdot n_k!$ одинаковых перестановок.

Если мы поделим число всех перестановок на количество одинаковых перестановок, образующих шаблон, мы получим общее число шаблонов, то есть общее число уникальных перестановок:

P(n_1, \ n_2, \ \ldots, \ n_k) = \frac{n!}{n_1! \ n_2! \ \ldots \ n_k!}

$\blacksquare$

Математика всему голова!

Сколько различных слов можно составить из букв слова «математика»?

Решение

Разделим все буквы в слове «математика» на группы одинаковых букв:

Три буквы «а»
По две буквы «м» и «т»
Все остальные буквы в единственном экземпляре

Найдем количество перестановок с повторениями по выведенной формуле:

P(3,\ 2,\ 2,\ 1,\ 1,\ 1) = \frac{10!}{3! \ 2! \ 2! \ 1! \ 1! \ 1!} = 151 \ 200

Числовой грандмастер

Сколько различных семизначных чисел можно составить, используя все цифры следующего числа:

4 \ 405 \ 557

Решение

Ход решения точно такой же, как и в примере «Числовой мастер», только в этот раз у нас элементы (цифры) повторяются, поэтому нужно использовать формулу перестановок с повторениями. Все уникальные перестановки 7 цифр:

P(2, \ 1, \ 3, \ 1) = \frac{7!}{2! \ 1! \ 3! \ 1!} = \frac{5040}{12} = 420

Среди этих 420 перестановок есть как искомые семизначные числа, так шестизначные, начинающиеся с цифры 0. Найдем все такие шестизначные числа, уберя из рассмотрения цифру 0:

P(2, \ 3, \ 1) = \frac{6!}{2! \ 3! \ 1!} = 60

Осталось только вычесть из уникальных перестановок 7 цифр все шестизначные числа, и мы найдем количество семизначных цифр:

P(2, \ 1, \ 3, \ 1) - P(2, \ 3, \ 1) = 420 - 60 = 360

Формула перестановок с повторениями является обобщением обычной формулы перестановок и логичным образом к ней сводится. Например, если у нас есть n элементов и все они уникальные, то есть представлены в единственном экземпляре, то получается следующее:

P(1, \ 1, \ \ldots, \ 1) = \frac{n!}{1! \ 1! \ \ldots \ 1!} = n! = P_n

Не путайте «размещения с повторениями» и «перестановки с повторениями»!

В размещениях с повторениями мы можем неограниченное количество раз использовать один и тот же элемент.

В перестановках с повторениями каждый элемент ипользуется только один раз, но среди самих элементов могут быть дубликаты в разных количествах!

За рубежом

Если помните, в теме про размещения говорилось, что в англоязычной литературе само понятие «размещение» и обозначение A не используют. Размещения и перестановки там объединили в одно понятие, которое и назвали «перестановкой».

У «нас» две сущности: размещения ( $A_n^k$ ) и перестановки ( $P_n$ ), как частный случай размещений.

У «них» одна сущность — перестановки, которые выполняют роль как размещений ( $P_{n,k}$ ), так и перестановок ( $P_n$ ) в нашем понимании.

Анаграммы

Из слова «кот» перестановкой букв можно составить слово «ток». А из слова «кабан» таким же образом можно получить слово «банка». Примеров множество: «куб» — «бук», «верность» — «ревность», «владение» — «давление» и прочие.

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

Анаграммы Дмитрия Авалиани

Анаграммные фразы, придуманные советским поэтом и палиндромистом Дмитрием Авалиани:

«Вижу зверей — живу резвей.»

«Слепо топчут — после почтут.»

Есть у него и полностью анаграммический стих:

«Аз есмь строка, живу я, мерой остр.
  За семь морей ростка я вижу рост.
  Я в мире — сирота.
  Я в Риме — Ариост.»

Анаграммы могут состоять из любых знаков, а не только букв. Например, числа $12 \ 392$ , $91 \ 223$ и $23 \ 912$ являются числовыми анаграммами.

Любая анаграмма в математическом смысле является перестановкой знаков, возможно, с повторениями. Используя уже выведенные формулы, количество анаграмм можно легко посчитать. Так, слово «строка» имеет $P_6 = 6! = 720$ анаграмм, из которых целых 19 это реально существующие слова:

Астрок, карост, кастор, корста, костра, красот, острак, ракост, расток, роскат, ростка, Сократ, старок, сторка, строка, торакс, трасок, трокса, тросак.

Анонсы научных открытий

Непросто приходилось ученым прошлого. Интернета нет, научные журналы не выходили. Заявить об открытии можно было либо в книгах, либо в частных письмах. Написать и издать свою книгу — это несколько лет непростой и недешевой работы. А писать письма — ставить под удар свое открытие, которое может присвоить себе любой прочитавший письмо человек.

Защитить свое открытие можно, если шифровать письма. С 17 по 19 века многие ученые краткой фразой формулировали суть открытия, переставляли в ней буквы и полученную анаграмму отсылали коллегам. Получался своеобразный «анонс» гитопезы или открытия.

Это был неплохой способ всем сообщить о том, кто открытие совершил, но при этом сделать это так, чтобы коллеги по профессии не приписали открытие себе. Ну а если гипотеза окажется неверной, ее автор мог с таинственным видом сказать, что его анаграмма вообще про другое и избежать позора.

«Загадка» Галилео

В первой половине 17 века под пристальными взглядами астрономов находился газовый гигант Сатурн. Галилео Галилей первым в 1610 году увидел по бокам от планеты какие-то странные «наросты», которые он принял за его луны.

Зарисовки «лун» Сатурна от разных астрономов в начале 17 века

В тот же год коллеги Галилео получили письма, в которых было написано следующее:

«SMAISMRMILMEPOETALEUMIBUNENUGTTAUIRAS»

Очевидно, на клавиатуру Галилея запрыгнула кошка, вот только клавиатур тогда не существовало, а кошки письмо до сих пор не освоили. На самом деле, это анаграмма об его открытии.

Найдем количество возможных перестановок этих букв по формуле перестановок с повторениями. Буква S встречается 3 раза, буква M — 5 и так далее. Для сокращения записи не будем писать не влияющий на результат 1! для букв в единственном экземпляре:

\frac{37!}{3! \ 5! \ 4! \ 4! \ 2! \ 2! \ 4! \ 3! \ 4! \ 2! } \approx 10^{33}

Согласитесь, неплохой способ защитить свое открытие. Просто перемешал буквы и готово! Расшифровывается анаграмма как «altissimum planetam tergeminum observavi» — «Высочайшую планету тройную наблюдал», то есть речь идет о Сатурне с двумя его «лунами» по бокам.

Примечательно, что один из получателей «письма-анонса» Галилея, астроном Иоганн Кеплер, таки расшифровал анаграмму, но с ошибками. У него получилось «salve, umbistineum geminatum Martia proles» — «Привет вам, близнецы, порождение Марса». Он был убежден, что его соперник обнаружил два спутника Марса. Спутники у Марса действительно есть, вот только открыли их лишь два столетия спустя.

Открытие кольца Сатурна

В 1655 году молодой астроном Христиан Гюйгенс нашел разгадку загадочных «непостоянных лун» Сатурна, над которыми ломали голову Галилео Галилей и другие астрономы. Он предположил, что это никакие не луны, а огромное кольцо вокруг газового гиганта.

Не будучи до конца увереным в верности своей гипотезы, но и не желая терять первенство в потенциально громком открытии, в 1656 он публикует «анонс» в виде анаграммы:

«aaaaaaa ccccc d eeeee g h iiiiiii llll mm nnnnnnnnn oooo pp q rr s ttttt uuuuu»

Посчитаем количество вариантов составить текст из этих элементов по формуле перестановок с повторениями:

\frac{61!}{7! \ 5! \ 5! \ 7! \ 3! \ 2! \ 9! \ 4! \ 2! \ 2! \ 5! \ 5!} \approx 10^{60}

Это гигантское число. Даже миллиард компьютеров, каждый из которых проверяет по миллиарду перестановок в секунду, будут перебирать эти анаграммы примерно $10^{34}$ лет, что гораздо больше, чем предполагаемый возраст всей нашей Вселенной. Впрочем, зная контекст и используя правила языка можно настолько упростить поиск расшифровки, что с этой задачей справится и человек, но все равно будет очень непросто.

Расшифровка анаграммы; наброски Сатурна с кольцом; реальное фото Сатурна
Все, кроме фото — фрагменты из книги Гюгенса «Systema Saturnium», 1659

В 1659, через три года после «анонса», Гюйгенс уже в своей книге «Systema Saturnium» дал расшифровку анаграммы: «Annulo cingitur, tenui, plano, nusquam cohaerente, ad eclipticam inclinato» — «Окружен кольцом тонким, плоским, нигде не подвешенным, наклонным к эклиптике».

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

Было бы здорово дать еще один или два красивых примера, как перестановки применяются в жизни, помимо анаграмм.