ヨーキョクデイ

いろいろ雑食

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

今回は整数の分割から歩み寄る。

18 の "strict partition" を考えてみる。分割の最大成分ごとに分けて書くと、

\begin{align}
q_\infty(18) &= 46 \\ &= |\{18\}| \\ &\;+ |\{17+1\}| \\ &\;+ |\{16+2\}| \\ &\;+ |\{15+3,15+2+1\}| \\ &\;+ |\{14+4,14+3+1\}| \\ &\;+ |\{13+5,13+4+1,13+3+2\}| \\ &\;+ |\{12+6,12+5+1,12+4+2,12+3+2+1\}| \\ &\;+ |\{11+7,11+6+1,11+5+2,11+4+3,11+4+2+1\}| \\ &\; \vdots \\ &\;+ |\{7+6+5,7+6+4+1,7+6+3+2,7+5+4+2,7+5+3+2+1\}| \\ &\;+ |\{6+5+4+3,6+5+4+2+1\}|
\end{align}

である。そのうち、要素の上限が 7 であるものを考えてみる。

\begin{align}
q_7(18) &= 7 \\ &= |\{7+6+5,7+6+4+1,7+6+3+2,7+5+4+2,7+5+3+2+1\}| \\ &\;+ |\{6+5+4+3,6+5+4+2+1\}|
\end{align}

当然、18 の "strict partition" の一部として、成分の上限が 7 である 18 の"strict partition" が含まれる。で、その差を考える。

ここで、たとえば  \{7+6,7+5+1,7+4+2,7+3+2+1\} と、それから 7 を除いた  \{6,5+1,4+2,3+2+1\}| が 1 対 1 に対応すると考えて、各分割から最大成分を除去した物を考えて、

\begin{align}
q_\infty(18) &= |\{0\}| \\ &\;+ |\{1\}| \\ &\;+ |\{2\}| \\ &\;+ |\{3,2+1\}| \\ &\;+ |\{4,3+1\}| \\ &\;+ |\{5,4+1,3+2\}| \\ &\;+ |\{6,5+1,4+2,3+2+1\}| \\ &\;+ |\{7,6+1,5+2,4+3,4+2+1\}| \\ &\; + |\{8,7+1,6+2,5+3,5+2+1,4+3+1\}| \\ &\; + |\{8+1,7+2,6+3,6+2+1,5+4,5+3+1,4+3+2\}| \\ &\; + |\{7+3,7+2+1,6+4,6+3+1,5+4+1,5+3+2,4+3+2\}| \\ &\; + q_7(18)  \end{align}

となるから、

\begin{align}
q_\infty(18) - q_7(18) &= q_0(0) \\ &\;+ q_1(1) \\ &\;+ q_2(2) \\ &\;+ q_3(3) \\ &\;+ q_4(4) \\ &\;+ q_5(5) \\ &\;+ q_6(6) \\ &\;+ q_7(7) \\ &\;+ q_8(8) \\ &\;+ q_8(9) \\ &\;+ q_7(10)
\end{align}

となる。前回、

\displaystyle
q_r(r)=q_{r+1}(r)=q_{r+2}(r)= \cdots = q_\infty(r)

という関係を示したので、

\begin{align}
q_\infty(18) - q_7(18) &= q_{17}(0) \\ &\;+ q_{16}(1) \\ &\;+ q_{15}(2) \\ &\;+ q_{14}(3) \\ &\;+ q_{13}(4) \\ &\;+ q_{12}(5) \\ &\;+ q_{11}(6) \\ &\;+ q_{10}(7) \\ &\; + q_9(8) \\ &\; + q_8(9) \\ &\; + q_7(10) \\ &= \sum_{m=7}^{17}q_k(17-m)
\end{align}

とできる。これを一般化すれば、

\begin{align}
q_\infty(r) - q_n(r) &= \sum_{m=n}^{r-1}q_m(r-(m+1)) \\ &= \sum_{m={n+1}}^r q_{m -1}(r-m)
\end{align}

とできそうである。ところで、

\begin{cases}
q_0(0)=1 \\ q_n(r)=0 & \left(r < 0, r > \frac{n(n+1)}{2}\right) \\ q_n(r) = q_{n-1}(r)+q_{n-1}(r-n)
\end{cases}

という漸化式を思い出すと、右辺は

\begin{align}
& \sum_{m={n+1}}^r q_{m -1}(r-m) \\ =& \sum_{m={n+1}}^r \left\{ q_m(r) - q_{m -1}(r) \right\} \\ =& -\sum_{m={n+1}}^r \left\{ q_{m -1}(r) - q_m(r) \right\} \\ =& -[ \{q_n(r) - q_{n+1}(r)\} + \{q_{n+1}(r) - q_{n+2}(r)\} + \cdots \\ &\; + \{q_{r -2}(r) - q_{r -1}(r)\} + \{q_{r -1}(r) - q_r(r)\} ] \\ =& -\{ (q_n(r) - q_r(r) \} \\ =&\; q_r(r) - q_n(r)
\end{align}

と変形できて、 q_r(r) = q_\infty(r) であるから、左辺と等しいことがわかる。

この総和部分はその変数が動く範囲からわかるように  n+1 \leq r のときのみ効いてくるわけであって、逆に言えば  n \geq r のときは  0 である。前回、 n \geq r のとき  q_n(r) = q_\infty(r) となることを示したので当然の結果だ。

続かない気がする。