Перестановки, размещения и сочетания

8–11 класссредне

Комбинаторика

Правило умножения в клетках: $n$ способов для первого выбора, $n - 1$ для второго… Размещения помнят порядок, сочетания — нет, и каждое сочетание — это $k!$ размещений. Небольшие случаи перечислены целиком.

ЕГЭ профилькомбинаторикаперестановкиразмещениясочетанияфакториал

Тренировать: Комбинаторика

51-й

42-й

33-й

$A_{5}^{3} = \frac{5!}{(5 - 3)!} = 5 \cdot 4 \cdot 3 = 60$

Все варианты: 60

АБВАБГАБДАВБАВГАВДАГБАГВАГДАДБАДВАДГБАВБАГБАДБВАБВГБВДБГАБГВБГДБДАБДВБДГВАБВАГВАДВБАВБГВБДВГАВГБВГДВДАВДБВДГГАБГАВГАДГБАГБВГБДГВАГВБГВДГДАГДБГДВДАБДАВДАГДБАДБВДБГДВАДВБДВГДГАДГБДГВ

n — сколько всего

k — сколько выбираем

Перестановки — все n предметов по порядку: $P_n = n!$ .

Размещения — k из n, порядок важен (капитан и заместитель): $A_n^k = \frac{n!}{(n-k)!}$ .

Сочетания — k из n, порядок не важен (два дежурных): каждое сочетание — это $k!$ размещений, поэтому $C_n^k = \frac{A_n^k}{k!}$ .

Теория

Правила умножения и сложения

Если первый выбор можно сделать $n$ способами, а после него второй — $m$ способами, то пару — $nm$ способами.
Если выбирают одно из двух непересекающихся множеств — $n + m$ способов.

Формулы

Перестановки — сколькими способами упорядочить $n$ предметов: $P_n = n!$ .
Размещения — выбрать $k$ из $n$ с учётом порядка: $A_n^k = \frac{n!}{(n - k)!} = n(n - 1)\dots(n - k + 1)$ .
Сочетания — без учёта порядка: $C_n^k = \frac{n!}{k!\,(n - k)!}$ ; каждое сочетание — $k!$ размещений.
$C_n^k = C_n^{n - k}$ , $0! = 1$ .

Как понять, что считать

Важен ли порядок? Староста и заместитель — да (размещения); двое дежурных — нет (сочетания).
Можно ли повторять? Код из четырёх цифр — $10^4$ вариантов, цифры могут повторяться.

Связь с вероятностью

В $P = \frac{m}{n}$ числа исходов часто считают сочетаниями. Вероятность выбрать двух девочек из 5 девочек и 3 мальчиков: $\frac{C_5^2}{C_8^2} = \frac{10}{28} = \frac{5}{14}$ .

Частые ошибки

Путают размещения и сочетания.
При выборе с повторениями пользуются $n!$ .