二項変換

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

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

${\displaystyle s_{n}=\sum _{k=0}^{n}(-1)^{k}{n \choose 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}{n \choose 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}{n \choose k}a_{k}}$

その逆は

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

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

二項変換の両方のバージョンは差分表に表示されます。次の差分表を検討してください。

各行は前の行の差分です。（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 }(-1)^{n}a_{n}=\sum _{n=0}^{\infty }(-1)^{n}{\frac {(\Delta ^{n}a)_{0}}{2^{n+1}}}}$

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

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

${\displaystyle \sum _{n=0}^{\infty }(-1)^{n}{n+p \choose n}a_{n}=\sum _{n=0}^{\infty }(-1)^{n}{n+p \choose 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).}$

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

とを複素数の列とする。それらの二項畳み込みは次のように定義される 。${\displaystyle \{a_{n}\}}$${\displaystyle \{b_{n}\}}$${\displaystyle n=0,1,2,\ldots ,}$

${\displaystyle (a\circ b)_{n}=\sum _{k=0}^{n}{n \choose k}a_{k}b_{n-k},\ \ n=0,1,2,\ldots }$

この畳み込みは、RL Graham、DE Knuth、O. Patashnik の著書「Concrete Mathematics: A Foundation for Computer Science」(Addison-Wesley、1989 年) に記載されています。二項畳み込みが結合的かつ可換であること、および およびで定義される シーケンスが二項畳み込みの下で恒等式として機能することは容易にわかります。さらに、 のシーケンスには逆が存在することも容易にわかります。したがって、 のシーケンスの集合は、二項畳み込みの下でアーベル群を形成します。 ${\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}{x^{n} \over n!}\right)\left(\sum _{n=0}^{\infty }b_{n}{x^{n} \over n!}\right)=\sum _{n=0}^{\infty }(a\circ b)_{n}{x^{n} \over 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}(-1)^{n-k}{n \choose k}a_{k}\iff a_{n}=\sum _{k=0}^{n}{n \choose k}t_{k}}$

メビウス反転型の式として解釈できる

${\displaystyle t_{n}=(a\circ \lambda )_{n}\iff a_{n}=(t\circ 1)_{n}}$

は二項畳み込みの下で は の逆数である ためです。${\displaystyle \lambda _{n}}$${\displaystyle 1_{n}}$

数学文献にはもう一つの二項畳み込みがある。算術関数の二項畳み込みは 次のように定義される。 ${\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),}$

ここで、 は正の整数の標準因数分解であり、は二項係数です。この畳み込みは PJ McCarthy (1986) の著書に記載されており、L. Toth と P. Haukkanen (2009) によってさらに研究されました。 ${\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}{n \choose k}a^{k}(-c)^{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}{n \choose j}j^{k}a_{j}.}$

下降k二項変換は

${\displaystyle \sum _{j=0}^{n}{n \choose j}j^{n-k}a_{j}}$。

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

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

${\displaystyle \sum _{i=0}^{n}(-1)^{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
• リーマン・リウヴィル積分
• 階乗と二項式のトピックのリスト

• ジョン・H・コンウェイとリチャード・K・ガイ、1996年、「民数記」
• Donald E. Knuth, The Art of Computer Programming Vol. 3、(1973) Addison-Wesley、Reading、MA。
• Helmut Prodinger、1992、二項変換についてのいくつかの情報 2007-03-12 にWayback Machineでアーカイブ
• 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: Concrete Mathematics: A Foundation for Computer Science、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)。

• 二項変換
• 整数列の変換