高校数学をプログラミングで解く（数学A編）「1-3 順列」

マガジンリスト　＞　数学A編 1.場合の数と確率　＞　1-3 順列

はじめに

今回は、数学Aで学ぶ「順列」について、順列、円順列、及び重複順列の総数を計算するプログラムを作成します。

順列

まず、順列について復習しておきます。

1.  順列とは、いくつかのものを、順序をつけて1列に並べる配列

2.  異なる$${n}$$個のものから$${r}$$個を取った順列の総数は

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

で表される。

今回は、この順列の総数$${ {}_nP_r }$$を計算するプログラムを作成します。

アルゴリズム設計 

順列の総数$${ {}_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);
}

プログラム

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

// 異なるn個のものからr個を取った順列の総数
void setup(){

  int n = 7;
  int r = 3;
  int p = 1; // 順列の総数
  for(int i=0; i<r; i++){ 
    p = p * (n-i);
  }
  println(p); // 順列の総数をコンソールに出力
}

ソースコード1　順列の総数を計算するプログラム

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

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

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

課題
この順列の総数のプログラムが正しく動いているか、確認してみてください。例えば、$${ {}_7P_0 }$$、$${ {}_7P_4 }$$、$${ {}_7P_7 }$$、$${ {}_0P_0 }$$などで正しい答えが出力されるか。

円順列

次に、円順列について考えます。円順列について復習しておきます。

1. 円順列とは、いくつかのものを、円形に並べる配列

2.  異なる$${n}$$個のものの円順列の総数は、$${ \frac{ {}_nP_n }{n} = (n-1)! }$$ 

3.  異なる$${n}$$個のものから$${r}$$個を取りだして並べる円順列の総数は$${ \frac{ {}_nP_r }{r} }$$

この円順列の総数を計算するプログラムを作成します。

アルゴリズム設計 

円順列の総数は、順列の総数$${ {}_nP_r }$$を$${r}$$で割ることで計算することができます。すでに$${ {}_nP_r }$$を計算するプログラムは作成しています（ソースコード1）ので、これに$${r}$$で割る処理を追加するだけで計算することができます。

プログラム

円順列の総数を計算するプログラムを作成します。なお、このプログラムではn=7、r=3としています。

// 異なるn個のものからr個を取り出して並べる円順列の総数
void setup(){

  int n = 7;
  int r = 3;
  int p = 1; // 円順列の総数
  for(int i=0; i<r; i++){
    p = p * (n-i);
  }
  p = p / r; // 最後にrで割る
  println(p); // 円順列の総数をコンソールに出力
}

ソースコード2　円順列の総数を計算するプログラム

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

図2　スケッチ「circular_permutation」の実行結果

図2のように、円順列の総数の値「70」をコンソールに出力します。

なお、円順列ではr=0とすることができませんので、注意してください。

重複順列

最後に、重複順列について考えます。重複順列について復習しておきます。

1. 重複順列とは、異なるものから重複を許していくつか取り出して並べる順列

2. $${n}$$個から$${r}$$個取る重複順列の総数は$${n^r}$$

この重複順列の総数を計算するプログラムを作成します。

アルゴリズム設計

重複順列の総数は、$${n}$$を$${r}$$回かけるだけなので、このプログラムは$${ {}_nP_r }$$を計算するプログラムを一部修正するだけで作ることができます。つまり、ソースコード1の

p = p * (n-i);

の部分を

p = p * n;

に書き換えるだけで作成することができます。

プログラム

重複順列の総数を計算するプログラムを作成します。なお、このプログラムではn=7、r=3としています。

// n個からr個取る重複順列の総数
void setup(){
  
  int n = 7;
  int r = 3;
  int p = 1; // 重複順列の総数
  for(int i=0; i<r; i++){ 
    p = p * n;
  }
  println(p); // 重複順列の総数をコンソールに出力
}

ソースコード3　重複順列の総数を計算するプログラム

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

図3　スケッチ「repeated_permutation」の実行結果

図3のように、重複順列の総数の値「343」をコンソールに出力します。

まとめ

今回は、数学Aで学ぶ「順列」について、順列の総数$${ {}_nP_r }$$を計算するプログラムを作成し、その後、そのプログラムに追加、修正する形で円順列、及び重複順列の総数を計算するプログラムを作成しました。特に、プログラムにおける変数は「p = p*n;」のように同じ変数同士を繰り返し更新することができることを利用して、計算を行うことができました。今回のような変数の更新方法は今後もよくでてきます。少しずつ使い方に慣れていってください。

参考文献

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

演習問題

８人の生徒のうち３人が番号のついた３脚のいすに座り、残りの５人が円形のテーブルの周りに並んで座る方法が何通りあるか計算し、結果をコンソールに出力するプログラムを作成してください。

演習問題の解答例