Сочетания

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

Тема combinations — одна из ключевых в комбинаторике. До этого момента мы в основном рассматривали задачи, где имел значение порядок выбора. Однако во многих задачах порядок не важен.

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

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

Когда порядок не имеет значения

Рассмотрим пример.
Есть 6 сотрудников одинакового статуса, и нужно выбрать 3 из них для задания. Пусть выбраны B, E и F.

Не имеет никакого значения:

• выбрали ли сначала B, потом E и F,

   

• или сначала F, затем B и E,

   

• или в любом другом порядке.

   

Важно только итоговое множество {B, E, F}.
В задачах на сочетания порядок выбора полностью игнорируется.

Обозначение сочетаний

Если:

• есть n различных объектов,

   

• и мы выбираем r объектов,

   

то количество сочетаний обозначается как:

nCr,
читается: «n выбрать r».

Пример:

• 8C3 — количество различных групп из 3 человек, которые можно выбрать из 8.

   

Базовые свойства сочетаний

Свойство 1: выбор одного элемента

Рассмотрим 7C1.
Это означает: выбрать одного человека из группы из 7.

Очевидно, это можно сделать 7 способами.
Следовательно:

• nC1 = n

   

Это важное базовое свойство.

Свойство 2: симметрия сочетаний

Рассмотрим 10C4 — число способов выбрать 4 человека из 10.

Обратите внимание:
каждый раз, когда мы выбираем группу из 4 человек, автоматически остаётся группа из 6 человек, которые не были выбраны.

Между:

• группами из 4 выбранных

   

• и группами из 6 оставшихся

   

существует взаимно однозначное соответствие.

Следовательно:

• 10C4 = 10C6

   

Аналогично:

• 10C3 = 10C7

   

• 10C2 = 10C8

   

В общем виде:

• nCr = nC(n − r)

   

Это очень важная формула симметрии сочетаний.

Как вычислять сочетания

Рассмотрим, как найти значение 10C4.

Шаг 1. Используем основной принцип подсчёта (FCP)

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

• 10 вариантов для первого выбора,

   

• 9 — для второго,

   

• 8 — для третьего,

   

• 7 — для четвёртого.

   

Получаем:

10 × 9 × 8 × 7

Шаг 2. Устраняем повторный подсчёт

Но порядок не важен, поэтому каждый набор из 4 человек был посчитан:

• 4! раз

   

Следовательно, нужно разделить на 4!:

10C4 = (10 × 9 × 8 × 7) / 4!

Шаг 3. Вычисление

Сократим:

• 4! = 4 × 3 × 2

   

• сокращаем 9 с 3 → 3

   

Получаем:

10 × 3 × 7 = 210

Ответ: 10C4 = 210

По симметрии сразу получаем:

• 10C6 = 210

   

Пример задачи

Есть 12 различных аттракционов, и можно выбрать любые 3.

Сколько различных наборов из 3 аттракционов существует?

Это задача на сочетания:

12C3

Решение

Сначала считаем с учётом порядка:

12 × 11 × 10

Затем устраняем повторения, деля на 3!:

12C3 = (12 × 11 × 10) / 6

Сократим:

• 12 / 6 = 2

   

Получаем:

2 × 11 × 10 = 220

Ответ: 220 различных наборов.

По симметрии:

• 12C9 = 220

   

Формула сочетаний и практический подход

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

• она громоздкая,

   

• редко нужна напрямую,

   

• и почти всегда сводится к тому же самому подходу через основной принцип подсчёта + устранение повторов.

   

На экзамене задачи часто наказывают механическое заучивание формул и поощряют понимание логики.

Выводы

• Сочетания — это выбор r объектов из n, где порядок не имеет значения.

   

• Обозначение: nCr.

   

• Ключевые свойства:

   

  • nC1 = n

     

  • nCr = nC(n − r) (симметрия).

     

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

   

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

     

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

     

Понимание сочетаний — критически важный этап в разделе Counting для GMAT и GRE Quant. Далее мы рассмотрим когда использовать сочетания.