Вычисление сочетаний

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

Предположим, что мы уже определили: в задаче нужно использовать сочетания.
Иногда варианты ответа сразу даны в виде, например, 50C10, и тогда ничего вычислять не нужно — достаточно распознать правильную форму. Это особенно характерно для очень больших чисел.

Экзамен не ожидает, что вы будете вычислять громоздкие значения. В таких случаях ответ намеренно оставляют в виде nCr.

Однако гораздо чаще требуется реально посчитать значение сочетания.

Почему стандартная формула — не лучший инструмент

Существует формула для сочетаний, содержащая несколько факториалов. Но важно понимать:

• эта формула изначально предполагает огромный объём вычислений,

   

• если начать отдельно считать факториалы, задача станет в разы сложнее,

   

• формула не является самым эффективным способом решения задач на сочетания.

   

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

Рекомендуемый подход (экзаменационный)

Самый эффективный и надёжный метод:

1. Начать с основного принципа подсчёта (FCP)

    

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

    

3. Всегда сокращать ДО умножения

    

4. Не перемножать ничего заранее, пока не выполнено всё возможное сокращение

    

Правило номер один:

Всегда сокращай, прежде чем умножать.

Частный, но очень полезный случай: nC2

Когда требуется выбрать неупорядоченную пару из n объектов:

• n вариантов для первого,

   

• n − 1 вариантов для второго,

   

• но порядок не важен → делим на 2.

   

Получаем универсальную формулу:

nC2 = n(n − 1) / 2

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

Альтернативный инструмент: треугольник Паскаля

Есть ещё один способ вычислять сочетания — треугольник Паскаля.
Некоторые его любят, другие — нет. Это вопрос удобства, а не обязательный навык.

Основная идея

• по краям треугольника стоят единицы,

   

• каждое число внутри — это сумма двух чисел над ним по диагонали,

   

• треугольник содержит все значения nCr.

   

Интерпретация

• nCr — это число в n-й строке на r-й позиции,

   

• строки и позиции считаются, начиная с нуля.

   

Например, в строке n = 7 находятся все значения:

• 7C0, 7C1, 7C2, 7C3, 7C4, 7C5, 7C6, 7C7

   

Если потренироваться строить треугольник Паскаля, можно очень быстро находить значения для n до 7–8.

Он особенно удобен, если:

• нужно найти несколько сочетаний из одного и того же n (например, 8C3 и 8C4).

   

Но если вам этот метод не нравится — не используйте его. Это необязательный инструмент.

Пример. Отношение двух сочетаний

В компании нужно выбрать 3 сертифицированных специалиста.

• Сначала таких специалистов было 6 → число комитетов = N1 = 6C3

   

• Затем стало 8 → число комитетов = N2 = 8C3

   

Найти отношение N2 / N1.

Решение через FCP (рекомендуемый способ)

6C3:

• 6 × 5 × 4

   

• делим на 3! = 6

   

После сокращения:

5 × 4 = 20

8C3:

• 8 × 7 × 6

   

• делим на 3! = 6

   

После сокращения:

8 × 7 = 56

Отношение

56 / 20

Сократим на 4:

14 / 5

Альтернативное решение (через треугольник Паскаля)

• 6C3 = 20

   

• 8C3 = 56

   

Отношение снова:

14 / 5

Оба способа корректны — выбирайте тот, который быстрее и понятнее именно вам.

Выводы

• Сочетания всегда можно вычислять через:

   

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

     

  • деление для устранения повторов.

     

• Этот метод:

   

  • быстрее,

     

  • надёжнее,

     

  • эффективнее, чем подстановка в громоздкую формулу.

     

• Ключевые правила:

   

  • всегда сокращать до умножения,

     

  • помнить формулу nC2 = n(n − 1) / 2,

     

  • использовать треугольник Паскаля только если он вам действительно помогает.

     

Экзамен GMAT и GRE проверяет понимание структуры подсчёта, а не умение механически применять формулы.

Изучим далее перестановки и сочетания.