3

二項変換とメビウス変換

97
0
$$$$

はじめに

数列の二項変換は, その母関数を調べるとメビウス変換と関連付けることができる.
この観点から, 二項変換の一般化を考えてみる.

ここで, $F(X)$を数列$(a_n)$の母関数といったとき, $F(X)$は各非負整数$n$に対して$n$次係数が$a_n$であるような形式的ベキ級数であるとする.

定義と諸定理

二項変換

数列$(a_n)=(a_0,a_1,\ldots)$に対して
$$ b_n = \sum_{k=0}^{n}(-1)^k\binom{n}{k}a_k $$
で定まる数列$(b_n)=(b_0,b_1,\ldots)$を考える.
このとき, その対応$(a_n)\mapsto(b_n)$二項変換(binomial transform)と呼ぶ.

被総和内に交代数列$(-1)^k$が含まれることに着目して, 特に交代二項変換と呼ばれることもある.

母関数との関係

数列$(a_n)=(a_0,a_1,\ldots)$, $(b_n)=(b_0,b_1,\ldots)$に対して
$$ F(X) = \sum_{n=0}^{\infty}a_nX^n ,\quad G(X) = \sum_{n=0}^{\infty}b_nX^n $$
をその母関数とする.
このとき, 以下同値となる.

  1. $(b_n)$$(a_n)$の二項変換である.

  2. $G(X)=\frac{1}{1-X}F\!\left(\frac{X}{X-1}\right)$が成り立つ.

この定理を示すために以下の補題を証明する.

二項係数の母関数

非負整数$k$に対して以下の等式が成り立つ.
$$ \sum_{n=k}^{\infty}\binom{n}{k}X^{n}=\frac{X^{k}}{(1-X)^{k+1}} $$

拡張二項展開より,
$$ \frac{1}{(1-X)^{k+1}}=\sum_{m=0}^{\infty}\binom{-k-1}{m}(-1)^mX^m $$
であり, 自然数$m$に対して
$$ \begin{align*} \binom{-k-1}{m} &=\frac{1}{m!}\prod_{j=0}^{m-1}(-k-1-j)\\ &=\frac{(-1)^m}{m!}\prod_{j=0}^{m-1}(k+j+1)\\ &=\frac{(-1)^m}{m!}\prod_{j=0}^{m-1}(k+(m-1-j)+1)\\ &=\frac{(-1)^m}{m!}\prod_{j=0}^{m-1}(k+m-j)\\ &=(-1)^m\binom{k+m}{m}\\ &=(-1)^m\binom{k+m}{(k+m)-m}\\ &=(-1)^m\binom{k+m}{k}\\ \end{align*} $$
となる.
ここで, $\binom{-k-1}{0}=1$かつ$(-1)^0\binom{k+0}{k}=1$より等式
$$ \binom{-k-1}{m}=(-1)^m\binom{k+m}{k} $$
は非負整数$m$に対して成り立つ.
これらより,
$$ \frac{X^{k}}{(1-X)^{k+1}}=\sum_{m=0}^{\infty}\binom{k+m}{k}X^{k+m}=\sum_{n=k}^{\infty}\binom{n}{k}X^n $$
となり, 題意が示された.

$(b_n)$$(a_n)$の二項変換と仮定すると, lem:binom-funcより
$$ \begin{align*} G(X) &=\sum_{n=0}^{\infty}b_nX^n\\ &=\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}(-1)^k\binom{n}{k}a_k\right)X^n\\ &=\sum_{k=0}^{\infty}(-1)^ka_k\left(\sum_{n=k}^{\infty}\binom{n}{k}X^n\right)\\ &=\sum_{k=0}^{\infty}(-1)^ka_k\frac{X^{k}}{(1-X)^{k+1}}\\ &=\frac{1}{1-X}F\!\left(\frac{X}{X-1}\right) \end{align*} $$
となる.
これは可逆な操作のため逆も成り立つことから, 題意が示された.

母関数による特徴付け

二次正方行列による母関数の変換

二次正方行列$A=\bigl(\begin{smallmatrix}a&b\\c&d\\\end{smallmatrix}\bigl)$と母関数$F(X)$に対して, 以下の式が形式的ベキ級数となるときに限り, これを$F(X)$$A$による変換といい, $F(X)^A$と表す.
$$ \frac{1}{cX+d}F\!\left(\frac{aX+b}{cX+d}\right) $$

ここで, 対応
$$ X\mapsto\frac{aX+b}{cX+d} $$
メビウス変換と呼ばれているものである.

特に恒等行列$I$に対して
$$ F(X)^I=\frac{1}{0\cdot X+1}F\!\left(\frac{1\cdot X+0}{0\cdot X+1}\right)=F(X) $$
となる.

変換と行列の積との関係

二次正方行列$A,B$と母関数$F(X)$に対して, 以下の等式が両辺が定義される場合に限り成り立つ.
$$ F(X)^{BA}=(F(X)^B)^A $$

二次正方行列$A=\bigl(\begin{smallmatrix}a&b\\c&d\\\end{smallmatrix}\bigl)$, $B=\bigl(\begin{smallmatrix}p&q\\r&s\\\end{smallmatrix}\bigl)$
を任意にとり固定する.
$$ BA=\left(\begin{matrix}p&q\\r&s\\\end{matrix}\right)\left(\begin{matrix}a&b\\c&d\\\end{matrix}\right)=\left(\begin{matrix}pa+qc&pb+qd\\ra+sc&rb+sd\\\end{matrix}\right) $$
より,
$$ F(X)^{BA}=\frac{1}{(ra+sc)X+(rb+sd)}F\!\left(\frac{(pa+qc)X+(pb+qd)}{(ra+sc)X+(rb+sd)}\right) $$
であり,
$$ \begin{align*} (F(X)^B)^A &=\left(\frac{1}{rX+s}F\!\left(\frac{pX+q}{rX+s}\right)\right)^A\\ &=\frac{1}{cX+d}\cdot\frac{1}{r\frac{aX+b}{cX+d}+s}F\!\left(\frac{p\frac{aX+b}{cX+d}+q}{r\frac{aX+b}{cX+d}+s}\right)\\ &=\frac{1}{cX+d}\cdot\frac{cX+d}{r(aX+b)+s(cX+d)}F\!\left(\frac{p(aX+b)+q(cX+d)}{r(aX+b)+s(cX+d)}\right)\\ &=\frac{1}{(ra+sc)X+(rb+sd)}F\!\left(\frac{(pa+qc)X+(pb+qd)}{(ra+sc)X+(rb+sd)}\right) \end{align*} $$
より
$$ F(X)^{BA}=(F(X)^B)^A $$
が成り立つ.

この形式的ベキ級数の変換を用いて, 数列の変換を以下のように定める.

二項変換の拡張

二次正方行列$A=\bigl(\begin{smallmatrix}a&b\\c&d\\\end{smallmatrix}\bigl)$と数列$(a_n)=(a_0,a_1,\ldots)$に対して, 変換$(a_n)\mapsto(a_n)^A=(b_n)$を以下の条件を満たすように定義する:

  • $(a_n)$, $(b_n)$の母関数$F(X)=\sum_{n=0}^{\infty}a_nX^n$, $G(X)=\sum_{n=0}^{\infty}b_nX^n$に対して, 等式$F(X)^A=G(X)$が成り立つ.

二次正方行列$A$$A=\bigl(\begin{smallmatrix}-1&0\\-1&1\\\end{smallmatrix}\bigl)$としたとき, 数列$(a_n)=(a_0,a_1,\ldots)$による母関数$F(X)$に対して
$$ \begin{align*} F(X)^A &=\frac{1}{-X+1}F\!\left(\frac{-X}{-X+1}\right)\\ &=\frac{1}{1-X}F\!\left(\frac{X}{X-1}\right) \end{align*} $$
より, 変換$(a_n)\mapsto(a_n)^A$は二項変換となる.

二項変換の逆変換

二項変換の逆変換は二項変換である.
すなわち, 二項変換が冪等性を有する.

$$ \begin{align*} A^2 &=\left(\begin{matrix}-1&0\\-1&1\\\end{matrix}\right)\left(\begin{matrix}-1&0\\-1&1\\\end{matrix}\right)\\ &=\left(\begin{matrix}1&0\\0&1\\\end{matrix}\right)=I \end{align*} $$
より, 先の補題から
$$ F(X)=F(X)^{A^2}=(F(X)^A)^A $$
なため, 二項変換が冪等性を有する.

二項変換以外の例

対角行列の場合

$A=\bigl(\begin{smallmatrix}a&0\\0&b\\\end{smallmatrix}\bigl)$としたとき, 数列$(a_n)=(a_0,a_1,\ldots)$による母関数$F(X)$に対して
$$ \begin{align*} F(X)^A &=\frac{1}{b}F\!\left(\frac{a}{b}X\right)\\ &=\sum_{n=0}^{\infty}\frac{a^n}{b^{n+1}}a_nX^n \end{align*} $$
より, $(a_n)^A=(b_n)$
$$ b_n=\frac{a^n}{b^{n+1}}a_n,\quad n=0,1,\ldots $$
となる.

投稿日:20231119
更新日:20231119

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

桜武
桜武
3
134

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中