数列の帰納的定義
　漸化式には一般項を求めて利用するものばかりでなく，定積分における次の公式のように，ｎが小さな整数のときの値を元に，帰納的に積み上げていく利用法もあります.
　ここでは，積の法則・和の法則を組み合わせて，帰納的な考え方で，場合の数を計算する方法を考えてみます.		 とおくとき
とおくとき

《解説》
■　階段の上り方
 

問題：「右図のように４段の階段がある.この階段を1段ずつ登っても，２段ずつ上っても，１段と２段をまぜて登ってもよいとすると，この階段を上る方法は何通りあるか.
　また，６段なら何通りあるか.」

＜帰納的な考え方＞
　階段の数が増えてくると，「もれなく，重複なく」数えるのが大変になります.そこでｎ段のときの登り方の総数をａｎとおき，漸化式を作って解きます.
　階段がｎ段のときの上り方の総数をａｎとおくと，ａ４及びａ６を求めることになります.


　４段目に行く前には3段目か2段目を必ず踏みます.（一度に1段または2段しか登らないから）
　3段目までの登り方の総数が分かれば（ａ3），３段目を踏んでから４段目を踏む場合の数がわかります.＝ａ3通り
　次に，2段目までの登り方の総数が分かれば，２段目を踏んで４段目を踏む場合の数がわかります.この場合，右の×で示した登り方は，ａ３ですでに数えているので，2段目を踏む方法のうち3段目を踏まない方法を考えると，ａ２通りです.
　以上により，ａ４＝ａ３＋ａ２

一般に，ａｎ＝ａｎ−１＋ａｎ−２が成り立ちます.
ａ１＝１，ａ２＝２だから順次求めると
ａ３＝３，ａ４＝５，ａ５＝８，ａ６＝１３・・・（答）
いわゆる「フィボナッチ数列」となります.
《問題1》

　上記と同様の条件で，階段の数が段のとき，登り方の総数は通り
（各自上の空欄を埋めること.　段数は35段以下とします.）
《問題1-2》

　ｎ段（ｎ≧5）からなる階段がある.この階段を登るのに，1度に1段，2段，3段を登る3種類の登り方が可能であるものとする.このとき，第ｋ段に登る登り方の総数をＡ(ｋ)で表す.このとき，
(1)　Ａ(1)，Ａ(2)，Ａ(3)，Ａ(4)，Ａ(5)　を求めよ.
(2)　Ａ(n-3)，Ａ(n-2)，Ａ(n-1)，Ａ(n)　の間に成り立つ関係式を求めよ.
(3)　Ａ(10)　を求めよ.

(東北学院大)
　
(1)
　Ａ(1)＝，Ａ(2)＝，Ａ(3)＝，Ａ(4)＝，Ａ(5)＝
 
 
 

(2)
A(n)=A(n-3)+A(n-2)+A(n-1)となります.
 　
(3)

A(10)=
 


 


《解説》
■　ハノイの塔
 
　「ハノイの塔の問題」とは次のような問題をいいます.（この問題は，他の多くのホームページでも取り扱われていますので，あわせてご覧になるとよいでしょう.中には，実際に動かして，回数を数えられるものもあります.）

問題：「Ａ，Ｂ，Ｃは床に固定された棒で，Ａの棒にｎ枚の円盤が突きさしてある.この円盤を1枚ずつ移動して，他の1つの棒に全部移動するに要する最小の回数を求めよ.ただし，ひとつの棒にささった円盤については，どの時点でも上のものが下のものよりも小さくなければならないものとする.」
　円盤の枚数がｎ枚のとき，移動に要する（最小の）回数をａｎで表すものとします.

＜小実験でイメージ作り＞
■　ｎ＝１のとき，明らかにａ１＝１
 

■　ｎ＝２のとき，
　1回目：小さい円盤をＡからＢに移動
　2回目：大きい円盤をＡからＣに移動
　3回目：小さい円盤をＢからＣに移動
（BとCを全部入れ替えても同じ）
ゆえに，ａ２＝３
・
・
・
・
・
・
・


＜帰納的な考え方＞
■　ｎ個のとき
　右図のように，一番大きな円盤を動かさずに上のｎ−１個の円盤をＢの棒に移動させる操作はａｎ-1回
　次に一番大きな円盤をCの棒に移動させる操作は１回
　さらに，Bにあるｎ−１個の円盤をCの棒に移動させる操作はａｎ-1回
　ゆえに，ａｎ＝２ａｎ−１＋１

そこで，ａ１＝１，ａｎ＝２ａｎ−１＋１を用いて順次ａｎを求めることができます.（一般項ａｎも簡単に求められます.）
 
ｎ
1
2
3
4
・・・
 
ａｎ
1
3
7
15
・・・
 



 
《問題2》

　ハノイの塔の問題で，円盤の数が個のとき，他の1つの棒にすべての円盤を移動するための最小移動回数は通り
（各自上の空欄を埋めること.　円盤数は20枚以下とします.）

《解説》
■　さいころの目の和
 
例
　大小相異なるサイコロを５個ふったとき，目の和が20となる場合は何通りあるか.

（第一印象）

  • 大小２個のサイコロをふったときの目の和については，次の図が使えますが，３個以上の場合に同様の表を作るのは困難です.
    • 和
    1
    2
    3
    4
    5
    6
    1
    2
    3
    4
    5
    6
    7
    2
    3
    4
    5
    6
    7
    8
    3
    4
    5
    6
    7
    8
    9
    4
    5
    6
    7
    8
    9
    10
    5
    6
    7
    8
    9
    10
    11
    6
    7
    8
    9
    10
    11
    12
  • 　ｘ＋ｙ＋ｚ＋ｕ＋ｖ＝20　（ｘ，ｙ，ｚ，ｕ，ｖ≧1）の整数解の個数なら，重複組み合わせで求めることができます.

    • はじめに1つずつ配っておいて（ｘ，ｙ，ｚ，ｕ，ｖ≧1のため）残り15を５人に重複を許して配る方法は5Ｈ15＝19Ｃ15通りです.ただし，この答の中には，ｘ＝ｙ＝ｚ＝ｕ＝1，ｖ＝１６のように，どれかが7以上のものも含まれるので，この方法だけでｘ，ｙ，ｚ，ｕ，ｖ≦6となる条件を生かすのは困難です.
（考え方）
■　サイコロ２個の和は，上の結果により次の表にまとめることができます.
     
    ｘ，ｙ2個の和
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    場合の数
    1
    2
    3
    4
    5
    6
    5
    4
    3
    2
    1
■　ｘ，ｙ，ｚ３個のサイコロの目の和は，このｘ，ｙ２個の和と３個目のｚとの和と考えることができます.
ｘ，ｙ，ｚの和
ｚの値
1
2
3
4
5
6
ｘ，ｙの和
場合の数
1
1
1
1
1
1
2
1
3
4
5
6
7
8
3
2
4
5
6
7
8
9
4
3
5
6
7
8
9
10
5
4
6
7
8
9
10
11
6
5
7
8
9
10
11
12
7
6
8
9
10
11
12
13
8
5
9
10
11
12
13
14
9
4
10
11
12
13
14
15
10
3
11
12
13
14
15
16
11
2
12
13
14
15
16
17
12
1
13
14
15
16
17
18
　たとえば，３個の目の和が５になる場合の数は，
ｘ＋ｙ＝2　（1通り）、その各々についてｚ＝3（1通り）・・・1×1＝1通り
ｘ＋ｙ＝3　（2通り）、その各々についてｚ＝2（1通り）・・・２×１＝2通り
ｘ＋ｙ＝4　（3通り）、その各々についてｚ＝１（1通り）・・・３×１＝3通り
以上により，１＋２＋３＝6通りとなります.
　ｚの値は、1通りずつしかないので，３個の和の場合の数は、２個の和の場合の数を縦に加えただけになります.
　以上により，サイコロ３個の目の和は，次の表にまとめることができます.
x,y,z３個の和
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
場合の数
1
3
6
10
15
21
25
27
27
25
21
15
10
6
3
1
■　同様にして，ｘ，ｙ，ｚ，ｕ４個のサイコロの目の和は，３個の場合の数を加えて
x,y,z,u４個の和
4
5
6
7
8
9
10
11
12
13
14
 15
16
17
18
19
20
 21 22 23 24
場合の数
1
4
10
20
35
56
80
104
125
140
146
 140
125
104
80
56
35
 20 10 4 1
■　同様にして，ｘ，ｙ，ｚ，ｕ，ｖ５個のサイコロの目の和は，４個の場合の数を加えて
和
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
場合の数
1
5
15
35
70
126
205
305
420
540
651
735
780
780
735
651
540
420
305
205
126
70
35
15
5
1
結局，５個のサイコロをふって目の和が20となるのは651通りあります.・・・（答）
 
《コンピュータの総当り計算による検算》

５個のサイコロの目の和を入力

↓(5〜30）　　　　　
　　　
場合の数
 

《問題3》

　相異なる６個のサイコロをふるとき，目の和がとなる場合の数は通り
（各自上の空欄を埋めること.　目の和は6以上36以下です.）

  ←メニューに戻る