Основной принцип подсчёта

Эта тема является частью раздела о комбинаторике в Quant GMAT Focus.

Fundamental Counting Principle — как следует из названия, это самый важный принцип во всём модуле Counting. По сути, он напрямую опирается на базовую идею:
слово «и» означает умножение.

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

Формулировка основного принципа подсчёта

Предположим, что некоторую задачу можно разбить на несколько последовательных этапов:

• первый этап можно выполнить n1 способами,
  
  
• второй этап — n2 способами,
  
  
• третий этап — n3 способами,
  
  
• и так далее.
  
  

Тогда общее количество способов выполнить всю задачу равно произведению количества вариантов на каждом этапе:

n1 × n2 × n3 × …

Это и есть основной принцип подсчёта.

Пример 1. Выбор блюд на ужине

На официальном ужине гости выбирают:

• 1 из 4 салатов,
  
  
• 1 из 5 закусок,
  
  
• 1 из 12 основных блюд,
  
  
• 1 из 4 десертов.
  
  

Каждый ужин состоит из салата, закуски, основного блюда и десерта.
Сколько различных вариантов полного ужина существует?

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

Применяем основной принцип подсчёта:

4 × 5 × 12 × 4

Считаем по шагам:

• 4 × 5 = 20
  
  
• 20 × 4 = 80
  
  
• 80 × 12 = 960
  
  

Ответ: 960 различных вариантов ужина.

Пример 2. Расстановка книг на полке

Допустим, есть 6 разных книг, которые нужно расставить на полке.
Сколькими различными способами это можно сделать?

Рассмотрим задачу по этапам:

• этап 1: выбор книги для первого места — 6 вариантов,
  
  
• этап 2: выбор книги для второго места — 5 вариантов (одна книга уже использована),
  
  
• этап 3: 4 варианта,
  
  
• этап 4: 3 варианта,
  
  
• этап 5: 2 варианта,
  
  
• этап 6: 1 вариант (остаётся последняя книга).
  
  

Общее количество способов:

6 × 5 × 4 × 3 × 2 × 1

Упростим:

• 3 × 2 = 6
  
  
• 5 × 4 = 20
  
  
• 20 × 6 = 120
  
  
• 6 × 120 = 720
  
  

Ответ: 720 различных порядков расстановки книг.

Общий вывод для упорядочивания элементов

Если нужно упорядочить n различных объектов без ограничений, то число возможных порядков равно произведению:

n × (n − 1) × (n − 2) × … × 1

Позже мы введём для этого специальное обозначение (факториал), но пока важно понять саму логику.

Пример 3. Выбор комитета с разными ролями

В подразделении компании работают 25 сотрудников. Нужно выбрать комитет из 3 человек, причём роли различны:

• координатор,
  
  
• представитель профсоюза,
  
  
• секретарь.
  
  

Важно:
если Гарри — координатор, а Салли — представитель профсоюза,
это другой комитет, чем если роли поменять местами.
Порядок (роли) имеет значение.

Рассмотрим этапы:

• выбор координатора — 25 вариантов,
  
  
• выбор представителя профсоюза — 24 варианта,
  
  
• выбор секретаря — 23 варианта.
  
  

Общее количество комитетов:

25 × 24 × 23

Посчитаем:

• 25 × 24 = 600
  
  
• 600 × 23 = 13 800
  
  

Ответ: 13 800 различных комитетов.

Почему числа в комбинаторике быстро растут

Даже при относительно небольшом количестве объектов (например, 25 человек),
если учитывать разные роли и порядок, количество возможных вариантов очень быстро становится большим.

Именно поэтому одни из самых больших чисел в математике возникают в комбинаторике.

Выводы

• Основной принцип подсчёта применяется к задачам, которые можно разбить на этапы.
  
  
• Если на каждом этапе есть определённое количество вариантов, то:
  
  
  • общее число способов = произведение вариантов на каждом этапе.
    
    
• При упорядочивании n различных элементов без ограничений:
  
  
  • количество возможных порядков равно произведению n × (n − 1) × … × 1.
    
    
• В следующих уроках мы формализуем этот результат с помощью факториалов и специального обозначения.
  
  

Этот принцип — фундамент для всех последующих тем в комбинаторике GMAT и GRE Quant. Следующий урок будет посвящен изучению основного принципа подсчета.