ヨーキョクデイ

いろいろ雑食

(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) と書くことにすると、

\displaystyle 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) であると。

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

具体的に、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=00 次の項を 4 つ掛けた 1 つの場合を考えるので、q_4(0)=1 なのである。上記の分割方法において、4 つの整数に満たない部分は 0 で埋めるとすれば、

\displaystyle q_4(0)=|\{0+0+0+0\}|=1

であり、同様に

\displaystyle 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)

\displaystyle Q_n(x) = \sum_{r=0}^\infty q_n(r)\,x^r

といった冪級数で表すことも可能である。また、母関数の常套手段であるマクローリン展開同様のアプローチで、

\displaystyle q_n(r) = \frac{Q_n^{(r)}(0)}{r!}

と閉じた形で表せるわけだが、この高階微分を計算するときに上記の分割の話に舞い戻る。

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

それはそれは有名というか有用というか、メジャーな議論のようで、このような分割は "strict partition" と呼ぶらしく、下記において Partition Function Q として紹介されている。

この辺の性質は数論の人が詳しく解明しているのだろう。

続く。