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

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

ある自然数 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-1Ｃ0 + n-1Ｃ1 + n-1Ｃ2 + … + n-1Ｃn-1

今回は、この式の展開と、二項定理についてです。



さて、以下の式ですが、これはシグマ（Σ）を使っても表現できそうです。

Qn = n-1Ｃ0 + n-1Ｃ1 + n-1Ｃ2 + … + n-1Ｃn-1

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

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

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

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

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

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

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

つまり、

Qn = Σn-1_k=0 n-1Ck　= ( 1 + 1 )^n-1　= 2^n-1

となります。

確かめてみましょう。

前回記事で、Q1からQ5までは確認しています。

Q1 = 1　= 2⁰
Q2 = 2　= 2¹
Q3 = 4　= 2²
Q4 = 8　= 2³
Q5 = 16　= 2⁴

Q0 は、合わないですね…。

Q0 = 1　≠ 2^-1

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

したがって、求めたい分断数Qnの一般項は、

Qn = 2^n-1 （ただし、n は n>0 の自然数）

です。


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

たとえば、(x+y)² を展開すると、

(x+y)² = x² + 2xy + y²

となり、x²、xy、y² の係数はそれぞれ 1、2、1 となります。

(x+y)³ ならば、

(x+y)³ = x³ + 3x²y + 3xy² + y³

それぞれの項の係数は、1、3、3、1 です。

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

前回記事で5の分断数を求めるときに、以下のように記述しました。

4つのうち0本の分断線を選択：4Ｃ0=1
4つのうち1本の分断線を選択：4Ｃ1=4
4つのうち2本の分断線を選択：4Ｃ2=6
4つのうち3本の分断線を選択：4Ｃ3=4
4つのうち4本の分断線を選択：4Ｃ4=1

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

(x+y)⁴ = x⁴ + 4x³y + 6x²y² + 4xy³ + y⁴

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

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