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

Теория

Комбинаторика считает количество способов выбора и упорядочивания объектов. Три базовые величины: перестановки, размещения и сочетания. Перестановки \(P(n) = n!\) — число способов расставить \(n\) предметов в ряд. Размещения \(A(n, k) = \frac{n!}{(n-k)!}\) — число способов выбрать \(k\) предметов из \(n\) с учётом порядка. Сочетания \(C(n, k) = \frac{n!}{k!(n-k)!}\) — то же, но без учёта порядка.

Например, из пяти книг три можно расставить на полке \(A(5,3) = 60\) способами, а выбрать три книги для чтения, не думая о порядке, — \(C(5,3) = 10\) способами.

Важно: порядок учитывается у размещений и не учитывается у сочетаний — поэтому \(A(n,k) = C(n,k) \times k!\), размещений всегда больше.

Пример с решением

Метод: Сочетания C(n,k)

1. Условие. Сколькими способами выбрать 2 делегатов из 5 кандидатов?
2. Формула. \(C(n, k) = \frac{n!}{k!(n-k)!}\).
3. Подстановка. \(C(5, 2) = \frac{5!}{2! \times 3!}\).
4. Вычисление. \(\frac{120}{2 \times 6} = 10\).
5. Ответ. 10 способов. Режим «Сочетания» с n = 5, k = 2 даст 10.

Метод: Размещения A(n,k)

1. Условие. Сколькими способами из 5 кандидатов выбрать председателя и секретаря?
2. Формула. \(A(n, k) = \frac{n!}{(n-k)!}\).
3. Подстановка. \(A(5, 2) = \frac{5!}{3!}\).
4. Вычисление. \(\frac{120}{6} = 20\).
5. Ответ. 20 способов — роли различаются, порядок важен. Режим «Размещения» даст 20.

Метод: Перестановки P(n)

1. Условие. Сколькими способами расставить 4 книги на полке?
2. Формула. \(P(n) = n!\).
3. Подстановка. \(P(4) = 4!\).
4. Вычисление. \(4! = 24\).
5. Ответ. 24 способа. Режим «Перестановки» с n = 4 даст 24 (поле k не нужно).

Главное

• Перестановки: \(P(n) = n!\) — порядок всех \(n\) предметов.
• Размещения: \(A(n,k) = \frac{n!}{(n-k)!}\) — с учётом порядка.
• Сочетания: \(C(n,k) = \frac{n!}{k!(n-k)!}\) — без учёта порядка.