Элементы комбинаторики - перестановки, размещения, сочетания

Комбинаторикой называют раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчинённых тем или иным условиям, можно составить из заданных объектов. Выбором объектов и расположением их в том или ином порядке приходится заниматься чуть ли не во всех областях человеческой деятельности.

Данный онлайн калькулятор рассчитывает следующие комбинаторные величины для заданных n и k:

• Число перестановок из n элементов: \[ P_n = n! \]
• Число размещений из n по k: \[ A_n^k = n\cdot(n-1)\cdots(n-k+1) = \frac{n!}{(n-k)!} \]
• Число сочетаний из n по k: \[ C_n^k = \binom{n}{k} = \frac{n!}{k!\,(n-k)!} \]

Перестановки - число способов упорядочить n различных элементов: \[ P_n = n! \] Размещения - число способов выбрать и упорядочить k элементов из n различных: \[ A_n^k = \frac{n!}{(n-k)!} = n \cdot (n-1) \cdot \ldots \cdot (n-k+1) \] Сочетания - число способов выбрать k элементов из n без учёта порядка: \[ C_n^k = \binom{n}{k} = \frac{n!}{k!\,(n-k)!} \]

Перестановка из n элементов - это упорядоченная последовательность всех n элементов. Число перестановок: \[ P_n = n! = 1 \cdot 2 \cdot 3 \cdots n \]

Размещение из n по k - это упорядоченная выборка k элементов из n различных. Число размещений: \[ A_n^k = \frac{n!}{(n-k)!} \] Является частным случаем: при k = n получаем P_n.

Сочетание из n по k - это неупорядоченная выборка k элементов из n. Число сочетаний (биномиальный коэффициент): \[ C_n^k = \binom{n}{k} = \frac{n!}{k!\,(n-k)!} \] Связь с размещениями: \[ C_n^k = \frac{A_n^k}{k!} \]

Свойства сочетаний: \[ \binom{n}{0} = \binom{n}{n} = 1 \] , \[ \binom{n}{k} = \binom{n}{n-k} \] , формула Паскаля: \[ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \]

Применение: комбинаторика применяется в теории вероятностей, криптографии, биоинформатике, при решении задач об укладке, планировании экспериментов, анализе алгоритмов. Число неупорядоченных выборок - основа формулы Бернулли и биномиального распределения.

Интересный факт: сочетания C(n, k) - это коэффициенты бинома Ньютона \[ (a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k} \] Сумма всех сочетаний C(n, 0) + C(n, 1) + ... + C(n, n) = 2ⁿ.