(1+x^k) の乗積を展開したときの係数

何年か前になぜか気になって、でもそのままにしていた問題をシンプルにした物だが、数学熱が高いことを理由に改めて考えてみた。

今気にしている式は、$$\begin{align} Q_n(x) &= (1+x)(1+x^2)(1+x^3) \cdots (1+x^n) \\ &= \prod_{k=1}^{n}(1 + x^k)\end{align}$$である。この $Q_n(x)$ は $x$ の $\frac{n(n+1)}{2}$ 次式であるが、これを展開するとどうなるのかという問題。まず、展開すると、次のような形の多項式となる。$$\begin{align} Q_n(x) &= a_0 + a_1\,x + a_2\,x^2 + \cdots + a_\frac{n(n+1)}{2}\,x^\frac{n(n+1)}{2} \\ &= \sum_{r=0}^{\frac{n(n+1)}{2}}a_r\,x^r \end{align}$$

で、具体的な係数 $a_r$ が欲しいよね、というお話である。

少し扱いづらいので、$Q_n(x)$ における $x^r$ の係数を $q_n(r)$ と書くことにすると、$$Q_n(x) = \sum_{r=0}^{\frac{n(n+1)}{2}}q_n(r)\,x^r$$と書ける。

正確さを欠く説明をすれば、実際の展開を考えたとき、$r$ 次の項は、$\{x^k\}$ から最大で $n$ 個選び、掛け合わせたときに $x^r$ になりました、という組み合わせから生じる。で、その積 $x^r$ がいくつか生じたものの和が最終的な $r$ 次の項となり、その係数 $q_n(r)$ は組み合わせの総数に等しい。つまり、指数法則の面から見れば、$n$ 以下の自然数から重複を許さずいくつか選び、それらの和が $r$ となる組み合わせの総数である。

さらに別の言い方をすれば、「自然数 $r$ の分割、すなわち $r$ を（必然的に $r$ 以下の）自然数の和で表す方法のうち、それぞれの分割方法において、成分がすべて異なり（制限その 1）、かつ、成分がすべて $n$ 以下（制限その 2）であるもの」の数が $q_n(r)$ であると。

俺の苦手な初等整数論とかの話になってきたぞ。

自然数の分割 - Wikipedia

具体的に、$Q_4(x)$ を見てみる。$$\begin{align} Q_4(x) &= (1+x)(1+x^2)(1+x^3)(1+x^4) \\ &= 1+x+x^2+2x^3+2x^4+2x^5+2x^6+2x^7+x^8+x^9+x^{10} \end{align}$$

係数の構成要素は次のようになる。$$\begin{cases} q_4(1)=|\{1\}|=1 \\ q_4(2)=|\{2\}|=1 \\ q_4(3)=|\{3,\,2+1\}|=2 \\ q_4(4)=|\{4,\,3+1\}|=2 \\ q_4(5)=|\{4+1,\,3+2\}|=2 \\ q_4(6)=|\{4+2,\,3+2+1\}|=2 \\ q_4(7)=|\{4+3,\,4+2+1\}|=2 \\ q_4(8)=|\{4+3+1\}|=1 \\ q_4(9)=|\{4+3+2\}|=1 \\ q_4(10)=|\{4+3+2+1\}|=1 \end{cases}$$

例によって $r=0$ は $0$ 次の項を 4 つ掛けた 1 つの場合を考えるので、$q_4(0)=1$ なのである。上記の分割方法において、4 つの整数に満たない部分は $0$ で埋めるとすれば、$$q_4(0)=|\{0+0+0+0\}|=1$$ であり、同様に
$$q_4(3)=|\{3+0+0+0,\,2+1+0+0\}|=2$$であるので同じことであるというか、指数部の成り立ちとしてはこちらの表記のほうが無難であろう。

それはさておき、$Q_n(x)$ はそういう数 $q_n(r)$ を表す母関数と考えられる。もちろん、$r > \frac{n(n+1)}{2}$ なる $r$ については、その上記の 2 つの制限を満たすような分割は存在しないので、そのような $r$ に関しては $q_n(r)=|\{\}|=0$ と定義することができて、より一般的な母関数のように $Q_n(x)$ を$$Q_n(x) = \sum_{r=0}^\infty q_n(r)\,x^r$$といった冪級数で表すことも可能である。また、母関数の常套手段であるマクローリン展開同様のアプローチで、$$q_n(r) = \frac{Q_n^{(r)}(0)}{r!}$$と閉じた形で表せるわけだが、この高階微分を計算するときに上記の分割の話に舞い戻る。

ところで、Wikipedia にはは上記の制限 2 を除去した場合、つまり $n \to \infty$ の極限をとった場合と思われる話があったぞ。