排列組合python，從排列與組合的python實現到生日問題的解釋

在 數論及Python實踐一文中，我們介紹了組合的基本定義以及一些常規實現方法，并未充分發揮python語言的優勢，本文我們從reduce函數的角度（從這個角度我們應當恢復reduce正宮娘娘的地位，因為在python3中Guido將reduce從系統內置函數降格為functools中的函數），重新實現給出排列組合的各自實現，以及據此給出”生日問題”的概率解釋。

$$\begin{split} &\binom{n}{k}=\frac{n!}{k!(n-k)!}\\ &\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1} \end{split}$$
第二行公式可看做其遞歸定義式。我們換個記號繼續推導：
$$\begin{split} C_n^k=&C_{n-1}^k+C_{n-1}^{k-1}\\ =&C_{n-1}^k+C_{n-2}^{k-1}+C_{n-2}^{k-2}\\ =&\cdots \end{split}$$
這里還有一個經典的結論：
$$\sum_{k=0}^n\binom{n}{k}=2^n$$
如何證明，其實很簡單，回歸定義（組合數combination，又叫二項式系數binomial coefficients），對 $2^n$進行二項展開，即：
$$\begin{split} 2^n=&(1+1)^n\\ =&\binom n0+\binom n1+\cdots+\binom n{n-1}+\binom n{n}\\ =&\sum_{k=0}^n\binom nk \end{split}$$

排列組合python？

$2^n$ 這不正是二進制嘛！這個結論有什么用？舉個栗子，給定三個卡片，編號為 $1-3$，使用該等式可得其會有 $2^3=8$種組合（combinations或叫subsets）（包括空集）：

$$|\{\{\};\{1\};\{2\};\{3\};\{1,2\};\{1,3\};\{2,3\};\{1,2,3\}\}|=8$$
以二進制的形式理解的話即為：

• 0：000
• 1：001
• 2：010
• 3：011
• 4：100
• 5：101
• 6：110
• 7：111

再來考慮這樣一種情形，從 $n$個數中隨機選擇 $k$個，再從余下的 $n-k$個隨機選擇$p$個，組合數一共多少：

$$\binom{n}{k}\cdot\binom{n-k}{p}=\frac{n!}{k!(n-k)!}\cdot\frac{(n-k)!}{p!(n-k-p)!}=\frac{n!}{k!p!(n-k-p)!}$$
將此記為：$\binom{n}{k,\,p}$，也即 $\binom{n}{k,\,p}=\frac{n!}{k!p!(n-k-p)!}$

再來看幾個結論：

$$A_n^k=\frac{n!}{(n-k)!}$$
所以有：
$$\binom{n}{k}A_k^k=\frac{n!}{k!(n-k)!}k!=A_n^k$$

python中排序、

$$N^k\neq \left [ A_N^k=\binom{N}{k}A_k^k\right ]$$

左邊允許重復，右邊不允許重復；

當我們試圖用reduce實現組合數的計算時，

$$\binom{n}{k}=\frac{n!}{k!(n-k)!}=\frac{\prod\limits_{i=n-k+1}^ni}{k!}=\frac{A_n^k}{k!}$$

python生日，

from functools import reduce
import operatordef fac(n):return reduce(operator.mul, range(1, n+1), 1)# 階乘n!的定義# reduce與operator.mul結合
def perm(n, k):return reduce(operator.mul, range(n-k+1, n+1), 1)   # 排列數的定義
def comb(n, k):return perm(n, k)//fac(k)                   def test():print('{}!={}'.format(5, fac(5)))print('A_{}^{}={}'.format(5, 2, perm(5, 2)))print('C_{}^{}={}'.format(5, 2, comb(5, 2)))
if __name__ == '__main__':test()

運行結果為：

5!=120
A_5^2=20
C_5^2=10

由以上準備，我們可求解概率論史上的經典問題（概率論史上的經典問題一般是指違反直覺的那些問題）”生日問題”：

一次聚會上，只要有23個人，就有50%的可能性其中至少有兩個人生日相同，如果人數達到50人，至少有兩個人生日相同的概率達到97%。（這個結論很恐怖，只要是班上的人數超過50，老師便可以說，我們班至少有兩個人生日相同，其實在人數超過23的時候，我們便可以這么說，應為概率占優，注意，是班上會有來個人生日相同，不是說，班上至少存在一個人生日生日與我相同）。

當然這類問題從其反問題對立事件出發，$1-P(所有人都不在同一天)=P(至少有兩人在同一天)$，

$$p=1-\frac{A_{365}^{23}}{365^{23}}\\ p=1-\frac{A_{365}^{50}}{365^{50}}$$

python 3。

這里的$A_{365}^{50}$可以理解為，隨意指定一個生日，他生日所在的自由度（或者作可選空間）為365，則下一個人只有365-1的自由度，依次類推。$365^{50}$是考慮到這50個人的生日大體獨立，也即每一個的生日都有365個自由度（也即365種選擇）。所謂概率，頻率的觀點（另有貝葉斯的觀點）來看就是出現的次數與總的可能性之比。

>>> 1-perm(365, 23)/(365**23)
0.5072972343239854
>>> 1-perm(365, 50)/(365**50)   
0.9703735795779884

注意：如果預先指定一個生日，隨機選取125人，250人，500人，出現某人生日正好是這一生日的概率分別是：

$$1-(\frac{364}{365})^{125}\approx0.29031618790748226\\ 1-(\frac{364}{365})^{250}\approx0.49634888685383205\\ 1-(\frac{364}{365})^{500}\approx0.7463355562266258$$

python生日祝福，比想象的要小很多，再次說明概率中的許多問題都比較違反直覺。

補充：

$$365^{50} \neq \binom{365}{50}A_{50}^{50}$$
為什么不等于呢？在于，左邊 “允許重復”（同一個位置，既可以是你，也可以是他），右邊 不允許重復；