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

Всего 12 способностей героя, которые можно расставить на 12 мест в панели быстрого доступа. При таких условиях каждый вариант панели можно рассматривать как перестановку из 12 способностей. Найдем количество перестановок по формуле:

Удивительно, как тесно могут быть связаны небольшие (12) и огромные (479 миллионов) числа! А панель-то не такая уж и большая!

Когда друзей шестеро схитрите и добавьте как-бы седьмого друга — пустоту.

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

Если друзей шестеро, то добавим к ним еще один элемент — пустоту, которую тоже можно «усадить» на место в машине. Теперь у нас вновь 7 элементов (6 друзей и 1 пустота) и 7 мест в машине. Снова перестановки из 7 элементов и по-прежнему 5040 вариантов их «рассадить».

Как же так?! Друзей стало меньше, а количество способов их рассадить не изменилось! Этот неочевидный момент можно пояснить, если взглянуть на задачу под другим углом:

Решение «наоборот»

Задачу можно решить и наоборот — представить друзей как 7 вакантных мест (роль k), которым мы назначаем 7 сидений такси (роль n).

Тогда получается $A_7^7 = 5040$ вариантов. В практикуме по размещениям мы доказывали вот такое интересное равенство:

Когда друзей (вакантных мест) становится 6, мы можем использовать это равенство!

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

$P_7 = 5040$ способов рассадить как семерых друзей, так и шестерых.

Смотрите решение аналогичной задачи из статьи.

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

Количество перестановок во втором вопросе тоже равно 120, но среди полученных чисел есть четырехзначные, начинающиеся с 0. Всего их $P_4 = 4! = 24$. За подробностями смотрите пример из статьи. Находим количество пятизначных чисел:

Ответ на первый вопрос — 120, на второй — 96.

Найдите количество всех возможных исходов соревнований и количество исходов, которые не удовлетворяют условию.

Логика решения простая: находим количество всех вариантов, потом количество вариантов, в которых команда A заняла первое и последние места. Вычитаем из всех вариантов лишние. PROFIT!

Для начала найдем количество всех возможных результатов соревнования. Каждый такой результат это размещение 6 мест по 6 названиям команд, то есть перестановка из 6 элементов. Посчитаем количество этих перестановок по формуле:

Теперь находим количество вариантов, когда команда A заняла первое место. Их количество равно числу перестановок из 5 оставшихся команд по 5 оставшимся местам:

Столько же вариантов, в которых A заняла последнее место.

Теперь просто вычитаем из всех возможных ситуаций (720) варианты, которые не удовлетворяют условию (240):

Решение через правило умножения

Задачу можно довольно просто решить «напрямую». На первое место претендуют все команды, кроме A, то есть 5 команд. Вне зависимости от выбора команды на первое место, на последнее место можно выбрать одну из 4 команд (все оставшиеся кроме A). Ну а далее со второго по пятое места можно выбирать любые оставшиеся команды, включая A: Используем правило умножения:

480

Число четное, если последняя его цифра четная и наоборот.

Число четное, только если последняя его цифра четная, и наоброт. Среди данных цифр четных две (6 и 4). Выбрав любую, оставшиеся 3 цифры надо расставить по 3 разрядам, а количество способов это сделать можно посчитать по формуле перестановок: $P_3 = 3! = 6$.

Итак, есть 2 способа выбрать последнюю цифру числа. Вне зависимости от сделанного выбора, оставишеся разряды можно заполнить 6 способами. Используем правило умножения:

Всего 12 четных четырехзначных чисел. И 12 нечетных, так как нечетных цифр тоже 2.

Можно составить 12 четных и 12 нечетных четырехзначных чисел.

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

Итак, пароля из 9 разных символов будет достаточно, чтобы Элли была спокойна. Жаль только она не знает, что эти $362 \ 880$ с помощью брут-форса можно перебрать за пару секунд...

9

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

У нас есть группа из трех человек, которую нужно поместить в таблицу результатов. В этой таблице 16 позиций, но эту группу можно поместить только на 13 мест — с 1 по 13. На 14, 15 и 16 места группу поместить нельзя, иначе Женя и Настя не влезут в таблицу.

Вне зависимости от того, каким из 13-ти способов мы разместили группу в таблице результатов, оставшиеся 13 мест могут занять любые остальные участники, причем сделать они это могут $P_{13} = 13!$ способами.

По правилу умножения находим все возможные способы, которыми группа из трех подруг может завершить марафон:

Если финиш они пересекают в любом порядке, друг за другом, то нужно сначала найти все варианты составить из трех подруг группу. Сделать это можно $P_3 = 3! = 6$ способами. Дальше действия те же самые, что и для заранее заданной группы:

Финишировать именно в таком порядке подруги могут $6\cdot 13!$ способами. Финишировать как группа, без определенного порядка, подруги могут $78 \cdot 13!$ способами.

Единственный вариант рассадить участников — чередовать мужчин и женщин. Сначала посадите одну женщину. Ее положение сразу разделит все оставшиеся стулья на «мужские» и «женские».

В случае с каруселью помните, что она не способна поменять положение участников относительно друга друга.

Раз лица одного пола не могут сидеть рядом друг с другом, то остается только вариант, когда мужчины и женщины чередуются. То есть стул 1 — мужчина, стул 2 — женщина, стул 3 — мужчина и так далее.

Для начала выберем одну женщину и посадим ее на стул. Сделать это можно 10 способами. Посадив эту женщину на стул, мы все оставшиеся стулья поделили на 5 «мужских» и 4 «женских».

Оставшихся 4 женщин можно рассадить только на 4 «женских» стула. Каждый способ сделать это является перестановкой, а их количество равно $P_4 = 4!$. Мужчин же надо рассадить по 5 «мужским» стульям и это еще $P_5 = 5!$ способов.

Итак, первую женщину можно посадить на стул 10 способами. Вне зависимости от выбранного стула, оставшихся женщин можно посадить 4! способами, а мужчин 5! способами. Используем правило умножения:

С каруселью алгоритм тот же самый, вот только нет никакой разницы, куда сажать первую женщину, ведь поворотом карусели ее можно сместить «на любой другой стул». Стало быть, 10 вариантов посадить первую женщину превращаются всего в 1.

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

Если ваша вечеринка не похожа на это, даже не пытайтесь меня приглашать...

$28 \ 800$ способов, если участников рассаживать за столом и в 10 раз меньше, 2880, если их рассаживать за карусель.

Аналогичная задача в теме «Размещения».

Любые числа, например 423 и 122, можно записать в развернутом виде:

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

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

Пять цифр

Начнем с разряда единиц. Если мы туда поставим цифру 5, то оставшиеся 4 цифры по оставшимся 4 разрядам можно записать $P_4 = 4!$ способами. Всего 4! пятизначных чисел, оканчивающихся на цифру 5. По такой же логике на цифру 4 тоже оканчивается 4! чисел, как и на цифры 3, 2, 1.

Итак, на каждую из цифр от 1 до 5 приходится по 4! оканчивающихся на нее пятизначных чисел. Найдем сумму единиц всех этих чисел:

С разрядом десятков точно такая же ситуация. На каждую из цифр от 1 до 5 приходится по 4! пятизначных чисел, у которых в разряде десятков стоит выбранная цифра. Найдем сумму десятков всех этих чисел:

По аналогии вычисляем суммы для оставшихся разрядов: 36000 для сотен, 360000 для тысяч и 3600000 для десятков тысяч. Осталось найти общую сумму:

Девять цифр

Действия точно такие же, но в этот раз по оставшимся 4 разрядам мы записываем уже не 4 цифры, а 8. Количество способов это сделать можно посчитать по формуле размещений без повторений:

Для единиц получаем такую сумму:

Дальше считаем общую сумму по всем разрядам:

Сумма для пяти цифр:

Сумма для девяти цифр:

Используйте тот факт, что каждая ладья находится на своей вертикали и горизонтали.

Если поставить ладью на одну из 8 вертикалей, то следующую ладью придется ставить уже на другую вертикаль. Всего на шахматной доске 8 вертикалей, значит каждую из них займет одна ладья.

Выстраиваем все ладьи в ряд, занимая все 8 ветрикалей. Так как все ладьи одинаковые, сделать это можно одним способом:

Теперь надо передвинуть каждую ладью на свою горизонталь. Другими словами, нужно разместить 8 ладей по 8 горизонталям без повторений. Например, можно расставить их по возрастанию номера горизонтали:

Каждое такое размещение ладей можно рассматривать как перестановку. Найдем количество перестановок по формуле:

$40 \ 320$

Внесите небольшое изменение в процесс решения задачи «Бесконтактный бой».

В решении задачи «Бесконтактный бой» мы сначала расставили ладьи в ряд. Если ладьи одинаковые, то сделать это можно одним способом. Но в этот раз ладьи у нас разные, поэтому каждая расстановка их в ряд по сути является перестановкой из n элементов. Количество таких перестановок находим по формуле:

Дальше, любую из этих $n!$ расстановок в ряд можно $n!$ способами раскидать по n горизонталям. По правилу умножения находим всего $n! \cdot n! = n!^2$ вариантов расположить n разных ладей на доске $n \times n$.

Решение через правило умножения

Первую ладью можно поставить на любую из $n^2$ доступных клеток шахматной доски. Эта ладья бьет по своей горизонтали и вертикали, поэтому для второй ладьи доступно лишь $(n-1)$ горизонталей и $(n-1)$ вертикалей, что дает $(n-1)^2$ способов размещения.

Продолжая эту логику дальше и используя правило умножения находим все способы разместить ладьи:

$n!^2$

Пользуйтесь формулой числа перестановок и факториальной формулой числа размещений без повторений.

Пункт а)

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

Для числителя несколько раз подряд используем рекуррентную формулу факториала:

Решаем это квадратное уравнение и находим два возможных значения n:

Значение -20 не подходит, потому что используемые комбинаторные понятия определены только для неотрицательных чисел. Другими словами, вопрос «сколько перестановок можно сделать из -20 элементов?» не имеет смысла. Поэтому остается только вариант с $n=11$.

Пункт б)

Используем те же самые формулы, что и в пункте а):

Для числителя два раза подряд используем рекуррентную формулу факториала:

Ответ 10.

Пункт в)

Используем те же самые формулы, что и в пункте а):

Для числителя дроби слева два раза подряд используем рекуррентную формулу факториала:

Решая по методу интервалов находим, что такому неравенству удовлетворяют все значения n в следующих границах:

Так как n — неотрицательное целое число (иначе задача не имеет смысла), то годятся варианты $n = 0; 1; 2$.

Пункт а) 11
Пункт б) 10
Пункт в) 0, 1, 2

Используйте формулу перестановок с повторениями.

9 фруктов, которые раздаются на протяжении 9 дней. Каждый способ это сделать является перестановкой. Так как среди элементов есть дубликаты, то использовать надо формулу перестановок с повторениями:

1260

Используйте формулу перестановок с повторениями.

Начем со слова «ингредиент». В нем 10 букв, из которых надо составлять анаграммы. Каждую такую анаграмму можно считать за перестановку. Так как среди букв есть дубликаты (2 буквы «и», 2 «е» и 2 «н»), то использовать надо формулу перестановок с повторениями:

Анаграммы для остальных слов считаем точно так же. Для «метаматематики» их количество равно:

Для «парабола»:

«ингредиент» — $453 \ 600$
«метаматематика» — $50 \ 450 \ 400$
«парабола» — 6720

Используйте важное отличие.

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

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

3

Двигайтесь слева-направо, подсчитывайте и вычеркивайте одинаковые буквы. Далее воспользуйтесь формулой перестановок с повторениями.

Слева-направо рассматриваем каждую букву, считаем, сколько раз она повторяется в тексте и вычеркиваем ее:

Буква «h» встречается один раз, можно ее не учитывать. Буква «a» встретилась 6 раз. Вычеркиваем и подсчитываем повторящиеся буквы по такому же алгоритму и дальше, после чего используем формулу перестановок с повторениями:

К сожалению, несчастный Кеплер и в этот раз «разгадал» анаграмму неправильно. У него получилось «macula rufa in Jove est gyratur mathem» — «На Юпитере есть красное пятно, вращающееся математически».

Так, очередная неверно разгаданная анаграмма Галилео оказалась предсказанием, ведь «Большое красное пятно» Юпитера действительно существует и будет открыто через 200 лет.

На самом деле анаграма расшифровывалась как «Cynthiae figuras aemulatur mater amorum» — «Мать любви [Венера] подражает фигурам Цинтии [Луны]» в том смысле, что у Венеры как и у Луны есть фазы.

Используйте формулу перестановок с повторениями.

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

5040

Для ответа на первый вопрос воспользуйтесь формулой перестановок с повторениями.

Для ответа на второй вопрос нужно помимо имеющихся фигур также рассмотреть пустые клетки как своеборазные «фигуры», которые мы тоже как-бы расставляем по полю. Так получится остаться в рамках перестановок.

Две линии

Всего 16 фигур, которые надо расставить в 16 клеток (это и есть две линии). Каждую такую расстановку можно рассматривать как перестановку. Так как некоторые фигуры имеют дубликаты, нужно использовать формулу перестановок с повторениями:

Вся доска

Этот вопрос может поставить в тупик. Как нам разместить 16 фигур по 64 клеткам? Если бы фигуры были уникальными, можно было бы воспользоваться формулой размещений без повторений:

Но здесь можно провернуть хитрый финт. Можно добавить к 16 фигурам 48 пустых клетки и думать о них, как о еще 48 повторяющихся фигурах. Тогда задача сводится к расстановке 64 фигур по 64 клеткам поля, для решения которой можно использовать формулу перестановок с повторениями:

Пешки

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

Способы расставить фигуры по двум первым линиям:

Способы расставить фигуры по всей доске:

Способы расставить фигуры с пешками по всей доске:

Решается почти так же, как и «Комбинаторный сумматор», но с небольшим нюансом.

Пункт а)

Как и в «Комбинаторном сумматоре», нам нужно отдельно сложить все единицы, десятки, сотни и тысячи.

Начнем с единиц. Если в этом разряде стоит цифра 1 или 5, то оставшиеся три разряда можно заполнить $P(2, \ 1) = 3$ способами (две 2 и еще одна цифра). Если же в этом разряде стоит цифра 2, то оставшиеся разряды можно заполнить $P_3 = 6$ способами. Находим сумму всех единиц:

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

Пункт б)

Решение аналогичное. Если в разряде единиц стоит 1, то есть только один способ заполнить оставшиеся разряды — записать в них тройки. Если в разряде единиц стоит 3, то есть $P(2, \ 1) = 3$. Рассмотрим, какая сумма единиц будет в этом случае:

Общая сумма:

Пункт в)

Сумма единиц:

Общая сумма:

Пункт а) $33 \ 330$
Пункт б) $11\ 110$
Пункт в) $16\ 665$

Адаптируйте решение задачи о композициях числа из статьи про размещения.

Самый длинный способ записать число n — представить его в виде суммы n единиц:

Заменим теперь в этой записи все плюсы на пустые квадраты. Всего этих пустых квадратов $n-1$, на единицу меньше, чем количество единиц:

Так как нам нужно m слагаемых, то по этим квадратам мы обязаны расставить ровно $m-1$ запятых, которые разделяют слагаемые. В оставшиеся $(n-1)-(m-1) = n-m$ квадратов вписываем +.

Например, нужно найти разложения числа 5 ровно на 3 слагаемых. Значит ищем перестановки из 3-1 = 2 запятых и 5-3=2 плюсов:

Так как элементы (плюсы и запятые) у нас повторяются, то количество способов разложить число n на m слагаемых можно найти по формуле перестановок с повторениями:

Эта задача является более конкретным вариантом замечательной задачи о композициях числа.

Разбейте эту задачу на две задачи поменьше.

Отдельно посчитайте сумму всех чисел, в том числе когда 0 является первой цифрой. Отдельно посчитайте сумму четырехзначных чисел из всех данных цифр, кроме 0. Вычтите из большей суммы меньшую.

$2 \ 599 \ 980$

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

Каждая расстановка шариков в ряд это просто перестановка с повторениями из 9 элементов по 9 вакантным местам. Посчитаем количество таких перестановок по формуле:

Как было 126 способов разложить шарики в ряд, так есть и 126 способов разложить их по кругу. Представим, что мы как-то разложили их по кругу. Так мы получили некий шаблон. Далее мы можем 8 раз «повернуть» круг, каждый раз получая дубликат этого шаблона. Выходит, каждый шаблон состоит из 9 дубликатов: 1-го исходного положения и 8 дубликатов, получаемых поворотом.

Получается, что все 126 вариантов разложить шарики по кругу можно разбить на шаблоны, в каждом из которых по 9 дубликатов. Тогда этих самых шаблонов — уникальных расположений шариков по кругу — будет 126 : 9 = 14.

В ряд шарики можно разложить 126 способами, а по кругу 14 способами.

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

Кстати, такой же подход можно использовать и в задаче «Званый вечер». Когда мы рассаживаем гостей на карусели, у нас по-прежнему есть $10\cdot 4! \cdot 5!$ способов их рассадить. Но среди этих «рассадок» также можно выделить шаблоны и каждый из них будет состоять из 10 дубликатов: исходного положения и 9 поворотов. Уникальных шаблонов остается $10 \cdot 4! \cdot 5! : 10 = 4!\cdot 5!$.

Для условия с поворотом квадрата воспользуйтесь рассуждениями из решения задачи «Хочешь в ряд, а хочешь в круг».

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

Точно так же, как и в задаче «Хочешь в ряд, а хочешь в круг», если допустить вращение квадрата, то среди $45 \ 360$ перестановок оказывается множество дубликатов. Если быть конкретнее, то каждый уникальный шаблон состоит из 4 дубликатов: 1-го исходного положения и 3 поворотов на $90\degree$.

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

$45 \ 360$ вариантов составить большой квадрат и $11 \ 340$ вариантов, если допустить вращение.