スタッフBLOG

先日の数学の解答(場合の数)2013年11月01日

(1) 1~n の中から隣り合わないk個の数の組合せは、

選んだk個を小さい順に (A1,A2,A3,・・・・,Ak) と全て名前を付けたものが、

(A1,A2 -1,A3 -2,・・・・,Ak -(k-1)) と1対1に対応すので、

すなわち、異なる n-(k-1) 個から k個を選ぶ方法に等しく n-k+1Ck 通り・・・(答え)

(2) nC0 + n-1C1 + n-2C2 + ・・・・+ n-[n/2]C[n/2] ・・・① を簡単な式で表すには、

まず(1)の結果から n-kCk = n-1-(k-1)Ck が 1~n-1 の中から隣り合わないk個の数の組合せだから、

(①式)=(1~n-1 の中から隣り合わないk個の数の組合せ総数)である。

ここで (1~n の中から隣り合わない数の組合せ総数)=Sn+2  とおくと、

フィボナッチ数列 Sn + Sn+1 = Sn+2 の関係が成り立つ。

(ただし、S1=1、S2=2 である)

(※1) Sn+1 は「1」の数がどのAにも選ばれないとき、残り2~nのn-1個から隣り合わない数の組合せ総数に等しい。

(※2)Sn は「1」がA1、「2」がどのAにも選ばれないとき、残り3~nのn-2個から隣り合わない数の組合せ総数に等しい。

フィボナッチ数列を解いて、α=(1-√5)/2、β=(1+√5)/2 とおくと、Sn={β(n乗)-α(n乗)}/√5 だから、

求めるものは、(①式)= Sn+1 = {β(n+1乗)-α(n+1乗)}/√5 ・・・(答え)