二項変換

Transformation of a mathematical sequence

組合せ論において、二項変換は、順方向差分を計算する列変換（すなわち、列の変換）である。これは、通常の生成関数に関連付けられた列に二項変換を適用した結果であるオイラー変換と密接に関連している。

意味

シーケンス{ a _n }の二項変換Tは、シーケンス{ s _n }が次のように定義されるもの である。

$${\displaystyle s_{n}=\sum _{k=0}^{n}(-1)^{k}{\binom {n}{k}}a_{k}.}$$

正式には次のように書くことができる。

$${\displaystyle s_{n}=(Ta)_{n}=\sum _{k=0}^{n}T_{nk}a_{k}}$$

変換は、Tが行列要素T _nkを持つ無限次元演算子であるときに行われる。この変換は反転であり、つまり

$${\displaystyle TT=1}$$

または、インデックス表記を使用すると、

$${\displaystyle \sum _{k=0}^{\infty }T_{nk}T_{km}=\delta _{nm}}$$

クロネッカーのデルタはどこにありますか？元の級数は次のようにして復元できます。 ${\displaystyle \delta _{nm}}$

$${\displaystyle a_{n}=\sum _{k=0}^{n}(-1)^{k}{\binom {n}{k}}s_{k}.}$$

数列の二項変換は数列のn番目の前方差分であり、奇数差分には負の符号が付きます。つまり、次のようになります。

$${\displaystyle {\begin{aligned}s_{0}&=a_{0}\\s_{1}&=-(\Delta a)_{0}=-a_{1}+a_{0}\\s_{2}&=(\Delta ^{2}a)_{0}=-(-a_{2}+a_{1})+(-a_{1}+a_{0})=a_{2}-2a_{1}+a_{0}\\&\;\;\vdots \\s_{n}&=(-1)^{n}(\Delta ^{n}a)_{0}\end{aligned}}}$$

ここでΔは前進差分演算子です。

一部の著者は、二項変換を余分な符号で定義し、それが自己逆にならないようにしています。

$${\displaystyle t_{n}=\sum _{k=0}^{n}(-1)^{n-k}{\binom {n}{k}}a_{k}}$$

その逆は

$${\displaystyle a_{n}=\sum _{k=0}^{n}{\binom {n}{k}}t_{k}.}$$

この場合、前者の変換は逆二項変換と呼ばれ、後者は単に二項変換と呼ばれます。これは、例えば「On-Line Encyclopedia of Integer Sequences」などにおける標準的な用法です。

例

二項変換の両方のバージョンは差分表に現れます。次の差分表を考えてみましょう。

0		1		10		63		324		1485
	1		9		53		261		1161
		8		44		208		900
			36		164		692
				128		528
					400

各行は前の行の差分です。（m行目のn番目の数はa _{m , n} = 3 ^{n −2} (2 ^{m +1} n ² + 2 ^m (1+6 m ) n + 2 ^{m -1} 9 m ²）であり、差分方程式a _{m +1, n} = a _{m , n +1} - a _{m , n}が成り立ちます。）

一番上の行を左から右に読むと、{ a _n } = 0、1、10、63、324、1485、... となります。同じ開始点 0 を持つ対角線は、{ t _n } = 0、1、8、36、128、400、... となります。{ t _n } は、{ a _n }の非反転二項変換です。

一番上の行を右から左に読むと、{ b _n } = 1485, 324, 63, 10, 1, 0, ... となります。同じ開始点 1485 を持つ交差対角線は、{ s _n } = 1485, 1161, 900, 692, 528, 400, ... となります。{ s _n } は、{ b _n }の逆二項変換です。

通常の生成関数

変換は級数に関連付けられた生成関数を結び付ける。通常の生成関数については、

$${\displaystyle f(x)=\sum _{n=0}^{\infty }a_{n}x^{n}}$$

そして

$${\displaystyle g(x)=\sum _{n=0}^{\infty }s_{n}x^{n}}$$

それから

$${\displaystyle g(x)=(Tf)(x)={\frac {1}{1-x}}f{\left({\frac {-x}{1-x}}\right)}.}$$

オイラー変換

通常の母関数間の関係は、オイラー変換と呼ばれることもあります。これは通常、2つの異なる方法で現れます。1つの形は、交代級数の収束を加速するために使用されます。つまり、次の恒等式が成り立ちます。

$${\displaystyle \sum _{n=0}^{\infty }{\left(-1\right)}^{n}a_{n}=\sum _{n=0}^{\infty }{\left(-1\right)}^{n}{\frac {(\Delta ^{n}a)_{0}}{2^{n+1}}}}$$

これは、上記の最後の式にx = 1/2 を代入することで得られます。右辺の項は通常、はるかに小さくなり、はるかに急速に減少するため、数値積分を迅速に行うことができます。

オイラー変換は一般化できます (Borisov B. および Shkodrov V.、2007)。

$${\displaystyle \sum _{n=0}^{\infty }{\left(-1\right)}^{n}{\binom {n+p}{n}}a_{n}=\sum _{n=0}^{\infty }{\left(-1\right)}^{n}{\binom {n+p}{n}}{\frac {(\Delta ^{n}a)_{0}}{2^{n+p+1}}},}$$

ここでp = 0, 1, 2,...。

オイラー変換はオイラー超幾何積分 にも頻繁に適用されます。ここで、オイラー変換は次の形をとります。 ${\displaystyle \,_{2}F_{1}}$

$${\displaystyle \,_{2}F_{1}(a,b;c;z)=(1-z)^{-b}\,_{2}F_{1}\left(c-a,b;c;{\frac {z}{z-1}}\right).}$$

[他の超幾何級数への一般化については^[1]を参照]

二項変換、およびそのオイラー変換としての変形は、数の連分数表現との関連で注目される。連分数表現が ${\displaystyle 0<x<1}$

$${\displaystyle x=[0;a_{1},a_{2},a_{3},\cdots ]}$$

それから

$${\displaystyle {\frac {x}{1-x}}=[0;a_{1}-1,a_{2},a_{3},\cdots ]}$$

そして

$${\displaystyle {\frac {x}{1+x}}=[0;a_{1}+1,a_{2},a_{3},\cdots ].}$$

指数生成関数

指数生成関数については、

$${\displaystyle {\overline {f}}(x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}}$$

そして

$${\displaystyle {\overline {g}}(x)=\sum _{n=0}^{\infty }s_{n}{\frac {x^{n}}{n!}}}$$

それから

$${\displaystyle {\overline {g}}(x)=(T{\overline {f}})(x)=e^{x}{\overline {f}}(-x).}$$

ボレル変換は、通常の生成関数を指数生成関数に変換します。

二項畳み込み

とを複素数列とします。これらの二項畳み込みは で定義されます。 この畳み込みは、RL Graham、DE Knuth、O. Patashnik 共著『Concrete Mathematics : A Foundation for Computer Science』（Addison-Wesley、1989年）に記載されています。二項畳み込みが結合法則と可換法則を満たし、とで定義される列が二項畳み込みのもとで恒等式となることは容易に理解できます。さらに、 の列には逆数が存在することも容易に理解できます。したがって、 の列の集合は二項畳み込みのもとでアーベル群を形成します。 ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ ${\displaystyle (b_{n})_{n\in \mathbb {N} }}$ $${\displaystyle (a\circ b)_{n}=\sum _{k=0}^{n}{\binom {n}{k}}a_{k}b_{n-k},\ \ n=0,1,2,\ldots }$$ ${\displaystyle \{e_{n}\}}$ ${\displaystyle e_{0}=1}$ ${\displaystyle e_{n}=0}$ ${\displaystyle n=1,2,\ldots ,}$ ${\displaystyle \{a_{n}\}}$ ${\displaystyle a_{0}\neq 0}$ ${\displaystyle \{a_{n}\}}$ ${\displaystyle a_{0}\neq 0}$

二項畳み込みは指数関数の積から自然に生じます。実際、 $${\displaystyle \left(\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}\right)\left(\sum _{n=0}^{\infty }b_{n}{\frac {x^{n}}{n!}}\right)=\sum _{n=0}^{\infty }(a\circ b)_{n}{\frac {x^{n}}{n!}}.}$$

二項変換は二項畳み込みを用いて表すことができます。すべての に対してととします。すると、 は二項畳み込みの下での逆数である ため、この式は メビウス反転型の式として解釈できます 。 ${\displaystyle \lambda _{n}=(-1)^{n}}$ ${\displaystyle 1_{n}=1}$ ${\displaystyle n}$ $${\displaystyle (Ta)_{n}=(\lambda a\circ 1)_{n}.}$$ $${\displaystyle t_{n}=\sum _{k=0}^{n}{\left(-1\right)}^{n-k}{\binom {n}{k}}a_{k}\iff a_{n}=\sum _{k=0}^{n}{\binom {n}{k}}t_{k}}$$ $${\displaystyle t_{n}=(a\circ \lambda )_{n}\iff a_{n}=(t\circ 1)_{n}}$$ ${\displaystyle \lambda _{n}}$ ${\displaystyle 1_{n}}$

数学文献には、別の二項畳み込みも存在します。算術関数 と の二項畳み込みは、と定義されます。ここで、 は正の整数 の標準因数分解、は二項係数です。この畳み込みは、PJ McCarthy (1986) の著書に掲載され、L. Toth と P. Haukkanen (2009) によってさらに研究されました。 ${\displaystyle f}$ ${\displaystyle g}$ $${\displaystyle (f\circ _{B}g)(n)=\sum _{d\mid n}\left(\prod _{p}{\binom {\nu _{p}(n)}{\nu _{p}(d)}}\right)f(d)g(n/d),}$$ ${\displaystyle n=\prod _{p}p^{\nu _{p}(n)}}$ ${\displaystyle n}$ ${\displaystyle {\binom {\nu _{p}(n)}{\nu _{p}(d)}}}$

積分表現

シーケンスを複素解析関数で補間できる場合、シーケンスの二項変換は補間関数上のNörlund–Rice 積分によって表すことができます。

一般化

プロディンガーは、関連するモジュラー的な変換を提示している。

$${\displaystyle u_{n}=\sum _{k=0}^{n}{\binom {n}{k}}a^{k}{\left(-c\right)}^{n-k}b_{k}}$$

与える

$${\displaystyle U(x)={\frac {1}{cx+1}}B{\left({\frac {ax}{cx+1}}\right)}}$$

ここで、UとBはそれぞれ、級数とに関連付けられた通常の生成関数です。 ${\displaystyle \{u_{n}\}}$ ${\displaystyle \{b_{n}\}}$

上昇k二項変換は次のように定義されることがある。

$${\displaystyle \sum _{j=0}^{n}{\binom {n}{j}}j^{k}a_{j}.}$$

下降k二項変換は

$${\displaystyle \sum _{j=0}^{n}{\binom {n}{j}}j^{n-k}a_{j}.}$$

どちらも、級数のハンケル変換の核の準同型です。

二項変換が次のように定義されている場合

$${\displaystyle \sum _{i=0}^{n}{\left(-1\right)}^{n-i}{\binom {n}{i}}a_{i}=b_{n}.}$$

これを関数と等しくする ${\displaystyle {\mathfrak {J}}(a)_{n}=b_{n}.}$

新しい順方向差分表を作成し、この表の各行の最初の要素を取って新しいシーケンスを形成すると、元のシーケンスの2番目の二項変換は次のようになります。 ${\displaystyle \{b_{n}\}}$

$${\displaystyle {\mathfrak {J}}^{2}(a)_{n}=\sum _{i=0}^{n}(-2)^{n-i}{\binom {n}{i}}a_{i}.}$$

同じプロセスをk回繰り返すと、

$${\displaystyle {\mathfrak {J}}^{k}(a)_{n}=b_{n}=\sum _{i=0}^{n}(-k)^{n-i}{\binom {n}{i}}a_{i}.}$$

その逆は、

$${\displaystyle {\mathfrak {J}}^{-k}(b)_{n}=a_{n}=\sum _{i=0}^{n}k^{n-i}{\binom {n}{i}}b_{i}.}$$

これを一般化すると、

$${\displaystyle {\mathfrak {J}}^{k}(a)_{n}=b_{n}=(\mathbf {E} -k)^{n}a_{0}}$$

ここではシフト演算子です。 ${\displaystyle \mathbf {E} }$

その逆は

$${\displaystyle {\mathfrak {J}}^{-k}(b)_{n}=a_{n}=(\mathbf {E} +k)^{n}b_{0}.}$$

参照

• ニュートン級数
• ハンケル行列
• メビウス変換
• スターリング変換
• オイラー和
• 二項QMF
• リーマン・リウヴィル積分
• 階乗と二項式のトピックのリスト

参考文献

1. Miller, Allen R.; Paris, RB (2010). 「一般化超幾何関数のオイラー型変換」. Z. Angew. Math. Phys . 62 (1): 31– 45. doi :10.1007/s00033-010-0085-0. S2CID  30484300.

• ジョン・H・コンウェイとリチャード・K・ガイ、1996年、『民数記』
• Donald E. Knuth, The Art of Computer Programming Vol. 3、(1973) Addison-Wesley、Reading、MA。
• Helmut Prodinger、「二項変換についてのいくつかの情報」、The Fibonacci Quarterly 32 (1994)、412-415。
• Spivey, Michael Z.; Steil, Laura L. (2006). 「k-二項変換とハンケル変換」. Journal of Integer Sequences . 9 : 06.1.1.書誌コード:2006JIntS...9...11S.
• Borisov, B.; Shkodrov, V. (2007). 「一般化二項変換における発散級数」.上級研究継続数学. 14 (1): 77– 82.
• Khristo N. Boyadzhiev、「二項変換に関する注記、理論と表、およびスターリング変換の付録」(2018)、World Scientific。
• RL Graham、DE Knuth、O. Patashnik：「具体的な数学：コンピュータサイエンスの基礎」、Addison-Wesley（1989年）。
• PJ McCarthy, 算術関数入門、Springer-Verlag、1986年。
• P. Haukkanen、算術関数の二項畳み込みについて、Nieuw Arch。ウィスク。 (IV) 14 (1996)、no. 2、209--216。
• L. Toth と P. Haukkanen、「算術関数の二項畳み込みについて」、J. Combinatorics and Number Theory 1(2009)、31-48。
• P. Haukkanen, 通常の母関数を用いたいくつかの二項反転. Publ. Math. Debr. 47, No. 1-2, 181-191 (1995).

外部リンク

• Wolfram MathWorldでの二項変換
• OEIS wikiの二項変換

Retrieved from "https://en.wikipedia.org/w/index.php?title=Binomial_transform&oldid=1319752493#Euler_transform"