Сочетания

Сочетанием из $n$ элементов по $k$ называют любую группу из $k$ элементов, составленную из данных $n$ элементов. Число сочетаний — $C_n^k$.

Отличие от размещения: если в размещении поменять элементы местами, получится другое размещение; сочетание от порядка элементов не зависит. $\{x_1, x_2\}$ и $\{x_2, x_1\}$ — одно сочетание, но два размещения.

Каждое сочетание из $k$ элементов можно упорядочить $P_k = k!$ способами — получим $k!$ разных размещений. Поэтому $A_n^k = k! \cdot C_n^k$, откуда и формула.

Удобное свойство: $C_n^k = C_n^{n-k}$ — выбрать $k$ элементов то же, что выбрать $n - k$ оставшихся.

1. Порядок в команде не важен — сочетания: $C_7^2 = \dfrac{A_7^2}{2!} = \dfrac{7 \cdot 6}{2} = 21$.
2. Сравните с размещением: $A_7^2 = 42$ — каждая команда посчитана дважды.

1. а) $C_8^3 = \dfrac{8 \cdot 7 \cdot 6}{3!} = \dfrac{336}{6} = 56$.
2. б) $C_{27}^2 = \dfrac{27 \cdot 26}{2} = 351$.

1. Мальчиков — $C_{12}^3 = 220$ способов, девочек — $C_{15}^4 = 1365$.
2. Нужна и тройка мальчиков, и четвёрка девочек — правило умножения: $220 \cdot 1365 = 300\,300$.

• Сочетание — группа без порядка; $C_n^k = \dfrac{A_n^k}{k!} = \dfrac{n!}{k!(n - k)!}$.
• $C_n^2 = \dfrac{n(n - 1)}{2}$ — пары, отрезки, рукопожатия, партии турнира.
• $C_n^k = C_n^{n-k}$.
• Несколько независимых выборов — перемножаем числа способов.