組み合わせの計算をPythonで作ってみる

問題意識

以前の記事で組み合わせ計算をPythonで再帰的にやったけれども、他のやり方もあるよな、と思い返してみました。

組み合わせの復習

順列組み合わせで習った組み合わせのの方です

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

でしたね。ここでn < rの時は組み合わせは0、つまり

_0C_1=0

など、定義から外れているものは0と約束しておきます。

漸化式っぽく

今回はPythonで再帰的に関数を呼び出す方法を採りたいので漸化式っぽいものを用意します。

漸化式1: rを下げる

_nC_r=_nC_{r-1}\times\frac{n-r+1}{r}

証明

まず、定義から

_nC_r=\frac{n!}{r!(n-r)!}=\frac{n!}{r\times(r-1)!\times(n-r)!}=\frac{n!}{(r-1)!\times(n-r)!}\times\frac{1}{r}\\
_nC_{r-1}=\frac{n!}{(r-1)!\times(n-r+1)\times(n-r)!}=\frac{n!}{(r-1)!\times(n-r)!}\times\frac{1}{n-r+1}

よって

r\times_nC_r=(n-r+1)_nC_{r-1}

両辺をrで割れば示すべき式が得られる■

漸化式2: nを下げる

_nC_r=_{n-1}C_{r-1}+_{n-1}C_r

こっちは、Pascalの三角形を考えれば自明ですが、あまり深い入りしないことにしますー

証明

\begin{eqnarray}
_nC_r+_nC_{r-1} &=& \frac{n!}{r!(n-r)!}+\frac{n!}{(r-1)!(n-r+1)!}\\
&=& \frac{n!\times\{(n-r+1)+r\}}{r!(n-r+1)!}\\
&=& \frac{n!\times(n+1)}{r!(n-r+1)!}=\frac{(n+1)!}{r!(n+1-r)!}\\
&=& _{n+1}C_r
\end{eqnarray}

■

Pythonで書いてみる

漸化式1

_nC_r=_nC_{r-1}\times\frac{n-r+1}{r}

を元に、端っこ、つまり初期値設定として

_0C_r=_nC_0=1

returnする関数として再帰的に書くとこんな感じ（以前の記事にあったものと同一）

def comb1(n, r):
    if n == 0 or r == 0: return 1
    return comb1(n, r-1) * (n-r+1) / r 

漸化式2

_nC_r=_{n-1}C_{r-1}+_{n-1}C_r

を元に初期値設定させたものが以下：

def comb2(n,r):
    if n < 0 or r < 0 or n < r: 
        return 0
    elif n == 0 or r == 0: 
        return 1
    return comb2(n-1,r-1)+comb2(n-1,r)

漸化式1より初期値設定が若干複雑なのは、n,rの両方が変化するからですねー。

試してみる

早速動かしてみよう。

>>> comb1(20,5)
15504.0
>>> comb2(20,5)
15504

既存のscipyの関数で確認

>>> import scipy.misc as scm
>>> scm.comb(20, 5)
15504.0

→うん、合ってそうですね♪(全然証明にはなってませんがw)

参考にさせて頂いたサイト

• Pythonで組み合わせ(Combination)を計算