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

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

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

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

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

где

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

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

${\displaystyle \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}$

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

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

${\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,}$

где

${\displaystyle B(a,b)}$ — бета-функция Эйлера.

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

${\displaystyle \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,}$

где

${\displaystyle c<\alpha }$

Пусть ${\displaystyle \{f_{n}\}}$ — некая последовательность и пусть ${\displaystyle g(t)}$ — некая производящая функция последовательности, причём ${\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 (s-n)}}\,ds,}$

где

${\displaystyle \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.