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

Интеграл Норлунда — Райса (метод Райса) — интеграл, связывающий $n$ конечных разностей с криволинейным интегралом в комплексной плоскости. Интеграл используется в теории конечных разностей, а также в Информатике и теории графов для оценки длины двоичного дерева.

Интеграл назван в честь Нильса Э. Норлунда и Стефана О. Райса; Норлунд определил интеграл; Райс нашёл ему применение в методе перевала.

Определение

Для мероморфной функции $f$ $n$-ю конечную разность $\Delta ^{n}[f](x)$ можно представить в виде:

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

где

${n \choose k}$ — Биномиальный коэффициент.

Переходя к интегрированию в окрестности полюсов точек $\alpha \ldots n$ и при условии, что функция $f$ полюсов не имеет, получим:

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

для $0\leqslant \alpha \leqslant n(\alpha \in \mathbb {N} )$.

Интеграл также можно записать в виде:

$\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)$ — бета-функция Эйлера.

Если функция $f$ полиномиально ограничена, например, справа, то интеграл можно продлить направо до бесконечности, получив запись:

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

где

$c<\alpha$

Цикл Пуассона — Меллина — Ньютона

Пусть $\{f_{n}\}$ — некая последовательность и пусть $g(t)$ — некая производящая функция последовательности, причём $g(t)=e^{-t}\sum _{n=0}^{\infty }f_{n}t^{n}.$

Используя преобразование Меллина, получим, что

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

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

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

где

$\Gamma$ — гамма-функция.

Применение

Это интегральное представление интересно тем, что интеграл Норлунда — Райса часто может быть оценён с использованием методов асимптотического разложения или методом перевала.

См. также

• Биномиальное преобразование

Литература

• Niels Erik Nörlund, Vorlesungen uber Differenzenrechnung, (1954) Chelsea Publishing Company, New York.
• Donald E. Knuth, The Art of Computer Programming, (1973), Vol. 3 Addison-Wesley.
• Philippe Flajolet and Robert Sedgewick, «Mellin transforms and asymptotics: Finite differences and Rice’s integrals (недоступная ссылка)», Theoretical Computer Science 144 (1995) pp 101–124.
• Peter Kirschenhofer, «A Note on Alternating Sums», The Electronic Journal of Combinatorics, Volume 3 (1996) Issue 2 Article 7.