Как вывести и применять формулу числа сочетаний C(n,k)?
Нужна формула числа сочетаний для задачи. Откуда берётся C(n,k) = n!/(k!·(n-k)!) и как ей пользоваться, чтобы не запутаться в факториалах?
2 ответа
Число сочетаний — это «сколькими способами выбрать k предметов из n, если порядок неважен».
Формула:
C(n,k) = n! / (k!·(n−k)!)
Откуда она. Сначала выбираем k элементов с учётом порядка — это размещения A(n,k) = n!/(n−k)!. Но порядок нам не нужен, а одни и те же k элементов можно переставить k! способами. Делим на лишние повторы → получаем формулу выше.
Считать удобнее сокращённо. Например, C(7,2):
7! / (2!·5!) = (7·6) / (2·1) = 42/2 = 21.
Длинные части факториала сокращаются — не надо считать 7! целиком.
Полезные свойства:
C(n,0) = 1иC(n,n) = 1(один способ ничего не взять или взять всё).C(n,k) = C(n, n−k)— симметрия (выбрать 2 из 7 = «оставить» 5 из 7).C(n,1) = n.
Эти сочетания — те самые числа из треугольника Паскаля и коэффициенты в биноме Ньютона.
Практический совет: всегда выбирай меньшее k через симметрию. Считать C(100,98) страшно, но C(100,98) = C(100,2) = (100·99)/2 = 4950 — легко. И помни: на калькуляторе кнопка обычно подписана nCr.