Вычисление суммы степеней последовательных чисел

Мы будем рассматривать задачу вычисления суммы степеней

	S(n,k)=S i=1..n ik    (1)

При этом суммирование в формуле (1) можно начинать с нуля, что не изменяет значения суммы, но зато облегчает некоторые математические преобразования.

В дальнейшем нам понадобятся числа Стирлинга второго рода, которые показывают, сколькими способами можно разбить n элементное множество на k непересекающихся подмножеств. Для вычисления чисел Стирлинга второго рода не существует закрытой формулы, как и для биноминальных коэффициентов, но есть простая рекурсивная формула:

	{n, k} = k * {n - 1, k} + {n - 1, k - 1}
	{n, 0} = {n == 0}							(2)
	{0, n} = (n == 0)
	{n, m} = 0; m > n

Начальные условия очевидны. Нет способов разбить n элементное множество на 0 множеств. А пустое множество можно разбить лишь на 0 пустых множеств.

Рекурсивный шаг тоже можно получить из соответствующих комбинаторных рассуждений. Последнее условие легко получается из предущего, так как после итерирования рекурсии получается сумма типа {0, n}, где n > 0, то есть сумма 0, которая очевидно равна 0. С помощью данной формулы мы можем легко вычислять.

Основное достоинство этих чисел заключается в том, что с их помощью можно представить обычную степень, как сумму факториальных степеней:

	x m = Si=0m-1 x (m - i) * {m, i}, (2)

где

	x (m)= x(x - 1)(x - 2)*...*(x - m + 1) (3)

Теперь разделив и умножив на (x - m)!, получим биноминальные коэффициенты C(x,m), следовательно получаем следующую формулу:

	x m = Si=0m-1 C(x, i) * (m - i)! * {m, i} (4)

Итак, нам осталось лишь вычислить сумму этих чисел:

	S(n,m) = 1n + ... + m n
	S(n,m) = Si (Sj ((C(i, j) * (n - j)! * {n, j})) (5)

Представляя биноминальные коэффициенты в рекурсивном виде получим следующую формулу:

	C(n,k) = C(n - 1, k) + C(n - 1, k - 1) (рекурсивная форма)
	C(n,k) = C(n - 1, k) + C(n - 1, k - 1) =
	       = C(n - 1, k - 1) + C(n - 2, k - 1) + C(n - 2, k) + ... =
	       = Sm=0n-1 (C(m, k - 1))    (6)

Меняя порядок суммирования в формуле (5) и вынося числа Стирлинга и факториал за сумму и просуммировав отдельно биноминальные коэффиценты, получим одинарную сумму:

	S(n,m) = Sj ((n - j)! * {n, j} * Si (C(i,j))) =
	       = Sj ((n - j)! * {n, j} * C(m + 1, n - j + 1))

Итак у нас все готово. Проведем небольшой анализ данного алгоритма. Вычисление биномиальных коэффициентов и факториала можно произвести без рекурсии, с помощью простого суммирования, то есть время их вычисление линейно. Для чисел Стирлинга получается рекурсивная формула, итерируя которую получим, что для вычисления потребуется время пропорциональное квадрату. Следовательно для всей суммы получится алгоритм пропорциональный кубу от n,

	T(n) = O(n3)

Это не очень быстрый алгоритм. Однако существует нерекурсивная формула, которая позволяет вычислять числа Стирлинга за время меньшее квадратного. Следовательно, уменьшится время для вычисления всей суммы.

Функция для вычисления биноминальных коэффициентов

 unsigned long binom(int n, int k)
 {
  unsigned long t = 1;
  for (int i = 0; i < k; i++)
  {
    t = (t * (n - i)) / (i + 1);
  }
  return t;
 }

Функция для вычисления чисел Стирлинга второго рода

 unsigned long stirling2(int n, int m)
 {
  if (n && !m)
  {
    return 0;
  }
  if (!n)
  {
    return (!m);
  }
  return m * stirling2(n - 1, m) + stirling2(n - 1, m - 1);
 }

Функция для вычисления факториала

 unsigned long factorial(int n)
 {
  unsigned long q = 1;
  for (int i = 2; i <= n; i++)
  {
    q *= i;
  }
  return q;
 }

Конечная функция для вычисления суммы

 unsigned long sumNK(int n, int k)
 {
  unsigned long s = 0;
  for (int i = 0; i < k; i++)
  {
    s += binom(n + 1, k - i + 1) * stirling2(k, i + 1) * factorial(k - i);
  }
  return s;
 }

Эта функция не дает ощутимого результата в общем случае, однако данное решение является красивым и в иных случаях может дать гораздо лучшие результаты, чем решения в лоб.