Сочетания

Сочетание – это выбор \(k\) объектов из \(n\), где порядок не важен.

Например, возможные команды из 3 человек, выбранные из \(A\),\(\;\) \(B\),\(\;\) \(C\),\(\;\) \(D\),\(\;\) \(E\):

\[ ABC,\quad ABD,\quad ABE,\quad ACD,\quad ACE,\quad ADE,\quad BCD,\quad BCE,\quad BDE,\quad CDE \]

Здесь мы перечисляем только \(ABC\), а не \(ACB\),\(\;\) \(BAC\),\(\;\) \(BCA\),\(\;\) \(CAB\),\(\;\) \(CBA\): это разные перестановки одних и тех же трёх букв, но одно и то же сочетание.

Мы видим, что сочетаний из 5 букв по 3 ровно 10, то есть

\[ \binom{5}{3} = 10 \]

Число перестановок из 5 букв по 3 равно

\[ 5 \times 4 \times 3 = 60 \]

Оно в 6 раз больше, потому что каждое сочетание из 3 букв можно упорядочить \(3 \times 2 \times 1\) способами.

Значит,

\[ \binom{5}{3} = \frac{5 \times 4 \times 3}{3 \times 2 \times 1} = \frac{5 \times 4 \times 3 \times \color{red}{2 \times 1}}{3 \times 2 \times 1 \times \color{red}{2 \times 1}} = \frac{5!}{3!\,2!} = 10 \]

Число сочетаний из \(n\) по \(k\) (порядок не важен) обозначают биномиальным коэффициентом

\[ \binom{n}{k} = \frac{n!}{k!\,(n-k)!} \]

Читают: «из \(n\) выбрать \(k\)» или «\(n\) по \(k\)».

Иными словами, чтобы найти число сочетаний из \(n\) по \(k\), можно взять число размещений из \(n\) по \(k\) и разделить на \(k!\) (потому что порядок внутри выбранных \(k\) элементов не важен)

Разберем пример

Задача:

В классе 8 учеников. Сколькими способами можно выбрать команду из 3 человек?

---

Решение:

\[ \binom{8}{3} = \frac{8!}{3!\,5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56 \]

Ответ: \(56\)

Формулу можно не запоминать – её удобно каждый раз выводить логически.

Идея: сначала считаем все варианты (размещения), а затем убираем повторы, которые отличаются только порядком.

1) Тогда получаем размещения из\(\;\) \(8\) по\(\;\) \(3\):

\( 8 \times 7 \times 6 \)

Первый ученик выбирается \(8\) способами, затем остаётся \(7\), затем остаётся \(6\)

2) Но команда – это набор, порядок не важен. Одна и та же тройка учеников в пункте 1 посчитана несколько раз: её можно переставить \(3!\) способами

3) Поэтому делим результат пункта 1 на\(\;\) \(3!\) и получаем число команд:

\( \binom{8}{3} = \dfrac{8 \times 7 \times 6}{3 \times 2 \times 1} \)