2011/06/09

勝手に作った分断数と二項定理の関係

現在考えている問題は、以下のようなものです。

ある自然数 n を自然数の和で表わしていきたい。例えば、「5」ならば、
5=5
5=4+1
5=3+2
5=2+3
5=1+4
5=3+1+1
5=2+2+1
5=2+1+2
5=1+3+1
5=1+2+2
5=1+1+3
5=2+1+1+1
5=1+2+1+1
5=1+1+2+1
5=1+1+1+2
5=1+1+1+1+1
の16通りある。同じ自然数を何回使ってもいいし、順番が違っていてもいい。
このときの16を5の分断数といい、Q5=16と書く。

このときの n の分断数 Qnを求めよ。

「分断数」というのは、「分割数」に対して、私が勝手に名付けた数です。

そして、前回記事にて、Qnについて以下の式を立てました。
Qn = n-10 + n-11 + n-12 + … + n-1n-1
今回は、この式の展開と、二項定理についてです。



さて、以下の式ですが、これはシグマ(Σ)を使っても表現できそうです。
Qn = n-10 + n-11 + n-12 + … + n-1n-1

シグマ(Σ)は総和(簡単にいえば合計)を表わす記号です。普通は、Σの上下に添え字をつけて表わします。しかし、このブログ上では、(私が添え字のつけ方を知らないので…)以下のように表現したいと思います。

Qn = Σn-1k=0 n-1Ck

この意味は、n-1Ck の k について、k=1 から k=n-1 まで合計する、という記号です。

さて、ここで登場するのが、有名な「二項定理」です。とはいうものの、『数学ガール』を読むまで頭の引出の奥の方でほこりをかぶっていましたが…。

二項定理とは以下のような公式です。(Wikipedia「二項定理」より)

この公式の n の部分を n-1 に、x、y を 1 に置き換えると、以下のようになります。
( 1 + 1 )n-1 = Σn-1k=0 n-1Ck 1k・1n-1-k

右辺が、先ほどΣを使って表現した分断数Qnの一般項と同じ形になりました。1は何乗しても1です。

つまり、
Qn = Σn-1k=0 n-1Ck = ( 1 + 1 )n-1 = 2n-1
となります。

確かめてみましょう。

前回記事で、Q1からQ5までは確認しています。
Q1 = 1 = 20
Q2 = 2 = 21
Q3 = 4 = 22
Q4 = 8 = 23
Q5 = 16 = 24

Q0 は、合わないですね…。
Q0 = 1 ≠ 2-1

とりあえず、n>0 としましょう(^-^;)

したがって、求めたい分断数Qnの一般項は、
Qn = 2n-1 (ただし、n は n>0 の自然数)
です。


さてここで出てきた二項定理ですが、もともとは、式を二項展開したときの係数を求めるためのものです。

たとえば、(x+y)2 を展開すると、
(x+y)2 = x2 + 2xy + y2
となり、x2、xy、y2 の係数はそれぞれ 1、2、1 となります。

(x+y)3 ならば、
(x+y)3 = x3 + 3x2y + 3xy2 + y3
それぞれの項の係数は、1、3、3、1 です。

今回の分断数は、この係数の合計を求めたこととなります(正確には、合計を2で割ったものです)。

前回記事で5の分断数を求めるときに、以下のように記述しました。
4つのうち0本の分断線を選択:40=1
4つのうち1本の分断線を選択:41=4
4つのうち2本の分断線を選択:42=6
4つのうち3本の分断線を選択:43=4
4つのうち4本の分断線を選択:44=1

これらの 1、4、6、4、1 は、(x+y)を4乗したときに出てくる係数と一致しています。
(x+y)4 = x4 + 4x3y + 6x2y2 + 4xy3 + y4

また、今回 Qn = 2n-1 という一般項を出しましたが、これも前回記事での分断線のON、OFFに相当すると考えると合点がいきます。分断線1本につき、ONとOFFの2種類あり、5の分断線は4本あるので、ONとOFFの組み合わせは25-1通りあるとも考えられます。

二項定理での係数と2の累乗の関係、考えると面白いですね。

ブログ アーカイブ