Task 88. Биномиальный коэффициент

Задача: Биномиальным коэффициентом Cnk называется количество способов выбрать набор k предметов из n различных предметов без учёта порядка расположения этих элементов.

Даны n, k. Необходимо вычислить Cnk.

Входные данные: n, k, где 0 <= k <= n < 2^32

Вывод: значение Cnk, где Cnk < 2^64.

Идея: воспользуемся одним из свойств биномиальных коэфф.:

Cnk = Cn(n-k)

Подробнее про свойства биномиальных коэфф.вы можете почитать здесь:

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

Исходя из этого при n - k < k положим, что k = n - k.

Далее по формуле бин.коэфф:

Cnk = n! / (k! * (n - k)!) =

= (n * (n-1) * (n-2)* ... *(n - k + 1)) / (1*2*...*k) =

= (n/1) * (n-1)/2 * (n-2)/3 * ... * (n-k+1)/k

В итоге получим формулу вида:

(n - i + 1) / i

При исходных данных в этой формуле можно получить переполнение, поэтому воспользуемся длинной арифметикой.

Реализация:

https://gist.github.com/unilecs/edc4164a062ce00222c9b86e52d5cef3

Test:

https://dotnetfiddle.net/s0gWtd