部分和を次数にとる母関数を用いて問題を解きたい

簡単な紹介

ぱっと, 定理を見てどんな風になるのか分かりにくいかもしれないので, 分からなかったときは下の例題で雰囲気を感じてもらえればいいです.

集合

{a_{n} (1), a_{n} (2), \dots, a_{n} (N_{n})}_{n \in N}

の要素を

1

個ずつ取った和を次数に取る多項式

$f (x) := \prod_{i = 1}^{n} (\sum_{j = 1}^{N_{i}} x^{a_{i} (j)}) = (x^{a_{1} (1)} + \dots + x^{a_{1} (N_{1})}) (x^{a_{2} (1)} + \dots + x^{a_{2} (N_{2})}) \dots (x^{a_{n} (1)} + \dots + x^{a_{n} (N_{n})})$

例題

次の例題を解きたいと思います.

整数列 ${a_{n}}$ は $1 \leq a_{k} \leq 3 k (k = 1, 2 \dots, n)$ を満たす.
$a_{1} + a_{2} + \dots + a_{n}$ が $3$ で割れるような組数 $S$ を求めよ.

$f (x) := \prod_{k = 1}^{n} (\sum_{l = 1}^{3 k} x^{l}) = (x + x^{2} + x^{3}) (x + x^{2} + \dots + x^{6}) \dots (x + x^{2} + \dots + x^{3 n})$
と定める.
$a_{1} + \dots + a_{n}$ で表される数を小さい順に $S_{1}, S_{2}, \dots$ とし, $S_{n}$ になる組数を $A_{n}$ とする.
$f (x) = A_{1} x^{S_{1}} + A_{2} x^{S_{2}} + \dots + A_{\frac{3}{2} n^{2} + \frac{1}{2} n + 1} x^{S_{\frac{3}{2} n^{2} + \frac{1}{2} n + 1}}$
と表せる.

$n \in N, ω = - \frac{1}{2} + \frac{\sqrt{3}}{2}$ とする.
$ω^{n} + ω^{2 n} + ω^{3 n} = {\begin{cases} 3 & (n \equiv 0 \mod 3) \\ 0 & (n ≢ 0 \mod 3) \end{cases}$

定理より, $f (ω) + f (ω^{2}) + f (ω^{3})$ は次のようになる.
$f (ω) + f (ω^{2}) + f (ω^{3}) = A_{1} (ω^{S_{1}} + ω^{2 S_{1}} + ω^{3 S_{1}}) + A_{2} (ω^{S_{2}} + ω^{2 S_{2}} + ω^{3 S_{2}}) + \dots + A_{\frac{3}{2} n^{2} + \frac{1}{2} n + 1} (ω^{S_{\frac{3}{2} n^{2} + \frac{1}{2} n + 1}} + ω^{2 S_{\frac{3}{2} n^{2} + \frac{1}{2} n + 1}} + ω^{3 S_{\frac{3}{2} n^{2} + \frac{1}{2} n + 1}})$
$f (ω) + f (ω^{2}) + f (ω^{3}) = 3 \cdot (a_{1} + \dots + a_{n} が 3 で割れるものの総数)$
$f (x) = \prod_{k = 1}^{n} (\sum_{l = 1}^{3 k} x^{l}) = \prod_{k = 1}^{n} \frac{x^{3 k + 1} - x}{x - 1}$
と表せるから, $ω^{3} = 1$ より
$f (ω^{3}) = f (1) = \prod_{k = 1}^{n} 3 k = 3^{n} n!, f (ω) = \prod_{k = 1}^{n} \frac{ω^{3 k + 1} - ω}{ω - 1} = 0, f (ω^{2}) = \prod_{k = 1}^{n} \frac{ω^{6 k + 2} - ω^{2}}{ω^{2} - 1} = 0$
$∴ f (ω) + f (ω^{2}) + f (ω^{3}) = 3^{n} n! + 0 + 0 = 3^{n} n!$
全体を $3$ で割ると, 求める組数は $3^{n - 1} n!$

ちょっと拡張

A_{n} \in {a_{n} (1), a_{n} (2), \dots, a_{n} (N_{n})}_{n \in N}

の和

c_{1} A_{1} + c_{2} A_{2} + \dots + c_{n} A_{n}

を次数に取る多項式

$f (x) := \prod_{i = 1}^{n} (\sum_{j = 1}^{N_{i}} x^{c_{i} a_{i} (j)}) = (x^{c_{1} a_{1} (1)} + \dots + x^{c_{1} a_{1} (N_{1})}) (x^{c_{2} a_{2} (1)} + \dots + x^{c_{2} a_{2} (N_{2})}) \dots (x^{c_{n} a_{n} (1)} + \dots + x^{c_{n} a_{n} (N_{n})})$

A_{n} \in {a_{n} (1), a_{n} (2), \dots, a_{n} (N_{n})}_{n \in N} \subset Z

のとき,

c_{1} A_{1} + c_{2} A_{2} + \dots + c_{n} A_{n}

の期待値

$\frac{d}{d x} \log f (x) |_{x = 1} = \frac{f^{'} (1)}{f (1)}$

(雑に)

$A_{n} \in {a_{n} (1), a_{n} (2), \dots, a_{n} (N_{n})}_{n \in N}$ の和 $c_{1} A_{1} + c_{2} A_{2} + \dots + c_{n} A_{n}$ を次数に取る多項式は
$f (x) := \prod_{i = 1}^{n} (\sum_{j = 1}^{N_{i}} x^{c_{i} a_{i} (j)})$
である.
$c_{1} A_{1} + c_{2} A_{2} + \dots + c_{n} A_{n}$ で表される数を小さい順に $S_{1}, S_{2}, \dots, S_{m} (m = max {c_{1} A_{1} + c_{2} A_{2} + \dots + c_{n} A_{n}})$ とし, $S_{n}$ になる組数を $B_{n}$ とする.
$f (x) = B_{1} x^{S_{1}} + B_{2} x^{S_{2}} + \dots + B_{m} x^{S_{m}}$
和が $S_{n}$ になる確率は $P (X = S_{n}) = \frac{B_{n}}{B_{1} + B_{2} + \dots + B_{m}} = \frac{B_{n}}{f (1)} (n = 1, 2, \dots, m)$ となるので,
$\frac{f (x)}{f (1)} = P (X = S_{1}) x^{S_{1}} + P (X = S_{2}) x^{S_{2}} + \dots + P (X = S_{m}) x^{S_{m}}$
両辺を微分して, $x = 1$ を代入すると,
$\frac{f^{'} (x)}{f (1)} = S_{1} P (X = S_{1}) x^{S_{1} - 1} + S_{2} P (X = S_{2}) x^{S_{2} - 1} + \dots + S_{m} P (X = S_{m}) x^{S_{m} - 1}$
$\frac{d}{d x} \log f (x) |_{x = 1} = \frac{f^{'} (1)}{f (1)} = S_{1} P (X = S_{1}) + S_{2} P (X = S_{2}) + \dots + S_{m} P (X = S_{m}) = \sum_{k = 1}^{m} S_{k} P (X = S_{k})$
よって, 期待値が求まる.