Интеграл Норлунда – Райса

В математике, то интеграл Nørlund-Райса, который иногда называют методом Райс, относится к п - й вперед разности функции к интегралу линии на комплексной плоскости. Он обычно появляется в теории конечных разностей, а также применяется в информатике и теории графов для оценки длины двоичного дерева. Он назван в честь Нильса Эрика Норлунда и Стивена О. Райса. Вклад Норлунда заключался в определении интеграла; Вклад Райс заключался в демонстрации его полезности путем применения методы перевала к его оценке.

• 1 Определение
• 2 цикл Пуассона – Меллина – Ньютона
• 3 среднее значение Рисса
• 4 Утилита
• 5 См. Также
• 6 Ссылки

П - й прямой разности некоторой функции F ( х) задается

${\ displaystyle \ Delta ^ {n} [f] (x) = \ sum _ {k = 0} ^ {n} {n \ select k} (- 1) ^ {nk} f (x + k)}$

где - биномиальный коэффициент. ${\ displaystyle {n \ select k}}$

Интеграл Норлунда – Райса дается выражением

${\ displaystyle \ sum _ {k = \ alpha} ^ {n} {n \ choose k} (- 1) ^ {nk} f (k) = {\ frac {n!} {2 \ pi i}} \ oint _ {\ gamma} {\ frac {f (z)} {z (z-1) (z-2) \ cdots (zn)}} \, dz}$

где f считается мероморфным, α является целым числом, и контур интегрирования считается окружающим полюсы, расположенные в целых числах α,..., n, но не окружает ни целые числа 0,..., ни любое из полюса f. Интеграл также можно записать как ${\ Displaystyle 0 \ Leq \ альфа \ Leq п}$ ${\ displaystyle \ alpha -1}$

${\ displaystyle \ sum _ {k = \ alpha} ^ {n} {n \ select k} (- 1) ^ {k} f (k) = - {\ frac {1} {2 \ pi i}} \ oint _ {\ gamma} B (n + 1, -z) f (z) \, dz}$

где B ( a, b) - бета-функция Эйлера. Если функция является полиномиально ограничена на правой стороне комплексной плоскости, то контур может быть продлен до бесконечности на правой стороне, что позволяет преобразовать быть записана в виде ${\ displaystyle f (z)}$

${\ displaystyle \ sum _ {k = \ alpha} ^ {n} {n \ choose k} (- 1) ^ {nk} f (k) = {\ frac {-n!} {2 \ pi i}} \ int _ {ci \ infty} ^ {c + i \ infty} {\ frac {f (z)} {z (z-1) (z-2) \ cdots (zn)}} \, dz}$

где постоянная c находится слева от α.

Цикл Пуассона – Меллина – Ньютона, отмеченный Flajolet et al. в 1985 году было обнаружено, что сходство интеграла Норлунда – Райса с преобразованием Меллина не случайно, а связано с помощью биномиального преобразования и ряда Ньютона. Пусть в этом цикле - последовательность, а g ( t) - соответствующая производящая функция Пуассона, т. Е. Пусть ${\ Displaystyle \ {е_ {п} \}}$

${\ displaystyle g (t) = e ^ {- t} \ sum _ {n = 0} ^ {\ infty} f_ {n} t ^ {n}.}$

Принимая преобразование Меллина

${\ Displaystyle \ phi (s) = \ int _ {0} ^ {\ infty} g (t) t ^ {s-1} \, dt,}$

затем можно восстановить исходную последовательность с помощью интеграла Нёрлунда – Райса:

${\ displaystyle f_ {n} = {\ frac {(-1) ^ {n}} {2 \ pi i}} \ int _ {\ gamma} {\ frac {\ phi (s)} {\ Gamma (- s)}} {\ frac {n!} {s (s-1) \ cdots (sn)}} \, ds}$

где Γ - гамма-функция.

Тесно связанный интеграл часто встречается при обсуждении средних Рисса. Грубо говоря, можно сказать, что он связан с интегралом Нёрлунда – Райса так же, как формула Перрона связана с преобразованием Меллина: вместо бесконечных рядов она имеет дело с конечными рядами.

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

• Таблица ньютоновских рядов
• Список факториальных и биномиальных тем

• Нильс Эрик Норлунд, Vorlesungen uber Differenzenrechnung, (1954) Chelsea Publishing Company, Нью-Йорк.
• Дональд Э. Кнут, Искусство программирования, (1973), Vol. 3 Эддисон-Уэсли.
• Филипп Флажоле и Роберт Седжвик, « Преобразования Меллина и асимптотики: конечные разности и интегралы Райса », « Теоретическая информатика» 144 (1995), стр. 101–124.
• Питер Киршенхофер, " [1] ", Электронный журнал комбинаторики, том 3 (1996), выпуск 2, статья 7.