Разбор добавил Виталий Павленко

Известно рекуррентное соотношение про числа сочетаний — \(C_n^k=C_{n-1}^k+C_{n-1}^{k-1}\). Оно выполняется по крайней мере для всех \(n>1\) и \(k>0\) при \(n\ge k\). Начальные значения для вычисления такие: при всех \(k=0\) и \(k=n\) для всех \(n\ge 0\) верно: \(C_n^k=0\). Вычислять числа сочетаний следует именно по этой формуле — сложность при реализации запоминания уже подсчитанных значений составляет \(O(kn)\), что выполняется за секунду по крайней мере при всех \(n\le 10^3\) (в случае аккуратной реализации, разумеется), но при этом промежуточные результаты не бывают больше конечного — верный способ избежать переполнений. Кроме того, числа сочетаний быстро растут, так что для больших \(n\) (например, для вычисления \(C^{35}_{70}\)) паскалистам и сишникам придётся писать длинную арифметику, а длинное сложение написать проще, чем длинное умножение.
Доказательство соотношения. Число сочетаний — это количество способов выбрать \(k\) предметов из \(n\) имеющихся. Будем переходить от всех способов для \(n-1\) предмета ко всем способам с \(n\) предметами. Мы можем либо добавить наш предмет в каждый из способов, либо не добавить. Это и отражает приведённое выше равенство.

2
1

2