組合せの数

作成日:2002-09-27
最終更新日:

n 個の相異なるものの中から r 個を取り出す組合せはいくつあるか、という古典的な問題がある。 この組み合わせの数は、`{::}_nC_r`あるいは`((n),(r))`と表記される。

この組合せの数を計算機で求める問題が、雑誌 bit の「ナノピコ教室」で出題された。 数学的には `((n),(r))=(n!)/((n-r)!r!)` であるが、このまま右辺の分子と分母を個別に計算すると、 組み合わせの数そのものがオーバーフローしない場合でも、分子がオーバーフローしてしまって値が求められないことがある。 この出題に対して、入山徳夫氏が、 途中の計算でオーバーフローをできるだけ起こさないような工夫されたアルゴリズムでの解を提出された。 今回は、この入山氏のアルゴリズムを用いている。

総個数 n 取り出す数 r
組合せの数

ただ、途中で 2147483647 `(=2^31 - 1)`を超えると、 整数の桁あふれのおそれありと考えた。この場合は、 近似値であるという断りを出すことにした。(2008-05-03)

まりんきょ学問所JavaScript 手習い > 組合せの数


MARUYAMA Satosi