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

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

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

Определение

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

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

где

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

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

$\sum _{k=\alpha }^n(\genfrac{}{}{0ex}{}{n}{k})(-1{)}^{n-k}f(k)=\frac{n!}{2\pi i}{\oint }_{\gamma }\frac{f(z)}{z(z-1)(z-2)\dots (z-n)}dz$

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

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

$\sum _{k=\alpha }^n(\genfrac{}{}{0ex}{}{n}{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(\genfrac{}{}{0ex}{}{n}{k})(-1{)}^{n-k}f(k)=\frac{-n!}{2\pi i}\underset{c-i\mathrm{\infty }}{\overset{c+i\mathrm{\infty }}{\int }}\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}^{\mathrm{\infty }}{f}_n{t}^n.$

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

$\varphi (s)=\underset{0}{\overset{\mathrm{\infty }}{\int }}g(t)t^{s-1}dt.$

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

$f_n=\frac{(-1{)}^n}{2\pi i}\underset{\gamma }{\int }\frac{\varphi (s)}{\mathrm{\Gamma }(-s)}\frac{n!}{s(s-1)\cdots (s-n)}ds,$

где

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