Аннотация. Рассматривается вычисление целочисленной суммы A(n,m) = sum((-1)k C(n,k)2 km) для неотрицательных целых n и m. Описан способ вычисления через производные конечного гипергеометрического многочлена и числа Стирлинга второго рода. Из дифференциального уравнения выводится двухшаговая рекурсия для производных в точке x = 1. Приведены результаты локальных сравнительных измерений с прямым суммированием, ограничения эксперимента и ссылки на ранее опубликованные результаты по той же задаче.
1. Введение
Суммы, содержащие квадраты биномиальных коэффициентов, встречаются в комбинаторике и теории целочисленных последовательностей. В частности, знакопеременные моменты квадратов биномиальных коэффициентов исследованы Н. Гогиным и М. Хирвенсало [1].
Цель настоящей работы - описать и проверить конкретную вычислительную схему, основанную на производных производящей функции. Практический вопрос состоит в том, позволяет ли такая схема уменьшить число операций по сравнению с непосредственным перебором всех k от 0 до n при вычислении одного момента высокого порядка.
2. Постановка задачи
Для целых n >= 0 и m >= 0 требуется вычислить
| A(n,m) = ∑k=0n (-1)k C(n,k)2 km. | (1) |
Здесь C(n,k) = n! / (k!(n-k)!) - биномиальный коэффициент. При m = 0 используется соглашение k0 = 1, в том числе при k = 0. Все вычисления в представленном алгоритме выполняются над целыми числами, без округления с плавающей точкой.
Прямой алгоритм вычисляет каждый член суммы и складывает его с соответствующим знаком. При этом биномиальный коэффициент можно получать последовательно по формуле C(n,k+1) = C(n,k)(n-k)/(k+1), не вычисляя факториалы заново. Именно такой вариант использовался для прямого суммирования в приведённом (ниже) тесте.
3. Производящая функция
Введём конечный многочлен
| Fn(x) = ∑k=0n (-1)k C(n,k)2 xk. | (2) |
Обозначим через fr значение r-й производной этого многочлена в точке x = 1:
| fr = Fn(r)(1). | (3) |
Дифференцирование каждого слагаемого даёт
| fr = ∑k=0n (-1)k C(n,k)2 k(k-1)...(k-r+1). | (4) |
Произведение k(k-1)...(k-r+1) называется падающим факториалом и обозначается k r. При r = 0 оно равно 1. Таким образом, fr представляет собой момент с падающим факториалом вместо обычной степени km.
4. Вывод рекуррентного соотношения
Многочлен Fn(x) является гипергеометрическим многочленом. Для него выполняется дифференциальное уравнение
| x(1+x)F''n(x) + [1 + (1-2n)x]F'n(x) + n2Fn(x) = 0. | (5) |
Это частный случай гипергеометрического дифференциального уравнения, записанного в справочнике NIST Digital Library of Mathematical Functions [2]. После дифференцирования равенства r раз и подстановки x = 1 получаем
| 2fr+2 + (3r+2-2n)fr+1 + (n-r)2fr = 0. | (6) |
Следовательно, два следующих значения вычисляются по формуле
| fr+2 = -[(3r+2-2n)fr+1 + (n-r)2fr] / 2. | (7) |
Это позволяет последовательно получать f2, f3 и далее, используя только два предыдущих значения. При целых n и r результат в данной рекурсии целый; в программе это дополнительно проверяется проверкой делимости числителя на 2.
5. Начальные значения
Для запуска рекурсии нужны f0 = Fn(1) и f1 = F'n(1). Из классического тождества для знакопеременной суммы квадратов биномиальных коэффициентов следует
| f0 = 0, если n нечётно; | (8) |
| f0 = (-1)n/2C(n,n/2), если n чётно. |
Для первой производной используются следующие формулы:
| f1 = (n/2)f0, если n чётно; | (9) |
| f1 = (-1)(n+1)/2((n+1)/2) C(n,(n-1)/2), если n нечётно. |
Эти значения позволяют начать рекурсию без суммирования по всем k. Если требуется m = 0, вычисляется только f0; если m = 1, достаточно f0 и f1.
6. Переход к обычным степеням
В исходной задаче стоит степень km, а fr содержит падающий факториал k r. Эти выражения связаны числами Стирлинга второго рода S(m,r):
| km = ∑r=0m S(m,r) k r. | (10) |
Умножая это тождество на (-1)kC(n,k)2 и суммируя по k, получаем окончательную формулу
| A(n,m) = ∑r=0m S(m,r) fr. | (11) |
Числа S(m,r) вычисляются по стандартному соотношению S(m+1,r) = S(m,r-1) + rS(m,r), с начальными значениями S(0,0) = 1 и S(m,0) = 0 при m > 0. В реализации строится строка чисел Стирлинга до нужного порядка m, после чего вычисляется указанная линейная комбинация.
7. Алгоритм и оценка вычислений
Алгоритм состоит из четырёх этапов: вычисление f0 и f1; получение производных f2,...,fm по двухшаговой рекурсии; построение чисел Стирлинга второго рода до строки m; вычисление суммы S(m,r)fr. Для хранения производных требуется O(m) целых чисел. Построение строки чисел Стирлинга требует O(m2) арифметических операций, а вычисление производных - O(m) операций. Поэтому число арифметических операций алгоритма имеет порядок O(m2), не считая стоимости операций над большими целыми числами.
У прямого алгоритма имеется n+1 слагаемое. При последовательном обновлении биномиального коэффициента число шагов по k имеет порядок O(n), но стоимость операций также зависит от длины больших целых чисел. Поэтому оценка O(m2) против O(n) описывает количество арифметических шагов, а не полное время для любых размеров входа. При небольших n прямой метод может оказаться быстрее из-за меньших постоянных затрат.
8. Программная реализация и точность
Экспериментальная реализация написана на Python и использует целочисленные операции. В рекурсии проверяется, что числитель делится на 2 без остатка; иначе программа сообщает об ошибке. Сравниваются три способа вычисления одной и той же суммы: рекурсия через производные, метод на основе многочленов Кравчука, изложенный Гогиным и Хирвенсало [1], и прямое суммирование.
Во всех четырёх тестовых случаях три реализации возвращают одинаковые целые значения. Дополнительно скрипт проверяет оба рекуррентных метода на полном наборе параметров 0 ≤ n ≤ 30 и 0 ≤ m ≤ 15, сопоставляя их с прямым вычислением. Такая проверка помогает обнаружить ошибки реализации в проверенном диапазоне, но сама по себе, конечно, вряд ли сможет заменить математическое доказательство формул.
9. Сравнение алгоритмов
Для сравнения использована формула метода Кравчука, приведённая в работе Н. Гогина и М. Хирвенсало [1]. В этой работе рассматриваются обычные и знакопеременные моменты квадратов биномиальных коэффициентов; авторы выражают моменты через коэффициенты соответствующих многочленов Кравчука и получают рекуррентные соотношения. В данном эксперименте сравнивается программная реализация этого подхода с рекурсией через производные, выведенной в разделах 3-6, и с прямым суммированием.
В прямом алгоритме биномиальный коэффициент обновляется последовательно по формуле C(n,k+1) = C(n,k)(n-k)/(k+1). Это более эффективный вариант прямого суммирования, чем повторное вычисление коэффициентов через факториалы. Для каждого метода выполняются пять измерений; в таблице указана медиана времени. Результаты получены при одном локальном запуске скрипта и относятся к конкретной системе, а не являются универсальной оценкой скорости.
| n | m | Наша рекурсия, с | Метод Кравчука, с | Прямая сумма, с | Кравчук / наша | Прямая / наша |
| 100 | 10 | 0,000013 | 0,000057 | 0,000030 | 4,47 | 2,31 |
| 1000 | 20 | 0,000061 | 0,006155 | 0,001214 | 101,16 | 19,95 |
| 10000 | 20 | 0,001898 | 0,376118 | 0,216951 | 198,21 | 114,33 |
| 10000 | 50 | 0,002197 | 2,335512 | 0,247151 | 1062,91 | 112,48 |
В этих измерениях наша рекурсия быстрее прямого суммирования примерно в 2,31-114,33 раза, а сравнительная реализация метода Кравчука выполняется примерно в 4,47-1062,91 (!) раза дольше нашей рекурсии. Наиболее заметное различие наблюдается при n = 10000 и m = 50.
10. Исходный код и воспроизводимость
Для повторения эксперимента приложены исходный код рекурсии, единый скрипт бенчмарка и текстовый файл с примером результатов:
Основная реализация рекурсии: binomial_moments.py. Скрипт сравнения трёх методов: binomial_moments_benchmark.py. Пример результатов запуска: benchmark_results.txt.
Для воспроизведения требуется Python 3. Запустите команду python binomial_moments_benchmark.py из каталога с файлами. Скрипт выполняет пять замеров каждого метода, выводит медиану времени, проверяет совпадение целочисленных результатов и проводит дополнительную проверку на малых параметрах. Измеренные значения могут отличаться от приведённых здесь из-за процессора, версии Python, операционной системы и фоновой нагрузки.
11. Обсуждение результатов
Полученные измерения показывают, что для выбранных параметров рекурсия через производные требует меньше времени, чем прямая сумма с последовательным обновлением биномиальных коэффициентов, и чем использованная реализация подхода на основе многочленов Кравчука. Вероятное практическое преимущество связано с тем, что рекурсия строит только значения производных до порядка m, а не обрабатывает все n + 1 слагаемых исходной суммы. При этом стоимость операций с большими целыми числами растёт вместе с размером промежуточных значений, поэтому число арифметических шагов не описывает всё время выполнения.
Метод Кравчука не является каким-то произвольным сторонним алгоритмом: он предназначен для той же задачи знакопеременных моментов и опубликован ранее [1]. Поэтому его наличие в сравнении важно для корректного контекста исследования. Настоящие результаты относятся к указанным реализациям и тестовым параметрам; они не позволяют заявлять о превосходстве над всеми возможными реализациями метода Кравчука или о новизне самой задачи. Для дальнейшей работы полезно исследовать влияние порядка m, увеличить набор параметров и провести замеры на нескольких конфигурациях компьютера.
12. Заключение
Описан точный алгоритм вычисления знакопеременного момента квадратов биномиальных коэффициентов через производные конечного гипергеометрического многочлена. Дифференциальное уравнение приводит к рекурсии, связывающей два последовательных предыдущих значения с очередной производной, а числа Стирлинга второго рода переводят падающие факториалы в обычные степени. В проведённых локальных тестах алгоритм дал те же целочисленные результаты, что и метод на основе многочленов Кравчука и прямое суммирование, и оказался быстрее обеих приложенных реализаций на всех четырёх проверенных наборах параметров.
По результатам проведённых вычислительных экспериментов предложенная реализация показала наименьшее время выполнения среди трёх сравниваемых алгоритмов: рекурсии на основе производных, реализации метода Кравчука и прямого суммирования. Во всех рассмотренных тестах вычисленные целочисленные значения совпали. То есть предложенный алгоритм продемонстрировал наилучшую производительность.
Список использованных источников
1. Gogin N., Hirvensalo M. On the Moments of Squared Binomial Coefficients // International Conference on Polynomial Computer Algebra. 2020. P. 66-70. Текст публикации: https://pca-pdmi.ru/2020/files/10/GoHi2020ExtAbstract.pdf.
2. NIST Digital Library of Mathematical Functions. Chapter 15: Hypergeometric Function. Section 15.10: Hypergeometric Differential Equation. URL: https://dlmf.nist.gov/15.10 (дата обращения: 09.10.2026).
3. OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences. Запись A002457 и ссылки на литературу о знакопеременных суммах квадратов биномиальных коэффициентов. URL: https://oeis.org/A002457 (дата обращения: 09.10.2026).