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

До сих пор мы рассматривали комбинации, в которых элементы не повторялись, то есть каждый из них можно было взять в выборку только один раз. Если же это ограничение убрать, то получим еще три вида комбинаций: перестановки, размещения и сочетания с повторениями. Рассмотрим, например, слово "КВАНТ", состоящее из пяти различных букв. Если менять порядок букв, получим 5! =120 перестановок, т.е. 120 новых слов. (Словом будем называть любую комбинацию букв). Если проделать то же со словом "АТАКА", то перестановок будет меньше, потому что, меняя местами первую, третью и пятую буквы, будем получать то же самое слово. И, так как три буквы "А" можно менять местами 3! = 6 способами, то и перестановок в слове "АТАКА" будет в 6 раз меньше.

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

состоящая из n элементов, причем, элемент а повторяется m₁ раз, элемент b - m₂ раз, и т.д., элемент с - m_k раз и m₁ + m₂ +...+ m_k = n. Перестановки в такой выборке, где есть одинаковые элементы, называются перестановками с повторениями и число перестановок с повторениями обозначается P_n(m₁,m₂,....,m_k) Из приведенных выше рассуждений следует формула:

    (1.8)

Пример 7.1. Сколькими способами можно расставить белые фигуры (2 ладьи, 2 коня, 2 слона, ферзь и король) на первой линии шахматной доски?

Решение.Первая линия шахматной доски представляет собой 8 клеток, на которых и надо расположить эти 8 фигур. Различные варианты расположения будут отличаться только порядком фигур, значит, это будут перестановки с повторениями Р₈ (2,2,2). По формуле:

Ответ: 5040 способами

Пример 7.2. У мамы 2 яблока, 3 груши и 4 апельсина. Каждый день в течение девяти дней она выдает сыну по одному фрукту. Сколько может быть вариантов такой выдачи? Решение. Обозначая фрукты по первым буквам названия, составим несколько вариантов выдачи: ЯЯГГГАААА, ААГГЯГААЯ, ГГГААЯЯАА. Эти выборки имеют один и тот же состав и отличаются только перестановкой элементов, поэтому применяем формулу числа перестановок с повторениями.

Ответ: 1260 вариантов

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

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

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

   (1.9)

Пример 8.1.Сколько четырехбуквенных "слов" можно составить из букв "М" и "А"? Результат проверить непосредственно.

Решение. Составим несколько таких "слов". МММА, МАМА, МААА ...Мы видим, что состав выборки меняется, порядок элементов в выборке существенен. Значит, это - размещения с повторениями из 2 букв "М" и "А" по 4 буквы. Выпишем непосредственно все эти 16 "слов":

ММММ, МММА, ММАМ, МАММ, АМММ, ММАА, МАМА, АММА, АМАМ, ААММ, МААМ, АМАА, ААМА, АААМ, МААА, АААА.

Ответ: 16 слов.

Пример 8.2. Вдоль дороги стоят 6 светофоров. Сколько может быть различных комбинаций их сигналов, если каждый светофор имеет 3 состояния: "красный", "желтый", "зеленый"?

Решение. Выпишем несколько комбинаций: КККЖЗЗ, ЗЗЗЗЗЗ, КЖЗКЖЗ... Мы видим, что состав выборки меняется и порядок элементов существенен (ведь если, например, в выборке КЖЗКЖЗ поменять местами К и Ж, ситуация на дороге будет другой). Поэтому применяем формулу размещений с повторениями из 3 по 6: Ответ: 729 комбинаций