Интеграл Норлунда – Райса - Nørlund–Rice integral

В математике , то интеграл Nørlund-Райса , который иногда называют методом Райс , относится к п - й вперед разности функции к интегралу линии на комплексной плоскости . Он обычно появляется в теории конечных разностей, а также применяется в информатике и теории графов для оценки длины двоичного дерева . Он назван в честь Нильса Эрика Норлунда и Стивена О. Райса . Вклад Норлунда заключался в определении интеграла; Вклад Райс заключался в демонстрации его полезности путем примененияметоды перевала к его оценке.

Определение

П - й прямой разности некоторой функции F ( х ) задается

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

где - биномиальный коэффициент . ${\ displaystyle {n \ select k}}$

Интеграл Норлунда – Райса дается выражением

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

где f считается мероморфным , α является целым числом, и контур интегрирования считается окружающим полюсы, расположенные в целых числах α, ..., n , но не окружает ни целые числа 0, ..., ни любое из полюса f . Интеграл также можно записать как ${\ Displaystyle 0 \ Leq \ альфа \ Leq п}$${\ displaystyle \ alpha -1}$

${\ displaystyle \ sum _ {k = \ alpha} ^ {n} {n \ select k} (- 1) ^ {k} f (k) = - {\ frac {1} {2 \ pi i}} \ oint _ {\ gamma} B (n + 1, -z) f (z) \, dz}$

где B ( a , b ) - бета-функция Эйлера . Если функция является полиномиально ограничена на правой стороне комплексной плоскости, то контур может быть продлен до бесконечности на правой стороне, что позволяет преобразовать быть записана в виде ${\ displaystyle f (z)}$

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

где постоянная c находится слева от α.

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

Цикл Пуассона – Меллина – Ньютона, отмеченный Flajolet et al. в 1985 году было обнаружено, что сходство интеграла Норлунда – Райса с преобразованием Меллина не случайно, а связано с помощью биномиального преобразования и ряда Ньютона . Пусть в этом цикле - последовательность , а g ( t ) - соответствующая производящая функция Пуассона , т. Е. Пусть ${\ Displaystyle \ {е_ {п} \}}$

${\ 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 (sn)}} \, ds}$

где Γ - гамма-функция .

Рисса среднее

Тесно связанный интеграл часто встречается при обсуждении средних Рисса . Грубо говоря, можно сказать, что он связан с интегралом Нёрлунда – Райса так же, как формула Перрона связана с преобразованием Меллина: вместо бесконечных рядов она имеет дело с конечными рядами.

Утилита

Интегральное представление для этих типов рядов интересно тем, что интеграл часто можно вычислить, используя асимптотическое разложение или методы перевала ; Напротив, ряд прямых разностей может быть чрезвычайно сложно оценить численно, потому что биномиальные коэффициенты быстро растут при больших n .

Смотрите также

• Таблица ньютоновских рядов
• Список факториальных и биномиальных тем

Ссылки

• Нильс Эрик Норлунд, Vorlesungen uber Differenzenrechnung , (1954) Chelsea Publishing Company, Нью-Йорк.
• Дональд Э. Кнут, Искусство программирования , (1973), Vol. 3 Эддисон-Уэсли.
• Филипп Флажоле и Роберт Седжвик, « Преобразования Меллина и асимптотики: конечные разности и интегралы Райса », « Теоретическая информатика» 144 (1995), стр. 101–124.
• Питер Киршенхофер, " [1] ", Электронный журнал комбинаторики , том 3 (1996), выпуск 2, статья 7.