高校数学をプログラミングで解く（数学A編）「1-4 組合せ」

マガジンリスト　＞　数学A編 1.場合の数と確率　＞　1-4 組合せ

はじめに

今回は、数学Aで学ぶ「組合せ」について、組合せの総数を計算するプログラムを作成します。

組合せ

まず、組合せについて復習しておきます。

1.  異なる$${n}$$個のものから$${r}$$個を取る組合せの総数は

$$
{}_nC_r=\frac{{}_nP_r}{r!} =\frac{n!}{r!(n-r)!} = \frac{n(n-1)(n-2)\cdot \cdots \cdot (n-r+1)}{r(r-1)(r-2) \cdot \cdots \cdot 2 \cdot 1}
$$

で表される。ただし、$${r \leq n}$$。
特に、

$$
{}_nC_n=1, \ \ {}_nC_0=1
$$

2.  $${ {}_nC_r }$$の基本性質

$${ {}_nC_r = {}_nC_{n-r} }$$　ただし、$${ 0 \leq r \leq n }$$
$${ {}_nC_r = {}_{n-1}C_{r-1} + {}_{n-1}C_r }$$　ただし、$${ 1 \leq r \leq n-1}$$、$${n \geq 2 }$$ 

今回は、この組合せの総数$${ {}_nC_r }$$を計算するプログラムを作成します。

アルゴリズム設計 

記事『高校数学をプログラミングで解く（数学A編）「1-3 順列」』で説明したように、順列の総数$${ {}_nP_r }$$は、 $${n}$$に$${n-1}$$をかけて、次に$${n-2}$$ をかけて、と順に$${n-r+1}$$までかけることで計算することができました。これをプログラムで実現するために、変数を繰り返し更新する方法を利用しました。これについて復習しておきます。
int型の変数 p を考えます。

int p = 1;

この場合、変数 p は宣言とともに、1 で初期化されます。つまり、変数 p には 1 が入っています。この変数 p に対して、次のような処理を行います。

p = p * n;

これは p に n をかけて、それを改めて p に代入するという処理になり、p は 1 から n に更新されます。この変数の使い方を利用すると、$${ {}_nP_r }$$ は、

int p = 1;
p = p * n; // n に更新
p = p * (n-1); // n(n-1) に更新
p = p * (n-2); // n(n-1)(n-2) に更新
・・・
p = p * (n-r+1); // n(n-1)(n-2)・…・（n-r+1）に更新

と変数 p を順に繰り返し更新していくことで、計算することができます。繰り返し処理ですので、実際には for ループで次のように書きます。

int p = 1;
for(int i=0; i<r; i++){
  p = p * (n-i);
}

今回の組合せの総数$${{}_nC_r}$$の計算では、分子の$${{}_nP_r}$$の計算にそのまま利用できます。また、分母の$${r!}$$も、$${r}$$に$${r-1}$$をかけて、次に$${r-2}$$をかけて、と順に$${1}$$までかけることで計算することができますので、同様の繰り返し処理を利用できます。

プログラム

では、プログラムを作成していきます。なお、このプログラムでは n=7、r=3 としています。

// 異なるn個のものからr個を取る組合せの総数
void setup(){
  
  int n = 7;
  int r = 3;
  int p = 1; // 組合せの総数の分子
  int q = 1; // 組合せの総数の分母
  for(int i=0; i<r; i++){ 
    p = p * (n-i);
    q = q * (r-i);
  }
  int c = p / q; // 組合せの総数を計算
  println(c); // 組合せの総数をコンソールに出力
}

ソースコード1　組合せの総数を計算するプログラム

このソースコードを、Processingの開発環境ウィンドウを開いて（スケッチ名を「combination」としています）、テキストエディタ部分に書いて実行します。

図1　スケッチ「Combination」の実行結果

図1のように、$${ {}_7C_3 }$$の値「35」をコンソールに出力します。

課題
この組合せの総数のプログラムが正しく動いているか、確認してみてください。例えば、$${ {}_7C_0 }$$、$${ {}_7C_4 }$$、$${ {}_7C_7 }$$、$${ {}_0C_0 }$$などで正しい答えが出力されるか。

プログラムの問題点

ソースコード1で書いた組合せの総数$${{}_nC_r}$$を計算するプログラムは$${n}$$や$${r}$$の値が大きくなると、使うことができなくなります。
例えば、$${{}_{13}C_{12}}$$の計算を考えてみます。この場合、ソースコード 1の中で、
p=13・12・…・2＝6,227,020,800、q=12・11・…・1＝479,001,600 となり、最後に、p/q=13となるはずです。ところが、このような計算はできません。なぜなら、int型の整数は最大値 2,147,483,647 までしか扱えませんので、p に 6,227,020,800 は代入できないわけです。実際に、ソースコード1で n=13, r=12 として実行した結果「4」と間違った値がコンソールに出力されました。

図2　ソースコード１でn=13,r=12とすると間違った結果を与える

以下では、この問題点に対する完全な解決方法ではないですが、ソースコード1よりももう少し大きな$${n}$$や$${r}$$の値でも利用できるように改善してみます。

プログラムの改善

それには、 $${{}_nC_r}$$の基本性質の$${ {}_nC_r = {}_nC_{n-r} }$$を利用します。つまり、$${r}$$と$${n-r}$$とを比較して、$${r}$$より$${n-r}$$が小さければ、$${r}$$を$${n-r}$$で置き換えます。このとき、$${ {}_nC_r = {}_nC_{n-r} }$$なので、組合せの総数はこの置き換えで変わりません。そして、$${n=13, r=12}$$の例では、$${ n-r=1<12=r }$$となるので、$${r}$$を$${n-r=1}$$で置き換えると、ソースコード1で p=13, q=1 となり、p/q=13 と問題なく計算できます。
改善したプログラムを以下に示します。

// 異なるn個のものからr個を取る組合せの総数
void setup(){

  int n = 13;
  int r = 12;
  // n-rがrより小さければ、rをn-rで入れ替える
  if( n-r < r ){
    r = n-r;
  }
  int p = 1; // 組合せの総数の分子
  int q = 1; // 組合せの総数の分母
  for(int i=0; i<r; i++){
    p = p * (n-i);
    q = q * (r-i);
  }
  int c = p / q; // 組合せの総数を計算
  println(c); // 組合せの総数をコンソールに出力
}

ソースコード2　組合せの総数を計算するプログラム（改善版）

このソースコードを、Processingの開発環境ウィンドウを開いて（スケッチ名を「combination_r2」としています）、テキストエディタ部分に書いて実行します。

図３　スケッチ「combination_r2」の実行結果

図3のように、$${ {}_{13}C_{12} }$$の正しい値「13」をコンソールに出力します。

まとめ

今回は、数学Aで学ぶ「組合せ」について、組合せの総数$${ {}_nC_r }$$を計算するプログラムを作成しました。最初は単純に$${ {}_nC_r }$$を計算するプログラムを作成しましたが、$${n}$$や$${r}$$が大きくなるとint型変数の最大値を超えてしまい、うまく計算することができなくなります。そこで、$${ {}_nC_r }$$の基本性質を利用してプログラムを改善しました。
プログラムを作成するときは、このような改善を必要とすることがよくあります。自分の知識を総動員し、必要であればもっと勉強してこのような改善にあたります。自分で考えた改善方法がうまく機能したときの達成感はすごく気持ちいいものです。ぜひ皆さんにも体験してもらいたいです。

参考文献

改訂版 教科書傍用 スタンダード 数学A（数研出版、ISBN9784410209277）

演習問題

アルファベット「a」が 3 個、「b」が 4 個、「c」が 1 個の 8 文字を１列に並べる方法が何通りあるかを求めて、コンソールに出力するプログラムを作成してください。

ヒント：同じものを含む順列

$${n}$$個のもののうち、$${p}$$個は同じもの、$${q}$$個は別の同じもの、$${r}$$個はまた別の同じもの、$${\cdots \cdots}$$であるとき、これら$${n}$$個のものを１列に並べる順列の個数は

$$
\frac{n!}{p!q!r!\cdots \cdots} \ \ ( = {}_n C_p \times {}_{n-p}C_q \times {}_{n-p-q} C_r \times \cdots \cdots )
$$

ただし、$${p+q+r+\cdots \cdots = n}$$

演習問題の解答例