順列・組み合わせ | rpn入門(初級編) [講座] | 逆ポーランド電卓の実践ウェブ rpn hacks!

逆ポーランド電卓の実践ウェブ rpn hacks!

逆ポーランド電卓rpnの実践ウェブ   
rpn hacks! アールピーエヌ・ハックスサイトマップ

rpn | 講座 | rpn入門 | rpnの使い方を基本から応用まできちんと学習。

HOME > 講座 > rpn入門 > 初級編 > 順列・組み合わせ hatena yahoo buzzurl livedoor del.icio.us nifty newsing twitter facebook rss ソーシャルブックマーク

順列・組み合わせ

確率につながる考え

 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では以下のようになります。

  >rpn 3 !
  6
  >rpn 10 !
  3.6288e+06


rpnで順列を計算してみる

 上記の公式nPrが順列の数で、nCrが組み合わせの数なのですが、rpnで実際に5個のボールから3個のボールを取り出す時の順列と組み合わせの数を計算してみましょう。順列の場合は以下のとおりです。数式と一緒に示します。

            5!
  nPr = --------
         (5 - 3)!

  >rpn 5 #n 3 #r @n ! @n @r - ! /
  60


結果、60通りの数があります。これは5個のボールから1つずつボールを取り出し、一列に並べた時の3つの数字のパターンが60通りあることを示しています。

(1,2,3)(1,2,4)(1,2,5)(1,3,2)(1,3,4)(1,3,5)(1,4,2)...   60通り

rpnで組み合わせを計算してみる

 次に、組み合わせの数ですが、以下のとおりです。

             5!
  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)は重複として数えない)。

(1,2,3)(1,2,4)(1,2,5)(1,3,4)(1,3,5)(1,4,5)(2,3,4)...   10通り


組み合わせの数のほうが圧倒的に少ないですね。組み合わせの数は取り出すボールの数が5個の半分を超えると組み合わせ数は減っていき、5個から5個を取り出す組み合わせの数は1になります(全部取り出すのだから当たり前といえば当たり前)。rpnで公式に当てはめて実際に計算すると以下のとおりです。

  >rpn 5 #n 5 #r @n ! @r ! @n @r - ! * /
  1


それに対して、順列の数は取り出すボールの数が増えれば増えるほど急速に大きな値になっていきます。実際、5個から5個取り出す順列の数を公式に当てはめて、rpnで計算すると以下のとおりになります。

  >rpn 5 #n 5 #r @n ! @n @r - ! /
  120


120通りにもなっていますね。

注釈nPrやnCrの公式は事象を数え上げる時によく利用しますが、計算結果の数が急激に増えてしまう場合があります。これを「組み合わせ的爆発」と言います。例えば、チェスや将棋、囲碁といったゲームで、相手と自分の手の全ての組み合わせを考慮に入れるときなどに発生します(将棋の組み合わせ数は10の220乗)。組み合わせの爆発が発生すると現在のコンピュータ性能を持ってしても事実上、処理不可能になってしまいます。

階乗に関する面白い話

 ところで、0からnまでの階乗の逆数の総和はある数に収束するそうです。

  ∞   1
  ∑ ----- = ?
  n=0  n!


さっそくrpnで試してみましょう。0から4までの階乗の逆数の総和をそれぞれ計算してみます。

  >rpn 0 ! n . 1 ! n + . 2 ! n + . 3 ! n + . 4 ! n +
  1 2 2.5 2.66667 2.70833


グラフにすると次のようになります。収束している感じが出ていますね。

  ^y 4
  -
  |                    *       *
  |             *
  -      *
  |
  *
  |                            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と等しい階乗値を求める式。
…………………………………………………………………………………………

答えはこちらLinkIcon

警告文字で作られた図表や式が崩れることがあります。ブラウザによっては固定幅フォントをMSゴシックにするときれいに表示されます。それでも崩れる場合は図表や式をメモ帳にコピー後、閲覧下さい。

警告rpn試用版と標準版(2kリビジョン)はダブルクォートで囲ってください。

rpn 1 2 + ⇒ rpn "1 2 +"
rpn 1 -c foo ⇒ rpn "1" -c "foo"

ダブルクォートは省略できることが多いのですが、慣れない間は囲んだほうが無難です。なお、本ウェブサイトの記事ではrpn標準版(98リビジョン)を使用しているため囲っていません。詳しくは技術サポートの「rpn TIPS参照ください。

注意rpnの障害情報はこちら

警告rpn試用版の場合、複雑なプログラムや処理時間のかかるプログラムの一部には動作しないものがあるかもしれません。あくまで無料提供であることを勘案・了承ください。rpn標準版は、すべてのプログラムが動作します。