自然数の分割、あるいは階段の昇降

　　今も時たまやることではあるが、幼い頃から階段を一段飛ばしで上るのが楽しかった。今考えるとちょっと滑稽だが、階段を一段飛ばすことで漠然と決められた生活のルールみたいなものを破っている気分になれたからである。

　そんな話は、結局は数学の話に帰着される。数学において次のような有名問題がある。

階段昇降問題

階段を普通に上る、そして一段飛ばしで上るという二つの選択肢が与えられている。このとき、 $n$ 段の階段を上るときの場合の数を求めなさい

　なかなか面白そうな問題である。例えば $4$ 段の階段を上ることを考えてみよう。

　下手クソな絵で申し訳ないが、下の人が頑張って階段を上っていく様子を想像してほしい。

まず、素直に $1$ 段ずつ着実に上っていく場合があるだろう。

　　そのほかに $1$ 段飛ばしを入れてみたり、

　　全部 $1$ 段飛ばしを使って上る場合もある。

　とまあ、色々な上り方を合わせて最終的な場合の数は $5$ 通り存在する。ただ、これはあくまで $n$ に4を入れてみた場合の具体例にすぎない。これをどうやって一般的に求めるのかが難しいところである。ここで、漸化式を用いて問題を分割する。

数列の定義

$n$ 段の階段を与えられた方法で上るときの場合の数を $a_n$ とおく

　こうして数列を置くことで我々は漸化式という超強力な武器を使うことができるようになるのだった。ここで、 $a_n$ を再帰的に数えよう。

$n+2$ 段の階段を与えられた条件で上ることを考える。すると、以下の二つのパターンがあることに気づく。
(i)一段上って踊り場に着く
(ii)一段飛ばしで踊り場に着く
(i)のとき、踊り場に着く前には $n+1$ 段まで上っていたことになるが、この場合の数は $a_{n+1}$ 通りある。
(ii)のとき、踊り場に着く前には $n$ 段まで上っていたことになるが、この場合の数は $a_n$ 通りある。
これら(i)と(ii)の場合は排反であるので足せば $n+2$ 段の場合の数が求められる。よって求めたかった場合の数は $a_{n+1}+a_n$ である。定義より数えていた場合の数は $a_{n+2}$ に一致するので
$a_{n+2}=a_{n+1}+a_n$ が成り立つことがわかる $◽︎$

　漸化式は初期値とセットで初めて数列を定義することができるので、初期値を求める。

　 $a_1$ は当然 $1$ である。これに異論はないだろう。 $a_2$ は地道に一段一段上るのと一気に一段スキップしてしまう上り方の $2$ 通りがあるので $2$ である。さあ、定義された $a_n$ を並べてみよう。

　 $\{1, 2, 3, 5, 8, 13, 21, 34,\cdots\}$

　おもむろにフィボナッチ数列を下に置いておく。

　 $\{1, 1, 2, 3, 5, 8, 13, 21,\cdots\}$

　ん?

　異国の地で友人に会ったときのような安心感すら覚える。なんやお前、ここにもおったんか

　このことは気にせずに一旦一般化した数列を考えてみよう。異国にまさか友人がいるはずはない。きっと幻覚である。

一般化した問題を考える上で断っておきたいことがある。それは一段飛ばしという名称、やめませんか?ということである。一段飛ばしすると階段は二段進んだことになる。これはちょっとわかりづらいだろう。ということでちょっと大人ぶってこの操作を一般的に定義してみよう。

階段を上るときの技名

$k$ 段一気に階段を上ることを $k$ 段上りと定義する

　定義から、一段飛ばしは $2$ 段上りであり、通常の上り方は $1$ 段上りである。名称と実際に上る段数のずれを修正しただけである。

　ここまで考えたことを使うと、一般化した問題を簡潔に言い表すことができる。

一般化した階段昇降問題

$1\leq k$ とする。
$1,2,3\cdots k$ 段上りを認めて $n$ 段の階段を上る場合の数を $a_{n,k}$ と書くとき、 $a_{n,k}$ の満たす漸化式と十分な初期値を求めなさい

　なかなか面白そうな問題ではないか。初期値を求めるのは明らかに面倒なので、まずは漸化式から求めてみよう。

漸化式

$\displaystyle a_{{n+k},k}=\sum_{i=0}^{k-1}a_{{n+i},k}$

$k=2$ の場合でやったように、最後に何段上りをしたかで場合わけをすれば良い。 $1\leq i\leq k$ として最後に $i$ 段上りをしたと仮定しよう。このとき、踊り場に着く前には $n+k-i$ 段目にいたことがわかるので、そこにつく経路の数は定義によって $a_{{n+k-i},k}$ 通りである。この場合わけを $i=1\to k$ の範囲で足しあげてしまえば良く、 $\displaystyle \sum_{i=1}^{k}a_{{n+k-i},k}=\sum_{i=0}^{k-1}a_{{n+i},k}$ という和が導かれる。これは定義により $a_{{n+k},k}$ に一致するので、 $\displaystyle a_{{n+k},k}=\sum_{i=0}^{k-1}a_{{n+i},k}$ が示された $◽︎$

　なかなか証明していて楽しい定理である。それと同時にやはり数学は具体例を考えることが重要だと身に染みてわかった。

　そして漸化式は求められたので、数列を定義するのに必要な最後のピース、数列の初期値を求める。

初期値を求める前に $a_{n,k}$ の組み合わせ論的な性質について考えてみよう。すると次のことに気づける。

禁止行動の補題

$n\leq k$ のとき、 $a_{n,k}=a_{n,n}$

$Proof$
正直に言ってあまりいい言い方が思いつかないが、たとえば $4$ 段の階段を上るとき $5$ 段飛ばしをすることはできないだろう。それと同じで階段の段数 $n$ より大きい $k$ は $k$ 段上りができないので場合の数に含められない $◽$ ︎

　初期値を求める。初期値はどこまで定めるべきか考える。 $k$ が固定されていることに注目すると、それは $a_{1,k},a_{2,k},a_{3,k}\cdots a_{k-1,k},a_{k,k}$ であることがわかる。

禁止行動の補題を適用すると初期値を求める問題から $a_{1,1},a_{2,2},a_{3,3}\cdots a_{k-1,k-1},a_{k,k}$ を求める問題に早変わりする。

　ここまできてもつかみどころのない問題である。とりあえず新たに数列 $b_n$ を定義する。

$b_n$ の定義

$b_n=a_{n,n}$

　わからないときはとりあえず具体的に落とし込むのが重要だ。 $b_1,b_2,b_3,b_4$ くらいまで値を求めてみよう。

すると $b_1=1,b_2=2,b_3=4,b_4=8$ がわかる。実際に場合の数を数えればわかることである。

ここで、あれっと思った人もいるだろう。次のことが予想できる。

$b_n$ の値についての予想

$b_n=2^{n-1}$ が成り立つ

　どうにかしてこの予想を証明したい。ということで再び漸化式を立てる。 $b_{n+1}$ をうまいこと分解して $(1\leq k\leq n)\space b_k$ を用いて書きたい。

すると次のような変形を思いつく。

項番号下げの補題

$b_{n+1}=1+a_{{n+1},n}$ が成立する

$Proof$
$b_{n+1}=a_{{n+1},{n+1}}$ であり、 $n+1$ 段上りを使って上る場合は $1$ 通りしかないことがわかる。そして残りの全ての場合は $n+1$ 段上りを使わずに達成されるので $a_{n+1},n$ 通りである。よって $a_{{n+1}{n+1}}=1+a_{{n+1},n}$ $◽︎$

　そして思いつきにくい利用だが $a_{n,k}$ の漸化式を視点を変えて利用する。

$b_n$ の漸化式

$\displaystyle b_{n+1}=1+\sum_{k=1}^n b_k$

$Proof$
$\displaystyle a_{{n+k},k}=\sum_{i=0}^{k-1}a_{{n+i},k}$ が成り立っている。この漸化式を視点を変えて使ってみよう。漸化式に $k\mapsto n,n\mapsto 1$ というふうに代入すると、 $\displaystyle a_{{1+n},n}=\sum_{i=0}^{n-1}a_{{1+i},n}$ が得られる。 $\sum$ の中の $1+i$ は常に $n$ 以下であるので、禁止行動の補題を用いると、 $\displaystyle \sum_{i=0}^{n-1}a_{{1+i},n}=\sum_{i=0}^{n-1}a_{{1+i},{1+i}}$ と変形できる。 $a_{{1+i},{1+i}}\stackrel{\mathrm{定義から}}{=}b_{1+i}$ であるので、 $\displaystyle b_{n+1}=1+\sum_{i=0}^{n-1}a_{{1+i},{1+i}}=1+\sum_{i=1}^n a_{{i},{i}}=1+\sum_{i=1}^n b_i$ $◽︎$

　なかなか見ない形の漸化式である。初期値 $b_1$ は $1$ であるとわかっているので、これで $b_n$ が定義された。こういう解くのが難しそうな漸化式を見た時にやることは決まっている。当然数学的帰納法である。

$b_n$ の値

$b_n$ の値についての予想は正しく、 $b_n=2^{n-1}$ が成り立つ

$Proof$
累積帰納法を用いて示す。 $b_1=1=2^{1-1}$ が成り立つので、 $n=1$ のときは命題が成立する。 $k\leq n$ を満たす全ての自然数 $k$ について命題が正しいとして、 $n+1$ の場合を示す。 $\displaystyle b_{n+1}=1+\sum_{k=1}^n b_k\stackrel{\mathrm{帰納法の仮定より}}{=}1+\sum_{k=1}^n 2^{k-1}$
これを等比級数の和の公式を使って変形すると、 $1+\sum_{k=1}^n 2^{k-1}=1+\dfrac{2^n -1}{2-1}=2^n=2^{n+1-1}$ が成り立ち、帰納法によって全ての自然数で命題は成り立つ $◽︎$

　この定理により $a_{n,k}$ を定義する上で十分な初期値が求められて、考えていた問題は解決した。

具体例

$k=3$ のとき、 $a_{{n+3},3}=a_{{n+2},3}+a_{{n+1},3}+a_{n,3},a_{1,3}=1,a_{2,3}=2,a_{3,3}=4$ と定義される
これは $\{1,2,4,7,13,24,44,81\cdots\}$ という数列である

　ここでトリボナッチ数列をひとつまみ $\cdots\cdots$

トリボナッチ数列

トリボナッチ数列 $T_n$ とはフィボナッチ数列を四項間漸化式に拡張したもので、 $T_{{n+3},3}=T_{{n+2},3}+T_{{n+1},3}+T_{n,3},T_1=0,T_2=0,T_3=1$ を満たす数列である

　この数列の値を求めてみよう。すると $\{0,0,1,1,2,4,7,13,24,44,81\cdots\}$ となる $\cdots\cdots$

ん?(deja vu)

　 $\{0,0,1,1,2,4,7,13,24,44,81\cdots\}$

　 $\{1,2,4,7,13,24,44,81\cdots\}$

$a_{n,3}=T_{n+3}$ やんけ！

にわかに $k-nacci$ 数列を定義したい気分になってきた。

$k-nacci$ 数列の定義

$k-nacci$ 数列 $F_n^k$ を $\displaystyle F_{n+k}^k=\sum_{i=0}^{k-1}F_{n+i}^k,F_1^k=F_2^k=F_3^k=\cdots=F_{k-1}^k=0,F_k^k=1$
と定義する

　 $k=2$ のときがフィボナッチ、 $k=3$ のときがトリボナッチ数列である。

　ここまでの話の流れからして以下の定理が成り立ちそうである。

階段の昇降と $k-nacci$ 数列の関係

$a_{n,k}=F_{n+k}^k$

$Proof$
まず初めに初期値を求めてみよう。 $1\leq t\leq k$ としたとき、 $F_{t+k}^k$ の値を求める。 $k-nacci$ 数列の定義によって、漸化式 $\displaystyle F_{n+k}^k=\sum_{i=0}^{k-1}F_{n+i}^k$ が成り立ち、最右辺は $\displaystyle \sum_{i=0}^{k-1}F_{t+i}^k=\sum_{i=0}^{k-t}F_{t+i}^k+\sum_{i=k-t+1}^{k-1}F_{t+i}^k$ と分解することができる。ただし $t=1$ のとき、 $\displaystyle \sum_{i=k-t+1}^{k-1}F_{t+i}^k=0$ とみなす。 $1\leq t+i\leq k$ により $\displaystyle \sum_{i=0}^{k-t}F_{t+i}^k=1$ がわかる。 $\displaystyle \sum_{i=0}^{k-1}F_{t+i}^k=1+\sum_{i=1}^{t-1}F_{i+k}^k$ であることから、 $\displaystyle F_{t+k}^k=1+\sum_{i=1}^{t-1}F_{i+k}^k$

この漸化式は $b_n$ の時に出てきたものと同一である。

$g_n$ の定義

$\displaystyle g_1=F_{1+k}^k=1,g_{n+1}=1+\sum_{i=1}^{n}g_i$

$g_t$ はその定義により $F_{t+k}^k$ に一致する。そして $g_i=2^{i-1}$ がわかる。であるので $F_{t+k}^k=2^{t-1}=a_{n,k}$ が成り立つ。

　さて、数学的帰納法を用いて命題を証明しよう。 $n=t$ のケースでは正しいことが上で確認できている。 $n=s,s+1,s+2,\cdots,s+k-1$ のとき正しいとして、 $n=s+k$ のときを示そう。 $\displaystyle a_{s+k,k}=\sum_{i=0}^{k-1}a_{{s+i},k}=\sum_{i=0}^{k-1}F_{s+i}^k=F_{s+k}^k$ であるので題意は示された $◽︎$

　結局、階段の昇降の場合の数には $k-nacci$ 数列が関わっていることがわかった。しかも上の添字だけ下の添え字をずらす、という非常に簡単な方法で、である。ありがとうフィボナッチ数列！

　ちなみにこれに入試数学の一般化というタグをつけたのは京都大学で似たような問題が出されていたからである。確か連続して $2$ 段上りをしてはいけないというルールのもとで、 $1,2$ 段上りを使って階段を上るときの場合の数を求める問題だったような気がする。

　 $a_{n,k}$ は $n$ を $1$ から $k$ までの自然数に順序を区別して分割するときの場合の数である。（唐突）ここまで階段の昇降にしか触れていなかったので、ちょっと実験してみよう。

$4$ の分割

$4$ を $3$ 以下の自然数に分割するときの場合の数を求める。 $4\to 3+1=1+3=2+2=2+1+1=1+2+1=1+1+2$ $=1+1+1+1$ で $7$ 通り存在する。
これは $a_{4,3}=a_{3,3}+a_{3,2}+a_{3,1}=4+2+1=7$ に一致する

　階段を上ることは自然数を分割することだったのだ。今度から童心に帰りつつ、理学的に「今、自然数分割してるな〜」と思いながら階段を上ってみるのも良いかもしれない。

数ならぬ

理学系のこと、特に数学について書きます。雑学的な知識もまとめていく所存。

自然数の分割、あるいは階段の昇降