ノールンド・ライス積分

数学において、ノールンド・ライス積分（Nørlund–Rice 積分、またはライス法とも呼ばれる）は、関数のn次前進差分を複素平面上の線積分に関連付ける。これは差分理論でよく登場し、コンピュータサイエンスやグラフ理論でも二分木の長さを推定するために応用されている。この方法は、ニールス・エリック・ノールンドとスティーブン・O・ライスにちなんで名付けられた。ノールンドの貢献は積分を定義したことであり、ライスの貢献は積分の評価に鞍点法を適用してその有用性を実証したことである。

関数f ( x )のn次の前進差分は次のよう に表される。

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

ここで二項係数です。 ${\displaystyle {n \choose 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 \alpha \leq n}$${\displaystyle \alpha -1}$

${\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}$

ここで、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 はα の左側にあります。

ポアソン・メリン・ニュートンサイクルは、1985年にフラジョレットらによって指摘されたもので、ノアランド・ライス積分とメリン変換の類似性は偶然ではなく、二項変換とニュートン級数によって関連付けられているという観察である。このサイクルでは、を数列とし、g ( t ) を対応するポアソン生成関数とすると、 ${\displaystyle \{f_{n}\}}$

${\displaystyle g(t)=e^{-t}\sum _{n=0}^{\infty}{\frac{t^{n}}{n!}}f_{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に対して急速に増加するため、数値的に評価するのが非常に難しい場合があります。

• ニュートン級数表
• 階乗と二項式のトピックのリスト

• Niels Erik Nørlund、Vorlesungen uber Differenzenrechnung、(1954) Chelsea Publishing Company、ニューヨーク。
• Donald E. Knuth, The Art of Computer Programming、(1973)、第 3 巻、Addison-Wesley。
• Philippe Flajolet と Robert Sedgewick、「メリン変換と漸近解析: 有限差分とライス積分」、 理論計算機科学 144 (1995) pp 101–124。
• Peter Kirschenhofer、「[1]」、The Electronic Journal of Combinatorics、第3巻（1996年）第2号、第7条。
• フィリップ・フラジョレ、講演「空から見たメリン」、35ページ。