確率統計(nCrとnPr)

順列と組み合わせ


 ・n個の中からr個を選んで順序をつけてできる組み合わせnPrと表す(順列:permutation)。

 ・n個の中からr個を選ぶ組み合わせの総数をnCrと表す(組み合わせ:combination)。

 これらはそれぞれ以下のような公式で表される。



計算方法


 これらを実際に計算するときは以下のように変形する。

 このようにすることで...

 nPrの計算は乗算のみで行うことができる。

 nCrの計算はnPrに比べ若干複雑だ。まず は分母と分子に分けてすぐに乗算をするのではなく、一度簡単な約分をする。その後、それ ぞれ乗算して求め、最後に除算1回行う。約分は素因数分解して行うと効率がいいが、素因数 分解に要する計算量を考えると行わないほうがいい。また除算を行っているので結果を小数 点位置で四捨五入を行う。


組み合わせの高速計算方法


 組み合わせを図のように並べた三角形を「パスカルの三角形」と呼ぶ。


 先ほどの方法で組み合わせを計算すると除算があるために遅い。しかしこのパスカルの三角 形を用いると高速に計算することが可能。

 パスカルの三角形を以下のように展開して必要なところまで計算すればいい。
   
 メモリ内には横列の情報が格納できればいい。そのため計算に使うのは1次元配列のみ。
 1回のループで1行ずつ情報を更新し、nCrのn回分だけループをまわせばnCrの数値は配 列のr個目に格納される。


計算結果


 nPr、nCrにおいてそれぞれ n = 64 までを求めた結果を挙げる。

順列(nPr)一覧0P064P64

組み合わせ(nPr)一覧0C064C64

カテゴリー「VC++ TIPS」 のエントリー