если у нас есть A предметов, то 2 из них можно выбрать A(A-1)/2 способами, 3 — A(A-1)(A-2)/6 способами и т.д.; буду здесь обозначать (A|K) := A(A-1)…(A-K+1) / K!
эту формулу часто помнят в виде отношения факториалов, но если мы хотим выбрать 2 предмета из 1000, то начинать подсчет количества вариантов с вычисления 1000! — не самая лучшая идея
есть и другой аспект. разговор о выборе K предметов имеет смысл только если число A целое… а вот в наше определение для (A|K) формально можно подставить любое A
в этом есть смысл — например,
(1+x)^A = 1 + Ax + (A|2)x² + (A|3)x³ + ...
и это равенство верно и для нецелых A
многие помнят, что sqrt(1+x) это примерно 1+x/2 — а формула выше учит, что делать, если точности такого первого приближения недостаточно
2.
если от ограничений на A мы избавились, то K в формулах выше всё ж должно быть натуральным, иначе непонятно, что такое K!
но теперь можно изменить точку зрения и воспользоваться предыдущим для определения факториала произвольного числа
смотрите. если A большое число (а K пока натуральное), то (A|K) ~ A^K / K!, т.е. K! ~ A^K/(A|K); наконец, если A = K+N, то пользуясь симметрией биномиальных коэффициентов, (K+N|K)=(K+N|N), мы получаем K! ~ N^K/(K+N|N)
ура: правая часть определена и при нецелых K, и можно теперь считать определением факториала K! = lim N^K/(K+N|N) — а текст выше объясняет, что для целых K такой факториал совпадает с привычным
такое определение придумал, насколько понимаю, Эйлер
3.
пора всё-таки добавить компьютер… на картинке вычисления (1/2)!, (1/3)!, (1/4)! в экселе
sanity check: (K+2|2)=(K+2)(K+1)/2 — вроде это согласуется с тем, что подсчитано в строке 4
технически для бин. к-та написана формула типа
=PRODUCT(1+A$1/SEQUENCE(A3))приятно, что полмиллиона сомножителей тут для экселя совсем не проблема… потому что видно, что такие формулы сходятся к ответу довольно медленно
как посчитать (1/4)! быстрее — мб в следующий раз обсудим
если никогда с этим не сталкивались и кажется, что всё это какая-то ерунда, предлагаю возвести ответ для (1/2)! из таблицы в квадрат и сообразить, что это за число (если ничего не приходит в голову — умножьте на 4)