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

《解説》
■ 階段の上り方
 

問題:「右図のように4段の階段がある.この階段を1段ずつ登っても,2段ずつ上っても,1段と2段をまぜて登ってもよいとすると,この階段を上る方法は何通りあるか.
 また,6段なら何通りあるか.」

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



 4段目に行く前には3段目か2段目を必ず踏みます.(一度に1段または2段しか登らないから)
 3段目までの登り方の総数が分かれば(a3),3段目を踏んでから4段目を踏む場合の数がわかります.=a3通り
 次に,2段目までの登り方の総数が分かれば,2段目を踏んで4段目を踏む場合の数がわかります.この場合,右の×で示した登り方は,aですでに数えているので,2段目を踏む方法のうち3段目を踏まない方法を考えると,a通りです.
 以上により,a=a+a


一般に,a=an−1+an−2が成り立ちます.
=1,a=2だから順次求めると
=3,a,a=8,a13・・・(答)
いわゆる「フィボナッチ数列」となります.
《問題1》

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

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

(東北学院大)
 
(1)
 A(1)=,A(2)=,A(3)=,A(4)=,A(5)=
 
 
 

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

A(10)=
 


 



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

問題:「A,B,Cは床に固定された棒で,Aの棒にn枚の円盤が突きさしてある.この円盤を1枚ずつ移動して,他の1つの棒に全部移動するに要する最小の回数を求めよ.ただし,ひとつの棒にささった円盤については,どの時点でも上のものが下のものよりも小さくなければならないものとする.」

 円盤の枚数がn枚のとき,移動に要する(最小の)回数をaで表すものとします.

<小実験でイメージ作り>
■ n=1のとき,明らかにa
 


■ n=2のとき,
 1回目:小さい円盤をAからBに移動
 2回目:大きい円盤をAからCに移動
 3回目:小さい円盤をBからCに移動
(BとCを全部入れ替えても同じ)
ゆえに,a


































<帰納的な考え方>
■ n個のとき
 右図のように,一番大きな円盤を動かさずに上のn−1個の円盤をBの棒に移動させる操作はan-1
 次に一番大きな円盤をCの棒に移動させる操作は1回
 さらに,Bにあるn−1個の円盤をCの棒に移動させる操作はan-1
 ゆえに,a=2an−1+1


そこで,a=1,a=2an−1+1を用いて順次aを求めることができます.(一般項aも簡単に求められます.)
 
1
2
3
4
・・・
 
1
3
7
15
・・・
 



 
《問題2》

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


《解説》
■ さいころの目の和
 

 大小相異なるサイコロを5個ふったとき,目の和が20となる場合は何通りあるか.

(第一印象)

  • 大小2個のサイコロをふったときの目の和については,次の図が使えますが,3個以上の場合に同様の表を作るのは困難です.
  • 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
  •  x+y+z+u+v=20 (x,y,z,u,v≧1)の整数解の個数なら,重複組み合わせで求めることができます.

  • はじめに1つずつ配っておいて(x,y,z,u,v≧1のため)残り15を5人に重複を許して配る方法は5151915通りです.ただし,この答の中には,x=y=z=u=1,v=16のように,どれかが7以上のものも含まれるので,この方法だけでx,y,z,u,v≦6となる条件を生かすのは困難です.
(考え方)
■ サイコロ2個の和は,上の結果により次の表にまとめることができます.
     
    x,y2個の和
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    場合の数
    1
    2
    3
    4
    5
    6
    5
    4
    3
    2
    1
■ x,y,z3個のサイコロの目の和は,このx,y2個の和と3個目のzとの和と考えることができます.
x,y,zの和
zの値
1
2
3
4
5
6
x,yの和
場合の数
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
 たとえば,3個の目の和が5になる場合の数は,
x+y=2 (1通り)、その各々についてz=3(1通り)・・・1×1=1通り
x+y=3 (2通り)、その各々についてz=2(1通り)・・・2×1=2通り
x+y=4 (3通り)、その各々についてz=1(1通り)・・・3×1=3通り
以上により,1+2+3=6通りとなります.
 zの値は、1通りずつしかないので,3個の和の場合の数は、2個の和の場合の数を縦に加えただけになります.
 以上により,サイコロ3個の目の和は,次の表にまとめることができます.
x,y,z3個の和
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,u4個のサイコロの目の和は,3個の場合の数を加えて
x,y,z,u4個の和
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
■ 同様にして,x,y,z,u,v5個のサイコロの目の和は,4個の場合の数を加えて
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
結局,5個のサイコロをふって目の和が20となるのは651通りあります.・・・(答)
 
《コンピュータの総当り計算による検算》

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

↓(5〜30)     
   
場合の数
 

《問題3》

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

  ←メニューに戻る