【Python】階乗と順列と組合せ

目的

統計的なデータ分析アプローチの中には確率的な考え方も多く使われます。今回は確率的な手法を用いる際に必要となる基本知識について、pythonのコードの勉強もかねて実践してみたいと思います。具体的には階乗、順列、組合わせです。

階乗の計算方法

階乗とはある変数の並び方が何通りあるかの計算です。

例えばAさん、Bさん、Cさん、Dさんという４人の組があった場合に、この人たち並べ方のパターンは4×3×２×1=24通りあります。

一般化した式は以下の通りです。

$$n! = n(n-1)(n-2)(n-3)…4\times3\times2\times1$$

この\(n\)の計算が階乗です。

これをpythonで計算すると以下のようになります。mathライブラリのfactorialメソッドの引数に変数の数\(n\)を入れて計算します。

#math ライブラリの読み込み
import math

# n=4 の階乗を計算
math.factorial(4) #24

順列の計算

今度はAさん、Bさん、Cさん、Dさんの４人の中から2人だけ選んで並び替えるとした時に何パターンあるかを計算したいとします。
この考え方を順列と呼びます
まず、最初にどの人を選ぶかで4パターンあります。次に残った３人から誰を選ぶかで3パターンあります。この時点で\(4\times3\)パターンあります。
そして、選んだ二人の並び替えでどちらが先にくるか、で2パターンあります。よって\(4\times3\times2\times\)で24パターンあることになります。

このとき、最初にどの人を選ぶかで4パターンあります。次に残った３人からだれを選ぶかで3パターンあります。この時点で\(4\times3\)パターンあります。
そして、選んだ二人の並び替えでどちらが先にくるか、で2パターンあります。よって\(4\times3\times2\times\)で24パターンあることになります。

ただし、この場合は先にAさんを選んでからBさんを選んで並べた場合と、先にBさんを選んでからAさんを選んで並べた場合で同じ並びが出てきます。そのため、重複した分の2で割ってやる必要があります。
よって、結局は\(24 \div2=12\)で12通りになります。

人数を\(n\)人、選ぶ人を\(r\)人とすると以下のように一般化できます。

$$ {}_n P_r= n(n-1)(n-2)…(n-r+1)=\frac{n!}{(n-r)}$$

\({}_n P_r\) の計算を順列と呼びます。

pythonでは上述のfactorialメソッドを使った コードで計算できます。
\(n\)が総人数、\(r\)が選ぶ人数です。

import math

n=4
r=2

# n!/(n-r)
P = (math.factorial(n))/math.factorial((n-r))

print(P) #12

組合せの計算

順列の計算では4人から2人を選んで並び替えを行いましたが、組合せは選んだ２人の並び方は問わない場合に何通りあるか、という考え方です。例えばAさん、Bさん、Cさん、Dさんの4人からAさん、Bさんを選んだとします。

この時、順列の計算の場合はABという並びとBAという並びを区別し、２通りとカウントしましたが、組合せはABとBAは同一とみなします。

よって順列の計算結果からさらに重複を削除することになります。よって、4人から2人を選ぶ組合せは順列の計算結果の\(12\)を重複数の2で割りますので、\(12\div2=\)で6通りとなります。

一般化を考えた場合、\(n\)人から\(r\)任を取り出した際の順列計算からの重複分は\(r!\)となります。よって以下の式になります。

$${}_nC_r = \frac{n!}{r!(n-r)!}$$

この \({}_nC_r\)の計算が組合せです。

pythonで記述すると以下のようになります。

import math

n = 4
r = 2

# n!/(n-r)!
C = (math.factorial(n))/(math.factorial(r)*math.factorial((n-r)))

print(C) #6

まとめ

math.factorial()が使えれば階乗と順列と組合せは非常に簡単に計算できてしまいます。ただ、やはり考え方や式はきっちり理解した上で使いたいなぁと思います。