Биномиальные коэффициенты

Материал из Algocode wiki
Версия от 10:33, 30 октября 2019; Глеб (обсуждение | вклад) (Новая страница: «==Определение== Посчитаем количество способов выбрать $k$ элементов из $n$ различных (назыв...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Определение

Посчитаем количество способов выбрать $k$ элементов из $n$ различных (называется числом сочетаний из $n$ по $k$ и обозначается $C_n^k$).

Первый способ

Точно так же на первое место мы можем поставить любой из $n$ элементов, на второе — любой из $n - 1$ оставшихся, на $k$-е место останется $n - k + 1$ вариант, то есть всего вариантов получится $n\cdot(n-1)\cdot\ldots\cdot(n-k+1)=\frac{n!}{(n-k)!}$. Заметим, что так мы посчитали число _упорядоченных_ наборов из $k$ элементов и чтобы получить количество способов выбрать $k$ элементов из $n$ нужно поделить результат на $k!$, ведь, как было установлено ранее, именно столько есть спобосов упорядочить $k$ элементов. В итоге получается $C_n^k=\frac{n!}{k!(n-k)!}$

Второй способ

Есть и другой способ подсчета $C_n^k$ для $0 < k < n$. Посмотрим на первый элемент. Если он входит в набор, то осталось выбрать $k-1$ из $n-1$ оставшихся. Иначе нужно выбрать $k$ из $n-1$ оставшихся. Значит, $C_n^k=C_{n-1}^{k}+C_{n-1}^{k-1}$. Так можно найти все $C_n^k$ до какого-то $n$ за $O(n^2)$.

Треугольник Паскаля

Таким образом, $C_n^k$ легко представлять в виде бесконечного треугольника, где на сторонах стоят 1, а остальные числа равны сумме двух верхних. Легко видеть, что $C_n^k$ это $k$-е число в строке номер $n$. Это называют треугольником Паскаля.



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin