MENU

組み合わせ（漸化式）

_n C_r を漸化式を使って求めてみる

ja.wikipedia.org n 個の中から r 個を選ぶ組み合わせの数を _n C_r と表現し, 以下のような式で表されます。

{ \displaystyle _n C_r = \frac{n!}{r!(n-r)!} }

n! は n・(n-1)・(n-2)...2・1 で表される階乗。C はConbination の頭文字から取っています。 この式で計算した場合, 大きな n の時に n! がオーバーフローすることがあります。 int 型なら 13! は 6227020800 なのでintが扱える範囲を超えています。

そこで漸化式を用いて表現することを考えます。漸化式は、各項がそれ以前の項の関数として定まるという意味で数列を再帰的に定める等式です。

例えば _n C_r は,

{ \displaystyle \begin{eqnarray} \left\{ \begin{array}{l} _n C_r = \frac{n-r+1}{r} {_n C_r} \\ _n C_0 = 1 \end{array} \right. \end{eqnarray} }

という漸化式を利用して表すこともできます。こちらは乗法表示による表現であり、

{ \displaystyle \begin{eqnarray} \left\{ \begin{array}{l} _n C_r = _{n-1} C_{r-1} + _{n-1} C_r \\ _n C_0 = 1 \end{array} \right. \end{eqnarray} }

という純加法表現で表すこともできます。

プログラム

漸化式をプログラムにする場合は、繰り返し又は再帰呼び出しを用いて表現できます。

以下は繰り返しによる乗法表現

#include <iostream>
#include <iomanip>
using namespace std;

long combination(int,int);

int main(){
    int n,r;
    for (n=0;n<=6;n++){
        for (r=0;r<=n;r++)
            cout << setw(3) << n << " C " << r << " = " << setw(2) <<combination(n,r);
        cout << endl;
    }
    return 0;
}

long combination(int n,int r){
    int i;
    long p=1;

    for (i=1;i<=r;i++)
        p=p*(n-i+1)/i;
    return p;
}

次は再帰呼び出しによる加法表現です。

#include <iostream>
#include <iomanip>
using namespace std;

long combination(int,int);

int main(){
    int n,r;
    for (n=0;n<=6;n++){
        for (r=0;r<=n;r++)
            cout << setw(3) << n << " C " << r << " = " << setw(2) <<combination(n,r);
        cout << endl;
    }
return 0;
}

long combination(int n,int r){
    if (r == 0 || r == n)
        return (1);
    else if (r == 1)
        return (n);
    return (combination(n-1,r-1) + combination(n-1,r));
}

実行結果

  0 C 0 =  1
  1 C 0 =  1  1 C 1 =  1
  2 C 0 =  1  2 C 1 =  2  2 C 2 =  1
  3 C 0 =  1  3 C 1 =  3  3 C 2 =  3  3 C 3 =  1
  4 C 0 =  1  4 C 1 =  4  4 C 2 =  6  4 C 3 =  4  4 C 4 =  1
  5 C 0 =  1  5 C 1 =  5  5 C 2 = 10  5 C 3 = 10  5 C 4 =  5  5 C 5 =  1
  6 C 0 =  1  6 C 1 =  6  6 C 2 = 15  6 C 3 = 20  6 C 4 = 15  6 C 5 =  6  6 C 6 =  1