Integral de Norlund-Rice

La integral de Norlund-Rice ( método de Rice ) es una integral que relaciona diferencias finitas con una integral curvilínea en el plano complejo . La integral se utiliza en la teoría de diferencias finitas , y en informática y teoría de grafos para estimar la longitud de un árbol binario . $norte$

La integral lleva el nombre de Niels E. Norlund y Stefan O. Rice ; Norlund definió la integral; Rice le encontró un uso en el método del pase .

Definición

Para una función meromórfica , la diferencia finita se puede representar como: $F$ $norte$ ${\ estilo de visualización \ Delta ^ {n} [f] (x)}$

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

dónde

{\displaystyle {n \elegir k))

— Coeficiente binomial .

Volviendo a la integración en la vecindad de los polos de los puntos y bajo la condición de que la función no tenga polos, obtenemos: ${\ estilo de visualización \ alfa \ ldots n}$ $F$

\sum _{k=\alpha }^{n}{n \elegir k}(-1)^{nk}f(k)={\frac {n!}{2\pi i}}\ punto _ {\ gamma }{\frac {f(z)}{z(z-1)(z-2)\ldots (zn)))\,dz

para _

0\leqslant \alpha \leqslant n(\alpha \in \mathbb {N} )

La integral también se puede escribir como:

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

dónde

{\ estilo de visualización B (a, b)}

es la función beta de Euler .

Si la función está polinomialmente acotada, por ejemplo, por la derecha, entonces la integral se puede extender por la derecha hasta el infinito, obteniendo la notación: $F$

\sum _{k=\alpha }^{n}{n \elegir 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,

dónde

{\ estilo de visualización c <\ alfa}

Ciclo de Poisson-Mellin-Newton

Sea alguna sucesión y sea alguna función generadora de la sucesión , y $\{f_{n}\}$ $g(t)$ $g(t)=e^{-t}\sum _{n=0}^{\infty}f_{n}t^{n}.$

Usando la transformada de Mellin , obtenemos que

\phi(s)=\int _{0}^{\infty}g(t)t^{s-1}\,dt.

Entonces puedes encontrar la secuencia original usando la integral de Norlund-Rice:

f_{n}={\frac {(-1)^{n}}{2\pi i}}\int _{\gamma }{\frac {\phi (s)}{\Gamma (- s)}}{\frac {n!}{s(s-1)\cdots (sn)}}\,ds,

dónde

\Gama

es la función gamma .

Aplicación

Esta representación integral es interesante porque la integral de Norlund-Rice a menudo se puede estimar utilizando métodos de expansión asintótica o el método del punto de silla .

Véase también

Transformación binomial

Literatura

Niels Erik Nörlund, Vorlesungen uber Differenzenrechnung , (1954) Chelsea Publishing Company, Nueva York.
Donald E. Knuth, El arte de la programación informática , (1973), vol. 3 Addison-Wesley.
Philippe Flajolet y Robert Sedgewick, " Transformadas de Mellin y asintóticas: diferencias finitas e integrales de Rice (enlace no disponible) ", Theoretical Computer Science 144 (1995) págs. 101–124.
Peter Kirschenhofer, " Una nota sobre sumas alternas ", The Electronic Journal of Combinatorics , volumen 3 (1996), número 2, artículo 7.