Основные правила комбинаторики

  • 3 мин чтения

Алгебра, 9 класс · А. Г. Мерзляк, В. Б. Полонский, М. С. Якир · § 17. Основные правила комбинаторики

Область математики, которая занимается подсчётом комбинаций, образованных по определённому правилу из элементов конечного множества, называют комбинаторикой. В основе решения большинства комбинаторных задач лежат два правила.

Туриста заинтересовали 5 маршрутов в Карелии и 7 маршрутов на Кавказе. Если у него есть время на один маршрут, то выбрать его можно 5 + 7 = 12 способами.

Правило суммы. Если множество A состоит из m элементов, а множество B — из k элементов, причём эти множества не имеют общих элементов, то выбор «a или b», где a ∈ A, b ∈ B, можно осуществить m + k способами.

Если у туриста есть время на два маршрута и он хочет побывать сначала в Карелии, а затем на Кавказе, то к каждому из пяти карельских маршрутов парой может быть любой из семи кавказских. Всего 7 · 5 = 35 способов.

Правило произведения. Если элемент a можно выбрать m способами и после каждого такого выбора элемент b можно выбрать k способами, то выбор «a и b» в указанном порядке можно осуществить mk способами.

Оба правила обобщаются на три и более множества.

Пример 1. Из класса, в котором учатся 28 человек, надо выбрать трёх дежурных — по одному на каждый из трёх этажей школы. Дежурного по первому этажу можно выбрать 28 способами, по второму — 27, по третьему — 26. Всего 28 · 27 · 26 = 19 656 способов.

Пример 2. Сколько натуральных делителей имеет число 2000? Имеем 2000 = 2⁴ · 5³. Любой делитель имеет вид 2^m · 5^k, где 0 ≤ m ≤ 4, 0 ≤ k ≤ 3. Число m можно выбрать 5 способами, число k — 4 способами. Значит, делителей 5 · 4 = 20.

Пример 3. Пароль — последовательность букв и цифр длиной от трёх до пяти символов, символы могут повторяться. Сколько разных паролей можно придумать из 26 букв и 10 цифр? Паролей из трёх символов 36³, из четырёх — 36⁴, из пяти — 36⁵. По правилу суммы всего 36³ + 36⁴ + 36⁵ паролей.

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

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

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