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

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

n -я прямая разность функции f ( x ) определяется как

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

где - биномиальный коэффициент .${\displaystyle {n \выберите 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 n}$${\displaystyle \альфа -1}$

${\displaystyle \sum _{k=\alpha }^{n}{n \choose 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 находится слева от α.

Цикл Пуассона–Меллина–Ньютона, отмеченный Флажоле и др. в 1985 году, представляет собой наблюдение, что сходство интеграла Норлунда–Райса с преобразованием Меллина не случайно, а связано посредством биномиального преобразования и ряда Ньютона . В этом цикле пусть будет последовательностью , и пусть g ( t ) будет соответствующей производящей функцией Пуассона , то есть пусть${\displaystyle \{f_{n}\}}$

${\displaystyle g(t)=e^{-t}\sum _{n=0}^{\infty }{\frac {t^{n}}{n!}}f_{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) Издательство Челси, Нью-Йорк.
• Дональд Э. Кнут, Искусство программирования , (1973), т. 3 Эддисон-Уэсли.
• Филипп Флажоле и Роберт Седжвик, «Преобразования Меллина и асимптотика: конечные разности и интегралы Райса», Теоретическая информатика 144 (1995) стр. 101–124.
• Питер Киршенхофер, «[1]», Электронный журнал комбинаторики , том 3 (1996), выпуск 2, статья 7.
• Филипп Флажоле, лекция «Меллин, вид с неба», стр. 35 .