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

  • 5 мин чтения
  • Послушать — 3 мин
  • 10 карточек

Алгебра, 9 класс · Л. Г. Петерсон, Н. Х. Агаханов, А. Ю. Петрович, О. К. Подлипский, М. В. Рогатова, Б. В. Трушин · § 1. Элементы комбинаторики и теории вероятностей

Из 8 класса известно: n различных элементов можно упорядочить P_n = n! = 1 · 2 · … · n способами. А если среди элементов есть одинаковые? Перестановка двух одинаковых элементов ничего не меняет, поэтому вариантов станет меньше.

Задача. Сколько четырёхзначных кодов можно получить, переставляя карточки 1, 2, 2, 2?

Сделаем одинаковые карточки на время «разными» — покрасим двойки в три цвета. Тогда все четыре карточки различны и кодов 4! = 24. Но в настоящей задаче двойки одного цвета: каждый код, например 2122, получается из 3! = 6 «цветных» кодов — столько способов переставить между собой три двойки. Значит, настоящих кодов в 6 раз меньше: 24 : 6 = 4 (это 1222, 2122, 2212, 2221).

Правило. Если среди n элементов первый встречается k₁ раз, второй — k₂ раз, …, последний — k_m раз (k₁ + k₂ + … + k_m = n), то различных перестановок

P(k₁, k₂, …, k_m) = (n!)/(k₁! · k₂! · … · k_m!).

Неповторяющемуся элементу отвечает множитель 1! = 1, его можно не писать. Если повторов нет совсем, формула превращается в P_n = n! — значит, она годится для любых перестановок.

Пример 1. Сколько семизначных номеров можно составить из цифр 1, 1, 2, 2, 3, 3, 3? Всего 7 цифр, двойка и единица повторяются по 2 раза, тройка — 3 раза: (7!)/(2! · 2! · 3!) = 5040/24 = 210.

Пример 2. Сколько «слов» (любых наборов букв) получится, если переставлять буквы слова «КОЛОКОЛ»? Букв 7: К — 2 раза, О — 3 раза, Л — 2 раза: (7!)/(2! · 3! · 2!) = 210.

Типичная ошибка — разделить только на один факториал, забыв про другие повторяющиеся элементы, или разделить на число повторов вместо его факториала.

Зачем это

1 / 10

Одинаковые элементы

Из 8 класса: n различных элементов можно упорядочить P_n = n! способами.

А если среди элементов есть одинаковые? Буквы А и Б дают две перестановки: АБ и БА. А две буквы А — только одну: АА.

Поменять местами одинаковые элементы — ничего не изменить, поэтому вариантов меньше.

Разбор

2 / 10

Коды из карточек

Сколько четырёхзначных кодов можно получить, переставляя карточки 1, 2, 2, 2?

  1. Цвета

    Покрасим двойки в три цвета: все карточки разные, кодов 4! = 24.

  2. Склейка

    Код 2122 получается из 3! = 6 цветных: столько способов переставить три двойки.

  3. Ответ

    24 : 6 = 4 кода: 1222, 2122, 2212, 2221.

Проверь себя

3 / 10

Пять карточек

Переставляем карточки 3, 3, 3, 3, 5.

Сколько разных кодов?

120305
Ответ и объяснение

(5!)/(4!) = 120/24 = 5: пятёрка стоит на одном из пяти мест.

Формула

4 / 10

Общее правило

Среди n элементов первый встречается k₁ раз, второй — k₂ раз, …, последний — k_m раз, k₁ + k₂ + … + k_m = n. Различных перестановок

P(k₁, …, k_m) = (n!)/(k₁! · … · k_m!)

Свойство

5 / 10

Один раз — множитель 1

Элемент встречается один раз — ему отвечает 1! = 1, его можно не писать:

АББВ: (4!)/(1! · 2! · 1!) = (4!)/(2!) = 12

Повторов нет совсем — формула даёт (n!)/(1 · … · 1) = n! = P_n. Она годится для любых перестановок.

Разбор

6 / 10

Семизначные номера

Сколько семизначных номеров можно составить из цифр 1, 1, 2, 2, 3, 3, 3?

  1. Подсчёт

    n = 7: единица — 2 раза, двойка — 2 раза, тройка — 3 раза; 2 + 2 + 3 = 7.

  2. Формула

    (7!)/(2! · 2! · 3!) = 5040/24

  3. Ответ

    210 номеров.

Пример

7 / 10

Слово КОЛОКОЛ

Сколько «слов» (любых наборов букв) получится, если переставлять буквы слова «КОЛОКОЛ»?

Букв 7: К — 2 раза, О — 3 раза, Л — 2 раза.

(7!)/(2! · 3! · 2!) = 210

Проверь себя

8 / 10

Слово АНАНАС

Переставляем буквы слова «АНАНАС»: А — 3 раза, Н — 2 раза, С — 1 раз.

Сколько «слов»?

72012060
Ответ и объяснение

(6!)/(3! · 2!) = 720/12 = 60.

Частая ошибка

9 / 10

Не тот знаменатель

Карточки 1, 2, 2, 2: «кодов (4!)/3 = 8» — неверно! Перебор даёт только 4 кода.

«КОЛОКОЛ: (7!)/(3!) = 840» — неверно! Забыты повторы К и Л.

Делим на факториалы повторов, и всех групп сразу.

Главное

10 / 10

Главное

  • Одинаковые элементы — вариантов меньше, чем n!.
  • P(k₁, …, k_m) = (n!)/(k₁! · … · k_m!), k₁ + … + k_m = n.
  • Одиночный элемент: 1! = 1; без повторов — P_n = n!.
  • Делим на факториалы всех повторов.

Проверь себя: тест по теме

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

  • Задания из этого учебника
  • Ответ проверяется сразу
  • Без регистрации
Начать тест