ホーム >> 場合の数 >> 数え上げの基本的な考え方

数え上げの基本的な考え方と,辞書式順序,樹形図というふたつの基本的な道具を紹介します.




数え上げの基本的な考え方

ある事柄の起こりうる場合の数をすべて調べ尽くすことを,数え上げといいます.
数え上げで最も重要なことは次のふたつです.
・すべての場合を数えもらさないこと
・同じ場合を重複して数えないこと
適当に数えてしまうと,数え漏れや重複が発生してしまいます.そうならないためには,工夫して数え上げることが大切です.

辞書式順序

起こりうる場合を辞書順に書き出すことで,数え漏れや重複を防ぐことができます.

 $A$ を $3$ つ,$B$ を $2$ つ用いて $5$ 文字の記号列をつくる方法は何通りあるか.

起こりうる場合を辞書順で並べてみましょう.一番最初の文字列は $AAABB$ です.つぎは,$AABAB$ です.その次は $AABBA$ です.以下同様に並べていくと, $$AAABB AABAB AABBA ABAAB ABABA$$ $$ABBAA BAAAB BAABA BABAA BBAAA$$ となります.したがって,求めるべき場合の数は全部で $10$ 通りであることがわかります.実際にやってみるとわかるように,この方法は深く考えずに機械的なルーティーンで書き出すことができます.

 $3$ つのさいころ $A,B,C$ を同時に投げるとき,目の積が $12$ となる場合は何通りあるか.

$A,B,C$ の目がそれぞれ $a,b,c$ である場合を $(a,b,c)$ という風に表すことにします.目の積が $12$ となる目の出方を辞書順で並べていきます.辞書式順序で最初の目の出方は $(1,2,6)$ です.すべて書き出すと以下のようになります.
$$(1,2,6) (1,3,4) (1,4,3) (1,6,2) (2,1,6)$$ $$(2,2,3) (2,3,2) (2,6,1) (3,1,4) (3,2,2)$$ $$(3,4,1) (4,1,3) (4,3,1) (6,1,2) (6,2,1)$$ したがって,求めるべき場合の数は全部で $15$ 通りであることがわかります.

 $0$ 以上の整数 $a,b,c$ が,$a+b+c=4$ を満たす場合の数を求めよ.

先ほどと同様に,$(a,b,c)$ を辞書順でならべてきます.すると,つぎのようになります. $$(0,0,4) (0,1,3) (0,2,2) (0,3,1) (0,4,0)$$ $$(1,0,3) (1,1,2) (1,2,1) (1,3,0) (2,0,2)$$ $$(2,1,1) (2,2,0) (3,0,1) (3,1,0) (4,0,0)$$ したがって,求めるべき場合の数は全部で $15$ 通りであることがわかります.

樹形図

先ほどと同じ $3$ つの問題を今度は樹形図を用いて解いてみましょう.

 $A$ を $3$ つ,$B$ を $2$ つ用いて $5$ 文字の記号列をつくる方法は何通りあるか.

まず,一番左にくる文字としてあり得るものをすべて書きつくします.今回の場合は,$A,B$ の $2$ 通りあります.
樹形図
つぎに,$2$ 番目にくる文字列としてあり得るものを下図のように書きます.つまり,一番左が $A$ という文字の場合は,二番目の文字は $A,B$ の $2$ 通りの可能性があり,一番左が $B$ という文字の場合も同様です.下の図はその様子を表しています.
樹形図
同様にして,$3$ 番目にくる文字列としてあり得るものを下図のように書きます.ここで,一番下の $B-B$ からは一本しか枝が伸びていないことに注意してください.問題の条件より,$B$ はふたつしか並べないので,$B-B-B$ となることはありえないからです.
樹形図
同様にして,問題の条件を満たすように注意しながら樹形図を最後まで書いていくと,下図のようになります.
樹形図
上の樹形図は問題の条件を満たすような $A,B$ の並べ方をすべて書きつくしています.したがって,求めるべき場合の数は,上図での赤い枝の本数に一致します.これを数えて,$10$ 通りであることがわかります.

 $3$ つのさいころ $A,B,C$ を同時に投げるとき,目の積が $12$ となる場合は何通りあるか.

前の問題と同様に樹形図を最後までかくと下図のようになります.
樹形図
赤い枝の本数を数えると,$15$ 本なので,求めるべき場合の数は全部で $15$ 通りであることがわかります.

 $0$ 以上の整数 $a,b,c$ が,$a+b+c=4$ を満たす場合の数を求めよ.

前の問題と同様に樹形図を最後までかくと下図のようになります.
樹形図
赤い枝の本数を数えると,$15$ 本なので,求めるべき場合の数は全部で $15$ 通りであることがわかります.