大学数学基礎解説

二項変換とメビウス変換

母関数,二項係数,変換

242

はじめに

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

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

定義と諸定理

二項変換

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

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

母関数との関係

数列 $(a_{n}) = (a_{0}, a_{1}, \dots)$ , $(b_{n}) = (b_{0}, b_{1}, \dots)$ に対して
$F (X) = \sum_{n = 0}^{\infty} a_{n} X^{n}, G (X) = \sum_{n = 0}^{\infty} b_{n} X^{n}$
をその母関数とする.
このとき, 以下同値となる.

$(b_{n})$ は $(a_{n})$ の二項変換である.
$G (X) = \frac{1}{1 - X} F (\frac{X}{X - 1})$ が成り立つ.

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

二項係数の母関数

非負整数 $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)^{m} X^{m}$
であり, 自然数 $m$ に対して
$\begin{aligned} (\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{aligned}$
となる.
ここで, $(\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{aligned} G (X) & = \sum_{n = 0}^{\infty} b_{n} X^{n} \\ = \sum_{n = 0}^{\infty} (\sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k}) a_{k}) X^{n} \\ = \sum_{k = 0}^{\infty} (- 1)^{k} a_{k} (\sum_{n = k}^{\infty} (\binom{n}{k}) X^{n}) \\ = \sum_{k = 0}^{\infty} (- 1)^{k} a_{k} \frac{X^{k}}{(1 - X)^{k + 1}} \\ = \frac{1}{1 - X} F (\frac{X}{X - 1}) \end{aligned}$
となる.
これは可逆な操作のため逆も成り立つことから, 題意が示された.

母関数による特徴付け

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

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

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

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

変換と行列の積との関係

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

二次正方行列 $A = (\begin{matrix} a & b \\ c & d \end{matrix})$ , $B = (\begin{matrix} p & q \\ r & s \end{matrix})$
を任意にとり固定する.
$B A = (\begin{matrix} p & q \\ r & s \end{matrix}) (\begin{matrix} a & b \\ c & d \end{matrix}) = (\begin{matrix} p a + q c & p b + q d \\ r a + s c & r b + s d \end{matrix})$
より,
$F (X)^{B A} = \frac{1}{(r a + s c) X + (r b + s d)} F (\frac{(p a + q c) X + (p b + q d)}{(r a + s c) X + (r b + s d)})$
であり,
$\begin{aligned} (F (X)^{B})^{A} & = {(\frac{1}{r X + s} F (\frac{p X + q}{r X + s}))}^{A} \\ = \frac{1}{c X + d} \cdot \frac{1}{r \frac{a X + b}{c X + d} + s} F (\frac{p \frac{a X + b}{c X + d} + q}{r \frac{a X + b}{c X + d} + s}) \\ = \frac{1}{c X + d} \cdot \frac{c X + d}{r (a X + b) + s (c X + d)} F (\frac{p (a X + b) + q (c X + d)}{r (a X + b) + s (c X + d)}) \\ = \frac{1}{(r a + s c) X + (r b + s d)} F (\frac{(p a + q c) X + (p b + q d)}{(r a + s c) X + (r b + s d)}) \end{aligned}$
より
$F (X)^{B A} = (F (X)^{B})^{A}$
が成り立つ.

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

二項変換の拡張

二次正方行列 $A = (\begin{matrix} a & b \\ c & d \end{matrix})$ と数列 $(a_{n}) = (a_{0}, a_{1}, \dots)$ に対して, 変換 $(a_{n}) \mapsto (a_{n})^{A} = (b_{n})$ を以下の条件を満たすように定義する:

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

二次正方行列 $A$ を $A = (\begin{matrix} - 1 & 0 \\ - 1 & 1 \end{matrix})$ としたとき, 数列 $(a_{n}) = (a_{0}, a_{1}, \dots)$ による母関数 $F (X)$ に対して
$\begin{aligned} F (X)^{A} & = \frac{1}{- X + 1} F (\frac{- X}{- X + 1}) \\ = \frac{1}{1 - X} F (\frac{X}{X - 1}) \end{aligned}$
より, 変換 $(a_{n}) \mapsto (a_{n})^{A}$ は二項変換となる.

二項変換の逆変換

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

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

二項変換以外の例

対角行列の場合

$A = (\begin{matrix} a & 0 \\ 0 & b \end{matrix})$ としたとき, 数列 $(a_{n}) = (a_{0}, a_{1}, \dots)$ による母関数 $F (X)$ に対して
$\begin{aligned} F (X)^{A} & = \frac{1}{b} F (\frac{a}{b} X) \\ = \sum_{n = 0}^{\infty} \frac{a^{n}}{b^{n + 1}} a_{n} X^{n} \end{aligned}$
より, $(a_{n})^{A} = (b_{n})$ は
$b_{n} = \frac{a^{n}}{b^{n + 1}} a_{n}, n = 0, 1, \dots$
となる.