1. Размещения с повторениями

Определения и обозначения

Размещение с повторениями из n элементов по k — упорядоченная последовательность длины k, составленная из n различных элементов, причём элемент может встречаться несколько раз. Например, из цифр 1, 2 и 3 можно составить последовательность 121: цифра 1 использована дважды. Такое определение помогает отличать эти последовательности от наборов, где порядок не учитывают.

Длина размещения — число позиций в последовательности; её обозначают k. Если составляют трёхбуквенное слово, то длина равна 3, даже если какие-то буквы повторяются. Параметр k нужен, чтобы указать, сколько раз предстоит сделать выбор и сколько мест требуется заполнить.

Число размещений с повторениями — количество различных последовательностей длины k, составленных из n элементов; обозначение — Āₙᵏ = nᵏ. Здесь n показывает, сколько элементов доступно для выбора, а k — сколько позиций надо заполнить. Формула позволяет сразу вычислить количество последовательностей, не перечисляя их по одной.

Как это устроено

Каждое размещение задаётся выбором элемента для каждой из k позиций, поэтому важно учитывать порядок элементов. Первая позиция и вторая — разные места, и перестановка выбранных элементов обычно создаёт новую последовательность. Например, код 12 отличается от кода 21: у них одинаковые цифры, но цифры занимают разные позиции. Поэтому здесь считают именно последовательности, а не просто группы выбранных элементов.

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

По правилу умножения число последовательностей равно произведению числа вариантов для всех позиций: n · n · … · n = nᵏ. Правило умножения применяют, когда результат складывается из нескольких последовательных выборов: для каждого варианта на первой позиции рассматривают все варианты на второй и так далее. Поскольку множитель n повторяется k раз, произведение удобно записать степенью. Например, четыре позиции с пятью вариантами на каждой дают 5 · 5 · 5 · 5 = 5⁴ последовательностей.

При k = 1 получается n вариантов, а при k = 0 существует одна пустая последовательность; эти случаи согласуются с формулой nᵏ. Для одной позиции достаточно выбрать один из n элементов, поэтому вариантов ровно n. Последовательность длины ноль не содержит позиций и не требует ни одного выбора; такой результат один — пустая последовательность. Соглашение n⁰ = 1 сохраняет формулу и для этого особого случая.

Если повторения запрещены, число вариантов на следующих позициях уменьшается, поэтому формула nᵏ для обычных размещений не подходит. После выбора элемента его уже нельзя поставить на другое место, и для второй позиции остаётся n − 1 вариант, для третьей — n − 2. Например, при трёх доступных элементах нельзя заполнить четыре позиции без повторений. Поэтому перед вычислением нужно выяснить, разрешено ли использовать элемент снова.

Размещения без повторений и с повторениями

Сначала определите, можно ли повторно использовать уже выбранный элемент: это ключевое различие между столбцами. Если повторение разрешено, на каждой позиции остаётся n вариантов и применяют nᵏ. Если оно запрещено, число вариантов сокращается, а длина последовательности не может превышать число доступных элементов.

Разбор задач

Задача 1. Из цифр 1, 2 и 3 составляют двузначные коды, цифры могут повторяться. Сколько кодов получится? Нужно считать коды, а не двузначные числа: в условии важны две отдельные позиции, и одна цифра может появиться на обеих. Запишем число вариантов и вычислим его по правилу умножения.

1. Для первой позиции есть три цифры на выбор.
2. Для второй позиции также есть три варианта, потому что повторение разрешено.
3. Перемножаем числа вариантов: 3 · 3 = 3² = 9.

Ответ: 9 кодов. Например, среди них есть 11 и 33, а порядок цифр отличает код 12 от кода 21.

Задача 2. Сколько четырёхбуквенных последовательностей можно составить из пяти букв, если буквы разрешено повторять? Последовательность имеет четыре позиции, значит, k = 4. Для каждой позиции доступно пять букв, причём выбор на одном месте не запрещает использовать ту же букву на другом.

1. Сопоставляем число доступных элементов и длину: n = 5, k = 4.
2. Повторения разрешены, поэтому для всех четырёх позиций число вариантов одинаково.
3. Применяем формулу: 5⁴ = 5 · 5 · 5 · 5 = 625.

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

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

1. Для золотой медали можно выбрать любую из 8 команд.
2. Для серебряной и бронзовой медалей также остаётся по 8 вариантов, поскольку команда может получить несколько наград.
3. Умножаем: 8 · 8 · 8 = 8³ = 512.

Ответ: 512 вариантов. При обычном распределении медалей одна команда не получает две награды; тогда повторения запрещены, и получилось бы 8 · 7 · 6 = 336 вариантов.

Типичные ошибки

Считать выборы без учёта порядка — значит объединять разные последовательности в одну. Так ошибаются, когда видят одинаковые элементы, но забывают, что у них разные позиции; например, 12 и 21 — не один и тот же код. Проверь себя: если поменять элементы местами, изменится ли результат задачи? Если да, порядок нужно учитывать.

Использовать формулу nᵏ, когда повторения запрещены, нельзя: она предполагает, что на каждой позиции сохраняются все n вариантов. Эту ошибку допускают, если ориентируются только на длину последовательности и не читают условие о повторении. Проверь число вариантов для второй позиции: если выбранный элемент уже нельзя использовать, там будет n − 1, а не n.

Считать, что повторение обязательно, — неверно: разрешение повторять элемент не заставляет выбирать его снова. Путаница возникает из-за слов «с повторениями», которые описывают возможность, а не обязательное свойство каждой последовательности. Проверь условие формулы: в подсчёт входят и последовательности с одинаковыми, и последовательности с различными элементами.

Путать n и k — значит неверно определить основание или показатель степени. Обычно n принимают за длину последовательности, а k — за число доступных элементов, потому что позиции и элементы легко смешать. Проверь обозначения по смыслу: n — сколько разных вариантов есть на одной позиции, k — сколько позиций заполнить; потому ответ равен nᵏ.

Связь с другими темами

Для подсчёта размещений с повторениями нужно правило умножения: оно помогает объединить результаты независимых последовательных выборов. С размещениями без повторений тема связана сравнением двух ситуаций: в одном случае выбор сужает возможности, в другом — нет. Формула nᵏ применяется в задачах о кодах и словах заданной длины, а также при подсчёте исходов последовательных испытаний с одинаковым числом вариантов.

Что запомнить

• В размещении важен порядок элементов.
• При повторениях один и тот же элемент можно использовать несколько раз.
• n — число доступных элементов, k — длина последовательности.
• Число размещений с повторениями равно nᵏ.
• Для каждой позиции имеется n вариантов.
• Повторения разрешены, но не обязательны.