Задача подсчёта числа вариантов

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

Математика, 7 класс · Л. Г. Петерсон, Д. Л. Абраров, Е. В. Чуткова

Комбинаторика — раздел математики, который изучает, сколькими способами можно выбрать и расположить элементы конечного множества: переставить их, выбрать некоторые из них, составить из них комбинации с заданными свойствами. Такие задачи называют задачами подсчёта числа вариантов.

Пример 1. Сколькими способами четверо друзей — Аня, Боря, Вера и Гена — могут встать в очередь в кассу?

Сначала поставим первой Аню и построим дерево возможностей. Вторым может стоять Б, В или Г — три ветки. Если вторым стоит Б, то третьим — В или Г, а последним — тот, кто остался; так же, если вторым стоит В или Г. Получается 3 · 2 = 6 очередей с Аней впереди: АБВГ, АБГВ, АВБГ, АВГБ, АГБВ, АГВБ. Первым может стоять любой из четверых, и для каждого из них тоже получится 6 очередей. Всего 6 · 4 = 24 способа.

Метод систематического перебора (комбинации из различных элементов):

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

Правило произведения. Если первый элемент комбинации можно выбрать m способами и при каждом таком выборе второй элемент — n способами, то пару можно составить m · n способами; для трёх элементов — m · n · k способами и т. д. Например, n различных предметов можно расставить в ряд n · (n - 1) · … · 2 · 1 способами: пять книг — 5 · 4 · 3 · 2 · 1 = 120 способами.

Пример 2 (перебор с ограничениями). В столовой на первое можно взять суп или салат, на второе — котлету, рыбу или плов, на третье — чай или компот. Компот к рыбе не подают, а суп не берут вместе с пловом. Сколько различных обедов из трёх блюд можно составить?

Дерево возможностей: суп — котлета (чай или компот), рыба (только чай): 3 обеда; салат — котлета (чай или компот), рыба (только чай), плов (чай или компот): 5 обедов. Всего 3 + 5 = 8 обедов.

Пример 3 (магический квадрат). Квадрат 3 × 3 называют магическим, если суммы чисел во всех его строках, столбцах и обеих диагоналях одинаковы. Сколькими способами можно расставить в нём числа 5, 6, …, 13?

Сумма всех чисел 81, значит, сумма в каждой строке 81 : 3 = 27. Троек различных чисел с суммой 27 ровно восемь — столько же, сколько строк, столбцов и диагоналей (3 + 3 + 2), поэтому каждая тройка занимает свою линию. Число в центре входит в четыре линии, в углу — в три, остальные — в две. В четыре тройки входит только 9 — оно стоит в центре; в три — 6, 8, 10, 12 — они стоят в углах. В левый верхний угол можно поставить любое из этих четырёх чисел, тогда противоположный угол определён (диагональ через 9), а в правый верхний угол — одно из двух оставшихся. Остальные клетки заполняются однозначно, и получается 4 · 2 = 8 магических квадратов.

Определение

1 / 13

Комбинаторика

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

Такие задачи называют задачами подсчёта числа вариантов.

Наглядно

2 / 13

Дерево возможностей

Дерево возможностей: вверху А; от неё три ветки Б, В, Г; от каждой две ветки к оставшимся двоим; от каждой из них одна ветка к последнему. Внизу шесть концов — шесть очередей с Аней впереди.
Дерево возможностей: вверху А; от неё три ветки Б, В, Г; от каждой две ветки к оставшимся двоим; от каждой из них одна ветка к последнему. Внизу шесть концов — шесть очередей с Аней впереди.

Аня первая: вторым — Б, В или Г, третьим — один из двух оставшихся. Очередей 3 · 2 = 6.

Разбор

3 / 13

Вся очередь

Сколькими способами Аня, Боря, Вера и Гена могут встать в очередь в кассу?

  1. Аня первая

    АБВГ, АБГВ, АВБГ, АВГБ, АГБВ, АГВБ — 6 очередей

  2. Любой первый

    Первым может стоять любой из четверых, у каждого по 6 очередей

  3. Ответ

    6 · 4 = 24 способа

Правило

4 / 13

Систематический перебор

Для комбинаций из различных элементов:

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

Проверь себя

5 / 13

Очередь из троих

Закрепи первого и посчитай варианты для него.

Сколькими способами трое могут встать в очередь?

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

Первый — любой из 3, для него 2 варианта: 3 · 2 = 6.

Формула

6 / 13

Правило произведения

Если первый элемент можно выбрать m способами и при каждом таком выборе второй — n способами, то пару можно составить

m · n

способами; для трёх элементов — m · n · k способами и так далее.

Пример

7 / 13

Предметы в ряд

n различных предметов можно расставить в ряд

n · (n - 1) · … · 2 · 1

способами. Пять книг — 5 · 4 · 3 · 2 · 1 = 120 способами.

Проверь себя

8 / 13

Четыре книги

Каждое следующее место — на один вариант меньше.

Сколькими способами можно расставить на полке 4 разные книги?

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

4 · 3 · 2 · 1 = 24.

Разбор

9 / 13

Перебор с ограничениями

Первое — суп или салат; второе — котлета, рыба или плов; третье — чай или компот. Компот к рыбе не подают, а суп не берут с пловом. Сколько разных обедов из трёх блюд?

  1. Суп

    Суп: котлета (чай или компот), рыба (только чай) — 3 обеда

  2. Салат

    Салат: котлета (2), рыба (1), плов (2) — 5 обедов

  3. Ответ

    3 + 5 = 8 обедов

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

10 / 13

Умножили, не глядя

Ошибка: обедов 2 · 3 · 2 = 12.

Проверим: суп с пловом нельзя — 2 обеда, рыба с компотом нельзя — ещё 2: 12 - 4 = 8.

При ограничениях число вариантов для второго зависит от первого: считают по случаям и складывают.

Определение

11 / 13

Магический квадрат

Квадрат 3 × 3 называют магическим, если суммы чисел во всех его строках, столбцах и обеих диагоналях одинаковы. Пример с числами 5, 6, …, 13:

61110
1395
8712

Разбор

12 / 13

Сколько магических квадратов

Сколькими способами можно расставить в квадрате 3 × 3 числа 5, 6, …, 13 так, чтобы он был магическим?

  1. Сумма

    Сумма всех чисел 81, в каждой строке 81 : 3 = 27

  2. Тройки

    Троек с суммой 27 ровно 8 — столько же, сколько линий: 3 + 3 + 2

  3. Центр и углы

    9 входит в 4 тройки — в центр; 6, 8, 10, 12 — в три, в углы

  4. Ответ

    Левый верхний угол — 4 способа, правый верхний — 2: 4 · 2 = 8

Главное

13 / 13

Главное

  • Систематический перебор: закрепить первого, посчитать деревом, умножить
  • Правило произведения: m · n, m · n · k
  • n предметов в ряд: n · (n - 1) · … · 1
  • Ограничения — считать по случаям и складывать

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

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

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