Часто математические задачи можно решить разными способами. Например, недавно у нас была задача про улицы Питера. Мы её решали с помощью треугольника Паскаля, а в комментариях многие писали другой способ решения — комбинаторный. Разберём его.

В той задаче Макс хочет пройти 6 кварталов вниз и 2 вправо. Все направления «вниз» идентичны между собой, как идентичны и варианты «вправо». Всего Максу нужно пройти 6 + 2 = 8 кварталов.
Закодируем направление «вниз» буквой Н, а варианты «вправо» — буквой П. С точки зрения комбинаторики каждый маршрут — это как бы слово из восьми букв, причём шесть из них — Н и две — П. И нам нужно найти количество таких слов. Это же…. число сочетаний!
Значит, количество способов добраться из точки А в точку В можно записать как C⁶₈ или как C²₈. В любом случае имеем
8! / (2!*6!) = (8*7) / 2 = 28. Именно этот ответ мы и получили раньше.

Обобщим! Любой элемент треугольника Паскаля можно вычислить с помощью формулы для количества сочетаний из n по k. Индекс n пишут внизу рядом с заглавной буквой С, а индекс k — наверху. Формула для подсчёта количества сочетаний равна:
n! / ((n-k)!*k!), где
n — это номер ряда треугольника Паскаля (в нашем случае равно длине слова)
k — это номер коэффициента в n-м ряду (количество выбираемых букв в слове).

Нумерация обоих индексов n и k начинается с нуля!
Такие коэффициенты вида Сᵏₙ называют биномиальными, потому что пришли они из разложения бинома.

И с их помощью можно легко вычислить любой элемент треугольника Паскаля, не вычисляя предыдущие.
Например, второй элемент в четвёртом ряду равен C²₄ = 4! / ((4-2)!*2!) = 4*3 / 2 = 6.

А значит, можно вычислить коэффициент при любом слагаемом в разложении (a+b)ⁿ, не выписывая весь треугольник Паскаля до этой строчки. Удобно!