Глава
Теория
Перестановка — это расположение объектов в порядке. Главное отличие от простого выбора: порядок теперь является частью объекта. Если объекты различны, \(n\) объектов можно упорядочить \(n!\) способами. Если некоторые объекты одинаковы, нужно убрать переучёт от перестановок одинаковых копий.
Олимпиадные задачи на перестановки редко сводятся к одной формуле. Чаще нужно выбрать правильный приём: склеить блок, вычесть запрещённые соседства, зафиксировать поворот в круговой рассадке или разбить по позициям.
Если объекты должны быть рядом, попробуйте блок. Если объекты не должны быть рядом, часто удобнее вычесть случаи, где они рядом. Если расположение круговое, сначала зафиксируйте один объект или используйте \((n-1)!\). Если есть одинаковые буквы, сначала посчитайте как разные, затем разделите на перестановки одинаковых копий.
В задачах с запретами на позиции полезно спросить: запреты независимы или пересекаются? Если пересекаются, может понадобиться включение-исключение.
Примеры
Базовая техника: каждый следующий выбор уменьшает число вариантов.
Задача. Сколькими способами можно расставить \(6\) разных книг на полке?
На первое место можно поставить \(6\) книг, на второе \(5\), затем \(4,3,2,1\). Всего \(6!=720\).
Комментарий. Это линейное расположение разных объектов.
Одинаковые буквы создают переучёт.
Задача. Сколько различных слов можно получить перестановкой букв слова \(BANANA\)?
Всего \(6\) букв. Буква \(A\) повторяется \(3\) раза, буква \(N\) — \(2\) раза. Если считать все копии различными, будет \(6!\), но каждое слово посчитано \(3!\cdot2!\) раз. Ответ \(6!/(3!\cdot2!)=60\).
Комментарий. Делим только на перестановки одинаковых букв.
Если два объекта должны стоять рядом, склейте их.
Задача. Сколькими способами можно расставить \(6\) человек в ряд, если Антон и Борис должны стоять рядом?
Склеим Антона и Бориса в блок. Тогда есть \(5\) объектов: блок и ещё \(4\) человека. Их можно расставить \(5!\) способами. Внутри блока \(2\) порядка. Ответ \(2\cdot5!=240\).
Комментарий. Нельзя забыть внутренний порядок блока.
Запрет часто проще считать как все минус плохие.
Задача. Сколькими способами можно расставить \(6\) человек в ряд, если Антон и Борис не должны стоять рядом?
Всего \(6!=720\) расположений. Рядом они стоят \(2\cdot5!=240\) способами. Значит не рядом: \(720-240=480\).
Комментарий. Это дополнение к предыдущей задаче.
В круге повороты считаются одинаковыми.
Задача. Сколькими способами можно посадить \(5\) разных людей за круглый стол?
Зафиксируем одного человека. Оставшихся \(4\) можно расположить вокруг него \(4!\) способами. Ответ \(24\).
Комментарий. Фиксация одного человека убирает поворот.
Блок работает и за круглым столом.
Задача. Сколькими способами можно посадить \(6\) людей за круглый стол, если двое заданных должны сидеть рядом?
Склеим этих двоих в блок. Получаем \(5\) объектов на круге, их можно расположить \((5-1)!=24\) способами. Внутри блока \(2\) порядка. Ответ \(48\).
Комментарий. Сначала учитываем круг, потом внутренний порядок блока.
Половина перестановок имеет \(A\) перед \(B\).
Задача. Сколько перестановок чисел \(1,2,3,4,5\) имеют \(1\) раньше \(2\)?
Во всех \(5!\) перестановках числа \(1\) и \(2\) симметричны: ровно в половине \(1\) стоит раньше \(2\), в половине наоборот. Ответ \(5!/2=60\).
Комментарий. Это не условие соседства.
Запреты на неподвижные точки пересекаются.
Задача. Сколько перестановок \(1,2,3,4\) не оставляют ни одно число на своём месте?
Всего \(4!=24\). Вычтем перестановки с хотя бы одной неподвижной точкой: \(4\cdot3!\). Вернём пересечения двух неподвижных точек: \(6\cdot2!\). Вычтем три: \(4\cdot1!\). Вернём четыре: \(1\). Ответ \(24-24+12-4+1=9\).
Комментарий. Это первая версия задачи о беспорядках.
Задачи
Сколькими способами можно расставить \(5\) разных книг на полке?
Это перестановка \(5\) различных объектов.
Ответ \(5!=120\).
Сколько различных слов можно получить перестановкой букв слова \(MAMA\)?
Есть две буквы \(M\) и две буквы \(A\).
Если считать все \(4\) буквы различными, будет \(4!=24\). Каждое слово посчитано \(2!\cdot2!=4\) раза. Ответ \(24/4=6\).
Сколькими способами можно выбрать и упорядочить \(3\) разных ученика из \(7\)?
Выбирайте первого, второго, третьего.
Первого можно выбрать \(7\) способами, второго \(6\), третьего \(5\). Всего \(7\cdot6\cdot5=210\).
Сколькими способами можно посадить \(5\) разных людей за круглый стол?
Зафиксируйте одного человека.
Фиксируем одного человека, чтобы убрать повороты. Остальных \(4\) рассаживаем \(4!=24\) способами.
Сколькими способами можно расставить \(6\) человек в ряд, если двое заданных должны стоять рядом?
Склейте этих двоих в блок.
Блок и ещё \(4\) человека — всего \(5\) объектов, их можно расставить \(5!\) способами. Внутри блока \(2\) порядка. Ответ \(2\cdot5!=240\).
Сколькими способами можно расставить \(6\) человек в ряд, если двое заданных не должны стоять рядом?
Вычтите случаи, где они рядом.
Всего \(6!=720\). Рядом они стоят \(2\cdot5!=240\) способами. Значит ответ \(720-240=480\).
Сколько различных перестановок букв слова \(BANANA\)?
Буква \(A\) встречается \(3\) раза, \(N\) — \(2\) раза.
Всего \(6\) букв. Делим \(6!\) на \(3!\) для букв \(A\) и на \(2!\) для букв \(N\). Получаем \(6!/(3!\cdot2!)=60\).
Семь учеников становятся в ряд. Сколькими способами это можно сделать, если два заданных ученика не должны стоять рядом?
Всего минус рядом.
Всего \(7!=5040\). Если двое рядом, склеиваем их: \(6!\cdot2=1440\). Ответ \(5040-1440=3600\).
На полке \(3\) книги по математике, \(2\) по физике и \(2\) по истории, все книги разные. Сколькими способами расставить их так, чтобы книги каждого предмета стояли вместе?
Считайте каждый предмет блоком.
Три предметных блока можно переставить \(3!\) способами. Внутри блоков: \(3!\), \(2!\), \(2!\). Всего \(3!\cdot3!\cdot2!\cdot2!=144\).
Сколькими способами можно посадить \(6\) человек за круглый стол, если двое заданных должны сидеть рядом?
Склейте пару и используйте круговую перестановку.
Пара образует блок. Итого \(5\) объектов на круге, их можно расположить \((5-1)!=24\) способами. Внутри блока \(2\) порядка. Ответ \(48\).
Сколько перестановок чисел \(1,2,3,4\) не оставляют ни одно число на своём месте?
Используйте включение-исключение по неподвижным точкам.
Всего \(24\). С одной указанной неподвижной точкой: \(3!\), таких точек \(4\). С двумя: \(2!\), таких пар \(6\). С тремя: \(1!\), таких наборов \(4\). С четырьмя: \(1\). Ответ \(24-4\cdot6+6\cdot2-4\cdot1+1=9\).
Сколько перестановок чисел \(1,2,3,4,5\) имеют \(1\) раньше \(2\)?
Для каждой перестановки с \(1\) раньше \(2\) есть парная с \(2\) раньше \(1\).
Всего \(5!=120\) перестановок. По симметрии ровно половина имеет \(1\) раньше \(2\). Ответ \(60\).
Сколькими способами можно поставить в ряд \(5\) мальчиков и \(4\) девочек так, чтобы никакие две девочки не стояли рядом?
Сначала расставьте мальчиков, затем выберите промежутки для девочек.
Мальчиков можно расставить \(5!\) способами. Вокруг них \(6\) промежутков: до первого, между соседними и после последнего. Выбираем \(4\) промежутка для девочек и расставляем девочек \(4!\) способами. Ответ \(5!\cdot15\cdot4!=43200\).
Сколько перестановок букв \(A,A,B,B,C,C\) не имеют двух одинаковых соседних букв?
Вычтите случаи, где \(AA\), \(BB\) или \(CC\) стоят блоком.
Всего \(6!/(2!2!2!)=90\). Если \(AA\) рядом, считаем блок \(AA\), \(B,B,C,C\): \(5!/(2!2!)=30\), таких букв \(3\). Если две пары рядом, например \(AA\) и \(BB\), получаем \(4!/2!=12\), таких выборов \(3\). Если все три пары рядом, \(3!=6\). Ответ \(90-3\cdot30+3\cdot12-6=30\).
Сколько четырёхзначных чисел с различными цифрами можно составить из \(0,1,\ldots,6\), если число делится на \(5\)?
Последняя цифра \(0\) или \(5\).
Если последняя \(0\), первая цифра выбирается \(6\) способами, затем \(5\) и \(4\): \(120\). Если последняя \(5\), первая цифра не \(0\) и не \(5\): \(5\) способов, затем \(5\) и \(4\): \(100\). Всего \(220\).
Сколькими способами можно посадить \(8\) человек за круглый стол, если двое заданных не должны сидеть рядом?
Всего круговых рассадок минус рассадки, где они рядом.
Всего \((8-1)!=5040\). Если двое рядом, склеиваем их в блок: остаётся \(7\) объектов на круге, \((7-1)!=720\), внутри блока \(2\) порядка. Плохих \(1440\). Ответ \(5040-1440=3600\).
На полке стоят \(8\) разных книг. Сколькими способами можно расставить их так, чтобы книги \(A,B,C\) стояли в порядке \(A\) раньше \(B\) раньше \(C\), не обязательно подряд?
Среди \(3!\) относительных порядков \(A,B,C\) подходит один.
Всего \(8!\) расстановок. Относительные порядки книг \(A,B,C\) равновозможны, их \(3!=6\). Подходит один порядок, значит ответ \(8!/6=6720\).
Сколько перестановок чисел \(1,2,\ldots,7\) имеют чётные числа ровно на чётных местах?
Чётных мест три, чётных чисел тоже три.
Чётные числа \(2,4,6\) можно расставить по местам \(2,4,6\) в \(3!\) способах. Нечётные числа \(1,3,5,7\) занимают остальные места в \(4!\) способах. Ответ \(3!\cdot4!=144\).
Сколько слов длины \(5\) над алфавитом \(\{A,B,C,D\}\) содержат ровно две буквы \(A\), причём они не стоят рядом?
Сначала выберите две несоседние позиции для \(A\).
Всего пар позиций для двух \(A\): \(10\). Соседних пар \(4\), значит несоседних \(6\). Остальные \(3\) позиции можно заполнить буквами \(B,C,D\) независимо: \(3^3=27\). Ответ \(6\cdot27=162\).
Сколькими способами можно посадить \(5\) человек за круглый стол, если между Антоном и Борисом должен сидеть ровно один человек?
Зафиксируйте Антона.
Зафиксируем Антона. Для Бориса есть \(2\) места на расстоянии два шага по кругу от Антона. Оставшихся \(3\) человек рассаживаем \(3!\) способами. Ответ \(2\cdot3!=12\).
Сколько перестановок чисел \(1,2,3,4,5\) не оставляют ни одно число на своём месте?
Примените включение-исключение по неподвижным точкам.
Всего \(5!=120\). С хотя бы одной указанной неподвижной точкой считаем по включению-исключению: \(120-5\cdot4!+10\cdot3!-10\cdot2!+5\cdot1!-1=120-120+60-20+5-1=44\).
Сколькими способами можно посадить \(6\) мальчиков и \(6\) девочек за круглый стол так, чтобы мальчики и девочки чередовались?
Сначала посадите мальчиков за круглый стол, затем девочек в промежутки.
Мальчиков можно посадить по кругу \((6-1)!=120\) способами. Между ними образуется \(6\) промежутков, в которые нужно рассадить \(6\) девочек: \(6!\) способов. Ответ \(120\cdot720=86400\).
Сколько перестановок чисел \(1,2,\ldots,8\) имеют свойство: никакие два из чисел \(1,2,3\) не стоят рядом?
Сначала расставьте остальные пять чисел.
Числа \(4,5,6,7,8\) можно расставить \(5!\) способами. Они создают \(6\) промежутков, включая края. Нужно выбрать \(3\) промежутка для чисел \(1,2,3\) и расположить эти числа \(3!\) способами. Ответ \(5!\cdot20\cdot6=14400\).
Сколько перестановок букв \(A,A,B,B,C,C,D,D,E,E\) не имеют двух одинаковых соседних букв?
Используйте включение-исключение по событиям \(AA\), \(BB\), \(CC\), \(DD\), \(EE\) стоят рядом.
Всего перестановок \(10!/(2!^5)=113400\). Если выбрать \(k\) букв, пары которых склеены, получаем \(C(5,k)(10-k)!/(2!^{5-k})\) расположений. По включению-исключению: \(113400-113400+50400-12600+1800-120=39480\).
Лестницы