"Алгебра и начала математического анализа. Углубленный уровень", Виленкин Н.Я., Ивашев-Мусатов О.С., Шварцбурд С.И.
Перестановка без повторений — это способ расположить все элементы набора так, чтобы каждый встретился ровно один раз. Такие подсчёты нужны, когда важно, кто или что стоит на каждом месте: например, при расстановке книг или составлении очереди. Если есть n различных элементов, первый можно выбрать n способами, следующий — n − 1 способом и так далее. Поэтому число перестановок равно n! — произведению чисел от 1 до n.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Перестановка без повторений — упорядоченное расположение всех элементов конечного множества, в котором каждый элемент используется ровно один раз. Например, для набора из букв A, B и C запись ABC — одна перестановка, а ACB — другая. Это понятие нужно, когда важно описать не только состав набора, но и места его элементов.
Факториал числа n — произведение всех натуральных чисел от 1 до n; его обозначают n!. Например, 4! = 1 · 2 · 3 · 4 = 24, а по определению 0! = 1. Факториал позволяет коротко записывать произведение, которое возникает при подсчёте последовательных выборов.
Число перестановок — количество различных порядков, которыми можно расположить n различных элементов; его обозначают P_n. Для n элементов P_n = n!, потому что на каждом следующем месте остаётся на один вариант меньше. Эта величина помогает быстро определить, сколько существует способов упорядочить весь набор.
Представим, что мы расставляем в ряд n различных предметов. Для первого места подходят все n предметов, поэтому выбор можно сделать n способами. После этого один предмет уже использован и повторно поставить его нельзя, значит, для второго места остаётся n − 1 вариант. Так ограничение «без повторений» каждый раз уменьшает число доступных вариантов.
Продолжая расстановку, для третьего места получаем n − 2 варианта, а далее количество вариантов убывает до одного. По правилу умножения количество способов выполнить несколько последовательных выборов равно произведению числа вариантов на каждом шаге. Поэтому общее число расположений равно n · (n − 1) · … · 2 · 1, то есть P_n = n!. Каждый полученный выбор мест задаёт один полный порядок элементов.
Факториал нужен как краткая запись длинного произведения: например, вместо 1 · 2 · 3 · 4 · 5 пишут 5!. Знак восклицания здесь не означает обычное умножение числа на единицу и не является степенью. Поэтому 5! = 120, а не 5 · 1 и не 5⁵. Чтобы вычислить факториал, перемножают все целые числа от 1 до данного числа.
Перестановки различаются, если хотя бы один элемент стоит на другом месте. Например, ABCD и BACD — разные порядки, хотя в них использованы те же буквы. Причина в том, что перестановка описывает последовательность позиций, а не просто перечисляет состав набора. Поэтому при подсчёте нельзя объединять расположения только потому, что в них встречаются одни и те же элементы.
Формула P_n = n! предполагает, что все элементы различны: тогда каждая последовательность выборов даёт новое расположение. Если два предмета одинаковы, обмен их мест может не изменить вид записи, и подсчёт n! посчитает совпадающие случаи отдельно. Например, перестановки букв А, А, Б включают записи, которые невозможно отличить друг от друга при обмене одинаковых букв. Значит, для наборов с повторами требуется отдельный учёт совпадений.
Сверяй условие задачи с каждой строкой таблицы: это помогает проверить, подходит ли формула факториала. Особенно важно выяснить, используются ли все элементы и являются ли они различными. Если хотя бы одно из этих условий не выполняется, простое применение P_n = n! может дать неверный результат.
| Характеристика | Описание |
|---|---|
| Что упорядочивается | Все n элементов набора, каждый ровно один раз. |
| Учитывается ли порядок элементов | Да: перестановки с разным порядком считаются разными. |
| Обозначение числа перестановок | P_n. |
| Формула для n элементов | P_n = n! = 1 · 2 · … · n. |
| Сколько вариантов выбора на каждом шаге | n, затем n − 1, далее n − 2 и так до 1. |
| Пример при n = 4 | P_4 = 4! = 24. |
Условие. Сколькими способами можно расставить на полке 4 различные книги? Важно, что требуется расположить все книги, а не выбрать из них несколько. Поскольку книги различны, любые два порядка, отличающиеся местами книг, будут считаться разными.
Ответ: 24 способа. Мы использовали перестановки, потому что каждая книга должна занять место, а порядок на полке имеет значение. Если бы перестановка двух книг не меняла результат, такой способ подсчёта не подошёл бы.
Условие. Для скольких различных элементов число перестановок равно 120? Здесь неизвестно количество элементов, поэтому нужно сопоставить 120 с факториалами. Начинаем с небольших значений и увеличиваем число, пока не получим нужный результат.
Ответ: 5 различных элементов. Проверка показывает, что 5! равно 120, а следующий факториал уже не подходит. Поскольку факториалы при переходе к следующему числу умножаются на положительное число, после 6! значение продолжит расти.
Условие. Сколькими способами можно расставить в ряд 6 различных книг, если две заданные книги не должны стоять рядом? Удобнее сначала посчитать все расстановки, а затем исключить те, где условие нарушено. Так как запрещённых случаев проще описать через соседство, объединим две заданные книги в один блок.
Ответ: 480 способов. Умножение на 2 учитывает оба возможных порядка книг внутри блока. Вычитание подходит, потому что каждая общая расстановка либо нарушает условие, либо удовлетворяет ему, и эти группы не пересекаются.
Не учитывать порядок. Ошибка — считать, что ABC и BAC представляют одну перестановку, ведь набор букв у них одинаков. Так рассуждают, когда смешивают упорядоченное расположение с обычным набором. Проверь себя: если элементы занимают разные места, это два разных результата.
Применять n! при повторяющихся элементах. В этом случае формула может посчитать одинаковые записи несколько раз, например при обмене двух одинаковых букв. Ошибку допускают, потому что ориентируются только на число предметов и не проверяют, различимы ли они. Перед вычислением перечисли элементы и выясни, нет ли среди них совпадающих.
Путать факториал с умножением или степенью. Запись 4! означает 1 · 2 · 3 · 4, а не 4 · 1 и не 4⁴. Такая ошибка возникает, если воспринимать восклицательный знак как часть обычной арифметической записи. Для проверки выпиши несколько множителей по порядку и сравни результат с факториалами малых чисел.
Считать перестановки, когда выбирают только часть элементов. Перестановка включает все n элементов, поэтому формула n! не подходит, если из набора нужно выбрать и упорядочить лишь несколько. Ошибка появляется, когда замечают важность порядка, но не проверяют полноту расположения. Пересчитай, все ли заданные элементы должны участвовать; если нет, задача относится к другому виду комбинаторных подсчётов.
Для вывода формулы перестановок нужно знать правило умножения: если действие состоит из последовательных шагов, число способов определяется произведением вариантов на каждом шаге. Также нужно понимать, что упорядоченный набор — это набор, в котором место каждого элемента имеет значение. Эти идеи позволяют увидеть, почему количество доступных вариантов при расстановке постепенно уменьшается.
Факториалы встречаются далее при изучении размещений и сочетаний — способов выбирать элементы с учётом порядка или без него. Формула перестановок служит основой для сравнения этих способов подсчёта и решения более сложных комбинаторных задач. Поэтому навык вычислять n! и проверять условия его применения пригодится в разных разделах комбинаторики.
Чем перестановка отличается от обычного набора элементов?
В обычном наборе порядок элементов может не иметь значения, а перестановка задаёт конкретный порядок всех элементов. Например, ABC и BAC — разные перестановки одного набора.
Почему число перестановок равно n!, а не n · n?
На каждое место приходится своё число вариантов: сначала n, затем n − 1, далее n − 2 и так до 1. По правилу умножения эти числа перемножают, получая n!, а n · n не учитывает, что после выбора элемента вариантов становится меньше.
Почему при подсчёте перестановок важен порядок элементов?
Потому что перестановка описывает, какой элемент стоит на каждом месте. Если поменять местами хотя бы два элемента, получится другое расположение.
Можно ли использовать формулу P_n = n!, если некоторые элементы повторяются?
Нет, формула P_n = n! относится к различным элементам. При повторах некоторые перестановки внешне совпадают, поэтому число различных расположений нужно считать с учётом этих совпадений.
Как понять, что в задаче нужно считать именно перестановки?
Проверь, используются ли все элементы и считается ли разным их расположение в разном порядке. Если да и элементы различны, нужно найти число перестановок и применить формулу P_n = n!.
3. Перестановки без повторений
