Когда использовать сочетания

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

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

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

Прежде чем решать этот вопрос, важно понять, зачем мы вообще его задаём.

Почему вопрос о порядке принципиален

• Если порядок имеет значение, мы:

   

  • разбиваем задачу на этапы,

     

  • считаем варианты на каждом этапе,

     

  • применяем основной принцип подсчёта (FCP) без деления.

     

• Если порядок не имеет значения, мы:

   

  • начинаем с FCP,

     

  • а затем делим, чтобы устранить повторения,

     

  • то есть используем подход сочетаний.

     

Таким образом, вся разница между перестановками и сочетаниями сводится к одному вопросу:
делим мы на повторения или нет.

Как правильно понимать «порядок имеет значение»

Рассмотрим пример.

Пример 1. Выбор руководства комитета

Есть 20 членов комитета, и нужно выбрать трёх должностных лиц:

• председателя,

   

• казначея,

   

• секретаря.

   

Имеет ли порядок значение?

Некоторые студенты ошибочно отвечают «нет», аргументируя это тем, что неважно, кого выбрали первым или вторым.
Но это неправильный способ думать.

Правильный подход — ориентироваться на результат

Посмотрите на итоговую конфигурацию.

Допустим:

• B — председатель,

   

• N — казначей,

   

• F — секретарь.

   

Если мы поменяем роли:

• F — председатель,

   

• B — казначей,

   

• N — секретарь,

   

мы получим совершенно другую команду руководства.

Результат изменился значимо, следовательно:

Порядок имеет значение.

Решение

Так как порядок важен, мы используем обычный FCP:

• 20 вариантов для председателя,

   

• 19 — для казначея,

   

• 18 — для секретаря.

   

Ответ остаётся в виде произведения:

20 × 19 × 18

(Экзамен часто даже не требует перемножать эти числа.)

Пример 2. Выбор овощей для супа

Шеф-повар готовит суп.
У него есть 20 различных овощей, и он должен выбрать любые 3, нарезать их и положить в одну кастрюлю.

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

Здесь суп полностью определяется набором овощей.
Не имеет никакого значения:

• какой овощ был выбран первым,

   

• вторым или третьим.

   

Все овощи нарезаются и перемешиваются — порядок полностью теряет смысл.

Порядок не имеет значения → это сочетание.

Решение

Используем сочетания:

20C3 = (20 × 19 × 18) / 3!

3! = 6

Сократим:

• 18 / 6 = 3

   

Получаем:

20 × 19 × 3

• 3 × 19 = 57

   

• 20 × 57 = 1140

   

Ответ: 1140 различных супов.

Почему нет универсального правила

Важно понимать:
не существует чёрно-белого правила, по которому всегда можно механически определить, имеет ли порядок значение.

Есть лишь ориентиры и способы мышления.

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

Как «увидеть» задачу правильно

В комбинаторике ключевой момент — как вы смотрите на задачу до начала вычислений:

• что именно считается результатом,

   

• какие различия считаются существенными,

   

• что считается одним и тем же исходом.

   

Очень полезно:

• внимательно разбирать решения,

   

• отслеживать, как автор решения изначально интерпретировал ситуацию,

   

• какие допущения были сделаны до любых вычислений.

   

Если вы сразу правильно «увидели» задачу, само решение обычно становится очевидным.

Пример 3. Музыкальная программа концерта

Концерт состоит из:

• двух увертюр в первом отделении,

   

• одной симфонии во втором отделении.

   

Программа определяется именно этими произведениями.

Дано:

• 10 возможных увертюр,

   

• 6 возможных симфоний.

   

Сколько различных программ можно составить?

Решение

1. Выбираем 2 увертюры из 10 — порядок между ними не важен:

    

10C2 = (10 × 9) / 2 = 45

1. Выбираем 1 симфонию из 6 — 6 вариантов.

    

Теперь используем слово «и», значит умножаем:

45 × 6

Упростим:

• 45 × 6 = 270

   

Ответ: 270 возможных программ.

Пример 4. Книги с обязательным блоком

Есть 10 книг, среди них:

• 4 разные книги про Авраама Линкольна.

   

Условие:
четыре книги про Линкольна должны стоять все вместе, но место этого блока на полке не фиксировано.

Решение

1. Рассматриваем 4 книги про Линкольна как один «большой объект».

    

2. Тогда всего объектов:

    

   • 6 обычных книг,

      

   • 1 «блок Линкольна» → всего 7 объектов.

      

Число способов расставить их:

7!

1. Внутри блока книги про Линкольна можно переставлять:

    

4! способов.

Итоговое количество расстановок:

(7!) × (4!)

Это выражение нельзя упростить дальше, его так и оставляют.

Итоговые ориентиры

• Если порядок имеет значение:

   

  • разбиваем задачу на этапы,

     

  • используем обычный FCP.

     

• Если порядок не имеет значения:

   

  • используем подход сочетаний,

     

  • начинаем с FCP,

     

  • затем делим, чтобы устранить повторения.

     

• Полезный мысленный тест:

   

  • если перестановка элементов в итоговом результате меняет смысл результата, порядок важен;

     

  • если не меняет — порядок не важен.

     

• Самый важный навык — умение правильно увидеть и сформулировать задачу до начала вычислений.

   

Именно этому навыку экзамен GMAT и GRE уделяет наибольшее внимание в разделе Counting. Далее рассмотрим как проводить вычисление сочетаний.