Вычисление биномиальных коэффициентов… вручную
Ранее в двух статьях была затронута тема вычисления биномиальных коэффициентов с помощью компьютера.
Расчет биномиальных коэффициентов на Си (С++)
Расчет биномиальных коэффициентов с использованием Фурье-преобразований
По их прочтению может сложиться мнение что это сложная и ресурсоемкая задача.
Прежде чем программировать что-то, попробуем разобраться что здесь к чему.
Факториальная формула:
Раскроем ее:
Очевидно, что
А теперь попробуем посчитать например
Сразу видно, что 10, 9 и 8 взаимно сокращаются, приводя нас к
Поглядев внимательнее, видим что на этом сокращения не заканчиваются. 14 делится на 7, 12 на 6, 15 на 5, 16 на 4. Оставшиеся от 15 три делится на три, и оставшиеся от 7 2 делится на последнюю двойку. Произведя все эти сокращения мы избавляемся от знаменателя, получаем такое произведение:
Попробуем посчитать
Первое сокращение:
Далее нетрудно видеть что 114/57=2, 112/56=2, 110/55=2 и так далее, до 62/31=2
Второе сокращение:
Так, мы получили в числителе 27 двоек, которые попробуем сократить со знаменателем. Для начала вычеркнем все степени двойки из знаменателя и соответствующее число двоек из числителя. ( 2, 4, 8, 16 = 10 двоек, осталось 17 )
В знаменателе есть еще 11 четных чисел, некоторые из них кратно четные. После всех сокращений в знаменателе не остается четных чисел, а в числителе останутся две двойки.
Примемся теперь за тройки.
Ну и далее, сокращаем на 5, 7, 11, 17, 19, 23, 29
Остается:
что равно 23 544 809 717 399 465 172 377 319 715 292 496.