In Previous article, I recursively performed combination calculation in Python, but I thought that there are other ways.
This is the combination that I learned from the permutation combination.
_nC_r=\frac{n!}{r!(n-r)!}
It was. Here, when n <r, the combination is 0, that is,
_0C_1=0
I promise 0 if it is out of the definition.
This time, I want to adopt the method of recursively calling the function with Python, so I will prepare something like a recurrence formula.
r_nC_r=_nC_{r-1}\times\frac{n-r+1}{r}
First, from the definition
_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}
Therefore
r\times_nC_r=(n-r+1)_nC_{r-1}
Divide both sides by r to get the formula to show ■
n_nC_r=_{n-1}C_{r-1}+_{n-1}C_r
This is self-explanatory considering Pascal's triangle, but I will not go too deeply-
\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}
■
_nC_r=_nC_{r-1}\times\frac{n-r+1}{r}
Based on, as the edge, that is, as the initial value setting
_0C_r=_nC_0=1
When written recursively as a function to return, it looks like this ([previous article](http://qiita.com/kyoro1/items/eed40ab333a9f9fd8ede#python%E3%81%A7%E3%82%B0%E3%] 83% A9% E3% 83% 95% E3% 82% 92% E6% 8F% 8F% E3% 81% 84% E3% 81% A6% E3% 81% BF% E3% 82% 8B) Same as)
def comb1(n, r):
if n == 0 or r == 0: return 1
return comb1(n, r-1) * (n-r+1) / r
_nC_r=_{n-1}C_{r-1}+_{n-1}C_r
The following is the initial value set based on:
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)
The reason why the initial value setting is a little more complicated than the recurrence formula 1 is that both n and r change.
>>> comb1(20,5)
15504.0
>>> comb2(20,5)
15504
>>> import scipy.misc as scm
>>> scm.comb(20, 5)
15504.0
→ Yeah, that's right ♪ (It's not proof at all, but w)
-Calculate Combination in Python
Recommended Posts