数列の部分和を次数に持つ母関数
簡単な紹介
ぱっと, 定理を見てどんな風になるのか分かりにくいかもしれないので, 分からなかったときは下の例題で雰囲気を感じてもらえればいいです.
集合$\{a_n(1),\,a_n(2),\,\cdots,\,a_n(N_n)\}_{n\in\mathbb{N}}$の要素を$1$個ずつ取った和を次数に取る多項式は
$$\prod_{i=1}^n \left(\sum_{j=1}^{N_i} x^{a_i(j)}\right)=(x^{a_1(1)}+\cdots+x^{a_1(N_1)})(x^{a_2(1)}+\cdots+x^{a_2(N_2)})\cdots(x^{a_n(1)}+\cdots+x^{a_n(N_n)})$$
となる. 各$x^k$の係数は集合$\{a_n(1),\,a_n(2),\,\cdots,\,a_n(N_n)\}_{n\in\mathbb{N}}$の要素を$1$個ずつ取った和が$k$になる組数に一致する.
例題
次の例題を解きたいと思います.
整数列$\{a_n\}$は$1\leq a_k\leq 3k\,(k=1,\,2\,\cdots,\,n)$を満たす.
$a_1+a_2+\cdots+a_n$が$3$で割れるような組数$S$を求めよ.
$$f(x):=\prod_{k=1}^n \left(\sum_{l=1}^{3k} x^{l}\right)=(x+x^2+x^3)(x+x^2+\cdots+x^6)\cdots(x+x^2+\cdots+x^{3n})$$
と定める.
$a_1+\cdots+a_n$で表される数を小さい順に$S_1,\,S_2,\,\cdots$とし, $S_n$になる組数を$A_n$とする.
$$f(x)=A_1 x^{S_1}+A_2 x^{S_2}+\cdots+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\mathbb{N},\,\omega=-\dfrac{1}{2}+\dfrac{\sqrt{3}}{2}$とする.
$$
\omega^n+\omega^{2n}+\omega^{3n}=
\begin{cases}
3 & (n\equiv0\mod3)\\
0 & (n\not\equiv0\mod3)
\end{cases}
$$
が成り立つ.
これより$f(\omega)+f(\omega^2)+f(\omega^3)$は次のようになる.
$$
f(\omega)+f(\omega^2)+f(\omega^3)=A_1 (\omega^{S_1}+\omega^{2S_1}+\omega^{3S_1})+A_2 (\omega^{S_2}+\omega^{2S_2}+\omega^{3S_2})+\cdots+A_{\frac{3}{2}n^2+\frac{1}{2}n+1}(\omega^{S_{\frac{3}{2}n^2+\frac{1}{2}n+1}}+\omega^{2S_{\frac{3}{2}n^2+\frac{1}{2}n+1}}+\omega^{3S_{\frac{3}{2}n^2+\frac{1}{2}n+1}})
$$
$$f(\omega)+f(\omega^2)+f(\omega^3)=3\cdot(a_1+\cdots+a_n\text{が}3\text{で割れるものの総数})$$
$$f(x)=\prod_{k=1}^n \left(\sum_{l=1}^{3k} x^{l}\right)=\prod_{k=1}^n \dfrac{x^{3k+1}-x}{x-1}$$
と表せるから, $\omega^3=1$より
$$f(\omega^3)=f(1)=\prod_{k=1}^n 3k=3^nn!,\,f(\omega)=\prod_{k=1}^n \dfrac{\omega^{3k+1}-\omega}{\omega-1}=0,\,f(\omega^2)=\prod_{k=1}^n \dfrac{\omega^{6k+2}-\omega^2}{\omega^2-1}=0$$
$\therefore f(\omega)+f(\omega^2)+f(\omega^3)=3^n n!+0+0=3^n n!$
全体を$3$で割ると, 求める組数は$3^{n-1}n!$
拡張
要素$A_n\in\{a_n(1),\,a_n(2),\,\cdots,\,a_n(N_n)\}_{n\in\mathbb{N}}$の和$c_1 A_1+c_2 A_2+\cdots+c_n A_n$を次数に取る多項式は
$$\prod_{i=1}^n \left(\sum_{j=1}^{N_i} x^{c_i a_i(j)}\right)=(x^{c_1 a_1(1)}+\cdots+x^{c_1 a_1(N_1)})(x^{c_2 a_2(1)}+\cdots+x^{c_2 a_2(N_2)})\cdots(x^{c_n a_n(1)}+\cdots+x^{c_n a_n(N_n)})$$
となる. 各$x^k$の係数は$c_1 A_1+c_2 A_2+\cdots+c_n A_n=k$になる組数に一致する.
要素$A_n\in\{a_n(1),\,a_n(2),\,\cdots,\,a_n(N_n)\}_{n\in\mathbb{N}}\subset\mathbb{Z}$とする.
$$f(x)=\prod_{i=1}^n \left(\sum_{j=1}^{N_i} x^{c_i a_i(j)}\right)=(x^{c_1 a_1(1)}+\cdots+x^{c_1 a_1(N_1)})(x^{c_2 a_2(1)}+\cdots+x^{c_2 a_2(N_2)})\cdots(x^{c_n a_n(1)}+\cdots+x^{c_n a_n(N_n)})$$
としたとき, $c_1 A_1+c_2 A_2+\cdots+c_n A_n$の期待値は
$$\dfrac{d}{dx}\log{f(x)}\bigg|_{x=1}=\dfrac{f'(1)}{f(1)}$$
となる.
$A_n\in\{a_n(1),\,a_n(2),\,\cdots,\,a_n(N_n)\}_{n\in\mathbb{N}}$の和$c_1 A_1+c_2 A_2+\cdots+c_n A_n$を次数に取る多項式は
$$f(x)=\prod_{i=1}^n \left(\sum_{j=1}^{N_i} x^{c_i a_i(j)}\right)$$
である.
$c_1 A_1+c_2 A_2+\cdots+c_n A_n$を小さい順に$S_1,\,S_2,\,\cdots,\,S_m\,(m=\max\{c_1 A_1+c_2 A_2+\cdots+c_n A_n\mid n\in\mathbb{N}\})$とし, $f(x)$の各$x^{S_k}$の係数$B_k$とすると
$$
f(x)=B_1 x^{S_1}+B_2 x^{S_2}+\cdots+B_m x^{S_m}
$$
と表せる.
和が$S_n$になる確率は$P(X=S_n)=\dfrac{B_n}{B_1+B_2+\cdots+B_m}=\dfrac{B_n}{f(1)}\,(n=1,\,2,\,\cdots,\,m)$となるので,
$$
\dfrac{f(x)}{f(1)}=P(X=S_1)x^{S_1}+P(X=S_2)x^{S_2}+\cdots+P(X=S_m)x^{S_m}
$$
両辺を微分して, $x=1$を代入すると,
$$
\dfrac{f'(x)}{f(1)}=S_1 P(X=S_1)x^{S_1-1}+S_2 P(X=S_2)x^{S_2-1}+\cdots+S_m P(X=S_m)x^{S_m-1}
$$
$$
\dfrac{d}{dx}\log{f(x)}\bigg|_{x=1}=\dfrac{f'(1)}{f(1)}=S_1 P(X=S_1)+S_2 P(X=S_2)+\cdots+S_m P(X=S_m)=\sum_{k=1}^m S_k P(X=S_k)
$$
次は定理1の考え方を利用した命題です.
$\{a_n\}_{n\in\mathbb{N}\cup\{0\}}$の母関数から$\{\sum_{k=0}^n a_k\}$の母関数を生成できる.
$$
\sum_{k=0}^\infty \left(\sum_{l=0}^k a_l\right)x^k=\frac{1}{1-x}\left(\sum_{k=0}^\infty a_k x^k\right)
$$
$$
\frac{1}{1-x}=\sum_{n=0}^\infty x^n\,(|x|<1)
$$
が成り立つ. 定理の考えを利用すると, $\{a_n\}$の母関数の項$x^s$と$1/(1-x)$の級数展開の項$x^t$を取ると, 2つの多項式の積は
$$
\frac{1}{1-x}\left(\sum_{k=0}^\infty a_k x^k\right)=\sum_{k=0}^\infty\left(\sum_{s+t=k} a_s\right)x^k=\sum_{k=0}^\infty \left(\sum_{s=0}^k a_s\right)x^k
$$
大体の問題は別の簡単な解法が存在するので、そんなに強いテクニックというわけではないのですが、応用が利きそうなので色々考えたいですね。
