二項変換とメビウス変換
はじめに
数列の二項変換は, その母関数を調べるとメビウス変換と関連付けることができる.
この観点から, 二項変換の一般化を考えてみる.
ここで, $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
$$
をその母関数とする.
このとき, 以下同値となる.
$(b_n)$は$(a_n)$の二項変換である.
$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
$$
となる.