母関数公式

252

$f (x) = \sum_{i = 0}^{\infty} a_{i} x^{i}$ のとき,
$\begin{aligned} \sum_{i = 0}^{\infty} \sum_{j = 0}^{\infty} a_{i + j} x^{i} y^{j} = \frac{x f (x) - y f (y)}{x - y} \\ \sum_{i = 0}^{\infty} \sum_{j = 0}^{\infty} a_{i - j} x^{i} y^{j} = \frac{1}{1 - x y} f (x) \\ \sum_{i = 0}^{\infty} \sum_{j = 0}^{\infty} a_{min (i, j)} x^{i} y^{j} = \frac{1 - x y}{(1 - x) (1 - y)} f (x y) \end{aligned}$
ただし, $a_{- 1} = a_{- 2} = \dots = 0$ とする.

まず一番上を導出する.

$i + j = n$ となる $(i, j)$ について, 単項式 $x^{i} y^{j}$ の和をとると,
$\begin{array}{r} \sum_{i + j = n} x^{i} y^{j} = \frac{x^{n + 1} - y^{n + 1}}{x - y} \end{array}$
となるので, $n = 0, 1, 2, \dots$ について $a_{n} \sum_{i + j = n} x^{i} y^{j}$ の和を取ればよく,
$\begin{aligned} \sum_{i = 0}^{\infty} \sum_{j = 0}^{\infty} a_{i + j} x^{i} y^{j} & = \sum_{n = 0}^{\infty} a_{n} \sum_{i + j = n} x^{i} y^{j} \\ = \sum_{n = 0}^{\infty} a_{n} \frac{x^{n + 1} - y^{n + 1}}{x - y} \\ = \frac{x \sum_{n = 0}^{\infty} a_{n} x^{n} - y \sum_{n = 0}^{\infty} a_{n} y^{n}}{x - y} \\ = \frac{x f (x) - y f (y)}{x - y} \end{aligned}$
同様に下二つも示します.

真ん中の式

$i - j = n$ となる(非負整数) $(i, j)$ について, 単項式 $x^{i} y^{j}$ の和をとると,
$\begin{aligned} \sum_{i - j = n} x^{i} y^{j} & = \sum_{j = 0}^{\infty} x^{j + n} y^{j} \\ = x^{n} \sum_{j = 0}^{\infty} (x y)^{j} \\ = x^{n} \frac{1}{1 - x y} \end{aligned}$
となるので,
$\begin{aligned} \sum_{i = 0}^{\infty} \sum_{j = 0}^{\infty} a_{i - j} x^{i} y^{j} & = \sum_{n = 0}^{\infty} a_{n} x^{n} \frac{1}{1 - x y} \\ = \frac{1}{1 - x y} f (x) \end{aligned}$

一番下の式

$min (i, j) = n$ となる(非負整数) $(i, j)$ について, 単項式 $x^{i} y^{j}$ の和をとるのは少し工夫が要ります.
まず $min (i, j) \geq n$ となる(非負整数) $(i, j)$ について, 単項式 $x^{i} y^{j}$ の和をとると,
$\begin{aligned} \sum_{min (i, j) \geq n} x^{i} y^{j} & = \sum_{min (i, j) \geq 0} x^{i + n} y^{j + n} \\ = x^{n} y^{n} \sum_{min (i, j) \geq 0} x^{i} y^{j} \\ = x^{n} y^{n} \sum_{i = 0}^{\infty} \sum_{j = 0}^{\infty} x^{i} y^{j} \\ = x^{n} y^{n} \sum_{i = 0}^{\infty} x^{i} \sum_{j = 0}^{\infty} y^{j} \\ = x^{n} y^{n} \frac{1}{1 - x} \frac{1}{1 - y} \end{aligned}$
となり, $min (i, j) = n$ となる(非負整数) $(i, j)$ について, 単項式 $x^{i} y^{j}$ の和をとるには $min (i, j) \geq n$ となる $(i, j)$ についての和から, $min (i, j) \geq n + 1$ となる $(i, j)$ についての和を引けばよく,
$\begin{aligned} \sum_{min (i, j) = n} x^{i} y^{j} & = \sum_{min (i, j) \geq n} x^{i} y^{j} - \sum_{min (i, j) \geq n + 1} x^{i} y^{j} \\ = \frac{x^{n} y^{n}}{(1 - x) (1 - y)} - \frac{x^{n + 1} y^{n + 1}}{(1 - x) (1 - y)} \\ = \frac{(1 - x y)}{(1 - x) (1 - y)} x^{n} y^{n} \end{aligned}$
したがって,
$\begin{aligned} \sum_{i = 0}^{\infty} \sum_{j = 0}^{\infty} a_{min (i, j)} x^{i} y^{j} & = \sum_{n = 0}^{\infty} a_{n} (x y)^{n} \frac{(1 - x y)}{(1 - x) (1 - y)} \\ = \frac{1 - x y}{(1 - x) (1 - y)} f (x y) \end{aligned}$

一番上について

$x_{1}, x_{2}, \dots, x_{n}$ と変数の数を増やして一般化すると
$\sum_{i_{1}, i_{2}, \dots, i_{n}} a_{(i_{1} + \dots + i_{n})} x_{1}^{i_{1}} x_{2}^{i_{2}} \dots x_{n}^{i_{n}} = \sum_{k = 1}^{n} \frac{x_{k}^{n - 1} f (x_{k})}{(x_{k} - x_{1}) \dots (x_{k} - x_{k - 1}) (x_{k} - x_{k + 1}) \dots (x_{k} - x_{n})}$
となります.

真ん中について

変数の数を増やすとどんな拡張が得られるかはわかりません.
$\sum_{i, j, k} a_{(| i - j | + | j - k | + | k - i |)} x^{i} y^{j} z^{k}$
とかもしも計算できたら面白そう...。思い付いた方がいたら教えてください！
以下のように対称性を意識すると,
$\sum_{i = 0}^{\infty} \sum_{j = 0}^{\infty} a_{| i - j |} x^{i} y^{j} = \frac{1}{1 - x y} (f (x) + f (y) - a_{0})$
となります.

$max$ ではどうなるか,

集合として ${i, j} = {max (i, j), min (i, j)}$ なので,
$\sum_{i = 0}^{\infty} \sum_{j = 0}^{\infty} (a_{i} + a_{j}) x^{i} y^{j} = \sum_{i = 0}^{\infty} \sum_{j = 0}^{\infty} (a_{min i, j} + a_{max (i, j)}) x^{i} y^{j}$
から計算することもできます.
$x_{1}, x_{2}, \dots, x_{n}$ と変数の数を増やして一般化すると $max i_{k} = m$ となる単項式の和が
$\begin{aligned} \sum_{max (i_{k}) = m} x_{1}^{i_{1}} x_{2}^{i_{2}} \dots x_{n}^{i_{n}} & = \sum_{max (i_{k}) \leq m} x_{1}^{i_{1}} x_{2}^{i_{2}} \dots x_{n}^{i_{n}} - \sum_{max (i_{k}) \leq m - 1} x_{1}^{i_{1}} x_{2}^{i_{2}} \dots x_{n}^{i_{n}} \\ = \prod_{k = 1}^{n} \sum_{i_{k} = 0}^{m} x_{k}^{i_{k}} - \prod_{k = 1}^{n} \sum_{i_{k} = 0}^{m - 1} x_{k}^{i_{k}} \\ = \prod_{k = 1}^{n} \frac{1 - x_{k}^{m + 1}}{1 - x_{k}} - \prod_{k = 1}^{n} \frac{1 - x_{k}^{m}}{1 - x_{k}} \end{aligned}$
となり, $f$ で表現する公式を得るには $\prod_{k} (1 - x_{k}^{m + 1})$ の展開をする必要がありあまり綺麗な式はえられないような気がします.

一番下について

これを用いて組み合わせの問題を作問してみたので興味のある方は挑戦してみてください！！ポロロッカでジャッジもできます！

$4$ 行 $6$ 列のマス目の各マスに $1$ 以上 $12$ 以下の整数を書き込みます. 上から $i$ 行目, 左から $j$ 列目にあるマスに書かれた数を $a_{i, j}$ で表すとき, 以下を満たす書き込み方は何通りありますか？

$j = 1, 2, 3, 4, 5$ について以下の値が正の奇数となる.
$min_{1 \leq i \leq 4} (a_{i, j + 1} - a_{i, j})$

投稿日：1月14日

この記事を高評価した人

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

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

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

MARTH

3796

OMC黄

他の人のコメント

コメントはありません。

読み込み中

MARTH

母関数公式

母関数公式

まず一番上を導出する.

真ん中の式

一番下の式

コメント

一番上について

真ん中について

max ではどうなるか,

一番下について

この記事を高評価した人

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

投稿者

コメント

他の人のコメント

$max$ ではどうなるか,