[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en\/wiki40\/norlund-rice-integral-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en\/wiki40\/norlund-rice-integral-wikipedia\/","headline":"N\u00f8rlund\u2013Rice integral – Wikipedia","name":"N\u00f8rlund\u2013Rice integral – Wikipedia","description":"before-content-x4 From Wikipedia, the free encyclopedia after-content-x4 In mathematics, the N\u00f8rlund\u2013Rice integral, sometimes called Rice’s method, relates the nth forward","datePublished":"2020-01-17","dateModified":"2020-01-17","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en\/wiki40\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en\/wiki40\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/3279caaea1b80af40625791857f861e0e29416e1","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/3279caaea1b80af40625791857f861e0e29416e1","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/en\/wiki40\/norlund-rice-integral-wikipedia\/","about":["Wiki"],"wordCount":3543,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4From Wikipedia, the free encyclopedia       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4In mathematics, the N\u00f8rlund\u2013Rice integral, sometimes called Rice’s method, relates the nth forward difference of a function to a line integral on the complex plane. It commonly appears in the theory of finite differences and has also been applied in computer science and graph theory to estimate binary tree lengths. It is named in honour of Niels Erik N\u00f8rlund and Stephen O. Rice. N\u00f8rlund’s contribution was to define the integral; Rice’s contribution was to demonstrate its utility by applying saddle-point techniques to its evaluation.       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Table of ContentsDefinition[edit]Poisson\u2013Mellin\u2013Newton cycle[edit]Riesz mean[edit]Utility[edit]See also[edit]References[edit]Definition[edit]The nth forward difference of a function f(x) is given by\u0394n[f](x)=\u2211k=0n(nk)(\u22121)n\u2212kf(x+k){displaystyle Delta ^{n}[f](x)=sum _{k=0}^{n}{n choose k}(-1)^{n-k}f(x+k)}where        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4(nk){displaystyle {n choose k}} is the binomial coefficient.The N\u00f6rlund\u2013Rice integral is given by\u2211k=\u03b1n(nk)(\u22121)n\u2212kf(k)=n!2\u03c0i\u222e\u03b3f(z)z(z\u22121)(z\u22122)\u22ef(z\u2212n)dz{displaystyle sum _{k=alpha }^{n}{n choose k}(-1)^{n-k}f(k)={frac {n!}{2pi i}}oint _{gamma }{frac {f(z)}{z(z-1)(z-2)cdots (z-n)}},dz}where f is understood to be meromorphic, \u03b1 is an integer, 0\u2264\u03b1\u2264n{displaystyle 0leq alpha leq n}, and the contour of integration is understood to circle the poles located at the integers \u03b1, …, n, but encircles neither integers 0, …, \u03b1\u22121{displaystyle alpha -1} nor any of the poles of f.  The integral may also be written as\u2211k=\u03b1n(nk)(\u22121)kf(k)=\u221212\u03c0i\u222e\u03b3B(n+1,\u2212z)f(z)dz{displaystyle sum _{k=alpha }^{n}{n choose k}(-1)^{k}f(k)=-{frac {1}{2pi i}}oint _{gamma }B(n+1,-z)f(z),dz}where B(a,b) is the Euler beta function.  If the function f(z){displaystyle f(z)} is polynomially bounded on the right hand side of the complex plane, then the contour may be extended to infinity on the right hand side, allowing the transform to be written as\u2211k=\u03b1n(nk)(\u22121)n\u2212kf(k)=\u2212n!2\u03c0i\u222bc\u2212i\u221ec+i\u221ef(z)z(z\u22121)(z\u22122)\u22ef(z\u2212n)dz{displaystyle sum _{k=alpha }^{n}{n choose k}(-1)^{n-k}f(k)={frac {-n!}{2pi i}}int _{c-iinfty }^{c+iinfty }{frac {f(z)}{z(z-1)(z-2)cdots (z-n)}},dz}where the constant c is to the left of \u03b1.Poisson\u2013Mellin\u2013Newton cycle[edit]The Poisson\u2013Mellin\u2013Newton cycle, noted by Flajolet et al. in 1985, is the observation that the resemblance of the N\u00f8rlund\u2013Rice integral to the Mellin transform is not accidental, but is related by means of the binomial transform and the Newton series.  In this cycle, let {fn}{displaystyle {f_{n}}} be a sequence, and let g(t) be the corresponding Poisson generating function, that is, letg(t)=e\u2212t\u2211n=0\u221efntn.{displaystyle g(t)=e^{-t}sum _{n=0}^{infty }f_{n}t^{n}.}Taking its Mellin transform\u03d5(s)=\u222b0\u221eg(t)ts\u22121dt,{displaystyle phi (s)=int _{0}^{infty }g(t)t^{s-1},dt,}one can then regain the original sequence by means of the N\u00f6rlund\u2013Rice integral:fn=(\u22121)n2\u03c0i\u222b\u03b3\u03d5(s)\u0393(\u2212s)n!s(s\u22121)\u22ef(s\u2212n)ds{displaystyle f_{n}={frac {(-1)^{n}}{2pi i}}int _{gamma }{frac {phi (s)}{Gamma (-s)}}{frac {n!}{s(s-1)cdots (s-n)}},ds}where \u0393 is the gamma function.Riesz mean[edit]A closely related integral frequently occurs in the discussion of Riesz means. Very roughly, it can be said to be related to the N\u00f6rlund\u2013Rice integral in the same way that Perron’s formula is related to the Mellin transform: rather than dealing with infinite series, it deals with finite series.Utility[edit]The integral representation for these types of series is interesting because the integral can often be evaluated using asymptotic expansion or saddle-point techniques; by contrast, the forward difference series can be extremely hard to evaluate numerically, because the binomial coefficients grow rapidly for large n.See also[edit]References[edit]Niels Erik N\u00f8rlund, 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\u2013124.Peter Kirschenhofer, “[1]“, The Electronic Journal of Combinatorics, Volume 3 (1996) Issue 2 Article 7.     (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki40\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki40\/norlund-rice-integral-wikipedia\/#breadcrumbitem","name":"N\u00f8rlund\u2013Rice integral – Wikipedia"}}]}]