В математике , то интеграл Nørlund-Райса , который иногда называют методом Райс , относится к п - й вперед разности функции к интегралу линии на комплексной плоскости . Он обычно появляется в теории конечных разностей, а также применяется в информатике и теории графов для оценки длины двоичного дерева . Он назван в честь Нильса Эрика Норлунда и Стивена О. Райса . Вклад Норлунда заключался в определении интеграла; Вклад Райс заключался в том, чтобы продемонстрировать его полезность, применивметоды перевала к его оценке.
Определение
П - й прямой разности некоторой функции F ( х ) задается
где - биномиальный коэффициент .
Интеграл Нёрлунда – Райса дается выражением
где f понимается как мероморфный , α - целое число,, а контур интегрирования понимается как окружающий полюсы, расположенные в целых числах α, ..., n , но не окружающий ни одного целого числа 0, ...,ни один из полюсов f . Интеграл также можно записать как
где B ( a , b ) - бета-функция Эйлера . Если функцияявляется полиномиально ограничена на правой стороне комплексной плоскости, то контур может быть продлен до бесконечности на правой стороне, что позволяет преобразовать быть записана в виде
где постоянная c находится слева от α.
Цикл Пуассона – Меллина – Ньютона.
Цикл Пуассона – Меллина – Ньютона, отмеченный Flajolet et al. в 1985 году было обнаружено, что сходство интеграла Норлунда – Райса с преобразованием Меллина не случайно, а связано с помощью биномиального преобразования и ряда Ньютона . В этом цикле пусть- последовательность , и пусть g ( t ) - соответствующая производящая функция Пуассона , т. е. пусть
Принимая его преобразование Меллина
затем можно восстановить исходную последовательность с помощью интеграла Нёрлунда – Райса:
где Γ - гамма-функция .
Рисса среднее
Тесно связанный интеграл часто встречается при обсуждении средних Рисса . Грубо говоря, можно сказать, что он связан с интегралом Нёрлунда – Райса так же, как формула Перрона связана с преобразованием Меллина: вместо бесконечных рядов она имеет дело с конечными рядами.
Полезность
Интегральное представление для этих типов рядов интересно тем, что интеграл часто можно вычислить, используя асимптотическое разложение или методы перевала ; Напротив, ряд прямых разностей может быть чрезвычайно трудно оценить численно, потому что биномиальные коэффициенты быстро растут при больших n .
Смотрите также
Рекомендации
- Нильс Эрик Норлунд, Vorlesungen uber Differenzenrechnung , (1954) Chelsea Publishing Company, Нью-Йорк.
- Дональд Э. Кнут, Искусство компьютерного программирования , (1973), Vol. 3 Эддисон-Уэсли.
- Филипп Флажолет и Роберт Седжвик, « Преобразования Меллина и асимптотики: конечные разности и интегралы Райса », « Теоретическая информатика» 144 (1995), стр. 101–124.
- Питер Киршенхофер, " [1] ", Электронный журнал комбинаторики , том 3 (1996), выпуск 2, статья 7.