部分和を次数にとる母関数を用いて問題を解きたい
簡単な紹介
ぱっと, 定理を見てどんな風になるのか分かりにくいかもしれないので, 分からなかったときは下の例題で雰囲気を感じてもらえればいいです.
$$f(x):=\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)})$$
例題
次の例題を解きたいと思います.
整数列$\{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!$
ちょっと拡張
$$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)})$$
$$\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\})$とし, $S_n$になる組数を$B_n$とする.
$$
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)
$$
よって, 期待値が求まる.
この集合の要素を同じものにすることによって, 重複を許したときの部分和もできます(例: 整数$k\,(k=1,\,2,\,\cdots,\,100)$が書かれたカードが$k$枚あるとき, $1$枚を引いて記録し, 戻す操作を繰り返す.).
大体の問題は別の簡単な解法が存在するので、そんなに強いテクニックというわけではないのですが、応用が利きそうなので色々考えたいですね。
