順列・組み合わせ
確率につながる考え
17世紀にパスカル(1623～1662)とフェルマー(1601～1665)の手紙のやり取りから始まった確率論は、統計学と切っても切り離せない双子のような関係とも言えます。確率は、全ての起こりうるケースの数と注目するケースの数の割合を示すのですが、その確率を計算するためには起こりうる全てのケースの数を導き出すことから始めなければなりません。
起こりうるケースの数を調べる方法に順列と組み合わせの公式があります。順番が無視できないものを順列といい、順番を無視してもよいものが組み合わせです。以下にその公式を示します。
n! n!
nPr ＝ ---------- nCr ＝ --------------
(n - r)! r!・(n - r)!
ここで、「!」は階乗計算の時に使用する記号で、「3!」は「3 * 2 * 1」のことで、「10!」は「10 * 9 * 8 * 7 * 6 * 5 * 4 * 2 * 1」ですね。rpnでは以下のようになります。
6
>rpn 10 !
3.6288e+06
rpnで順列を計算してみる
上記の公式nPrが順列の数で、nCrが組み合わせの数なのですが、rpnで実際に5個のボールから3個のボールを取り出す時の順列と組み合わせの数を計算してみましょう。順列の場合は以下のとおりです。数式と一緒に示します。
nPr ＝ --------
(5 - 3)!
>rpn 5 #n 3 #r @n ! @n @r - ! /
60
結果、60通りの数があります。これは5個のボールから1つずつボールを取り出し、一列に並べた時の3つの数字のパターンが60通りあることを示しています。
rpnで組み合わせを計算してみる
次に、組み合わせの数ですが、以下のとおりです。
nCr ＝ ------------
3!・(5 - 3)!
>rpn 5 #n 3 #r @n ! @r ! @n @r - ! * /
10
今度は、10通りになります。5個のボールから一度に3つのボールを取り出して、順番を考えずに3つの数字の組み合わせにだけ注意して数えると、10通りあることを示しています(例えば、(1,2,3)と(1,3,2)は重複として数えない)。
組み合わせの数のほうが圧倒的に少ないですね。組み合わせの数は取り出すボールの数が5個の半分を超えると組み合わせ数は減っていき、5個から5個を取り出す組み合わせの数は1になります(全部取り出すのだから当たり前といえば当たり前)。rpnで公式に当てはめて実際に計算すると以下のとおりです。
1
それに対して、順列の数は取り出すボールの数が増えれば増えるほど急速に大きな値になっていきます。実際、5個から5個取り出す順列の数を公式に当てはめて、rpnで計算すると以下のとおりになります。
120
120通りにもなっていますね。
nPrやnCrの公式は事象を数え上げる時によく利用しますが、計算結果の数が急激に増えてしまう場合があります。これを「組み合わせ的爆発」と言います。例えば、チェスや将棋、囲碁といったゲームで、相手と自分の手の全ての組み合わせを考慮に入れるときなどに発生します(将棋の組み合わせ数は10の220乗)。組み合わせの爆発が発生すると現在のコンピュータ性能を持ってしても事実上、処理不可能になってしまいます。
階乗に関する面白い話
ところで、0からnまでの階乗の逆数の総和はある数に収束するそうです。
∑ ----- = ?
n=0 n!
さっそくrpnで試してみましょう。0から4までの階乗の逆数の総和をそれぞれ計算してみます。
1 2 2.5 2.66667 2.70833
グラフにすると次のようになります。収束している感じが出ていますね。
-
| * *
| *
- *
|
*
| x
|o 4
+------|------|-------|------>
0から10まで計算してみると…。値は2.71828。あのネピア数でした。なんとも不思議です。
『今回の問題』………………………………………………………………………
以下を逆ポーランド式に変換せよ(レジスタを使わないこと)。
(1) 1～9まで番号が振られたボールを袋から順に全部取り出して並べた
時の並び方のパターン数を求める式。
(2) 1～9まで番号が振られたボールを袋から順に3個取り出して並べた時
の並び方のパターン数を求める式。
(3) 1～9まで番号が振られたボールを袋から同時に3個取り出した時の数
字の組み合わせパターン数を求める式。
(4) 0～10までの階乗の逆数の総和を求める式。
(5) 40－32÷2と等しい階乗値を求める式。
…………………………………………………………………………………………
/