読者です 読者をやめる 読者になる 読者になる

猫尾製作所

あまりアテにしないでね

連続する整数の積の多項式の展開

数学

前回の記事にて  (n+1)(n+2) \cdots (n+m-1)(n+m) という連続するいくつかの整数の積のかたちの多項式を扱ったのですが、今回はその展開について考えます。

この式を展開すると、 n に関する  m 次式になりますが、それぞれの  n^k の係数はどのようになっているのでしょう。

まず、最初のいくつかの  m ついて考えてみます。

 (n+1) = n+1

 (n+1)(n+2)
 = n^2+2n+n+2
 = n^2+3n+2

 (n+1)(n+2)(n+3)
 = (n^2+3n+2)(n+3)
 = n^3+3n^2+3n^2+9n+2n+6
 = n^3+6n^2+11n+6

 (n+1)(n+2)(n+3)(n+4)
 = (n^3+6n^2+11n+6)(n+4)
 = n^4+4n^3+6n^3+24n^2+11n^2+44n+6n+24
 = n^4+10n^3+35n^2+50n+24

というふうになります。

ここで  (n+1)(n+2)(n+3) \cdots (n+m) m多項式
 a_{m,m}n^m + a_{m,m-1}n^{m-1} + a_{m,m-2}n^{m-2} + \cdots + \\<br />
 a_{m,2}n^2 + a_{m,1}n + a_{m,0} とおいてみます。(☆)

すると、
 (n+1)(n+2)(n+3) \cdots (n+m)\{n+(m+1)\}
 = (a_{m,m}n^m + a_{m,m-1}n^{m-1} + a_{m,m-2}n^{m-2}+ \cdots + \\<br />
 a_{m,2}n^2 + a_{m,1}n + a_{m,0}) \{n+(m+1)\}

この部分を展開した

 a_{m,m} n^{m+1}
 + \{(m+1)a_{m,m}+a_{m,m-1}\} n^m
 + \{(m+1)a_{m,m-1}+a_{m,m-2}\} n^{m-1}
 …
 + \{(m+1)a_{m,1}+a_{m,0}\} n
 + (m+1) a_{m,0}

と、 (n+1)(n+2)(n+3) \cdots (n+m)\{n+(m+1)\} について新しく (☆) で作った  m+1 次式

 a_{m+1,m+1} n^{m+1}
 + a_{m+1,m} n^m
 + a_{m+1,m-1} n^{m-1}

 + a_{m+1,1} n
 + a_{m+1,0}

の係数を比較すると次のような漸化式が作れます。

  •  a_{m+1, 0} = (m+1) a_{m, 0)
  •  a_{m+1, k} = (m+1) a_{m, k} + a_{m, k-1}  ( 1 \leq k \leq m )
  •  a_{m+1, m+1} = a_{m, m}

なお、漸化式の底は『なにも掛け合わせない』ときなので

  •  a_{0, 0} = 1

です。

また、先ほどの漸化式を  m について  m+1 から書き直すと、

  •  a_{m, 0} = m a_{m-1, 0}
  •  a_{m, k} = m a_{m-1, k} + a_{m-1, k-1}  ( 1 \leq k \leq m-1 )
  •  a_{m, m} = a_{m-1, m-1}

となります。

次はこの展開をプログラミング言語 Ruby にて計算機上で実現します。