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

Интеграл Норлунда — Райса (метод Райса) — интеграл, связывающий ${\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.

У этой статьи есть несколько проблем, помогите их исправить: В статье есть список источников, но не хватает сносок. Без сносок сложно определить, из какого источника взято каждое отдельное утверждение. Вы можете улучшить статью, проставив сноски на источники, подтверждающие информацию. Сведения без сносок могут быть удалены. (8 февраля 2013) Раздел литературы нуждается в оформлении согласно рекомендациям. Пожалуйста, оформите его согласно образцам здесь. (8 февраля 2013) Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.