[ Math CC ] Probability and Statistics - C(N, K)

Preface : 
由於我的記憶實在不好, 所以整理一下常用數學概念筆記方便日後參考. 這裡要說明的是 C(N,K) 問題. 

C(N,K) - N 取 K 問題 : 
考慮有問題如下 : 
 

這邊的 C(N,K) 指的是從一個集合大小為 N 中取出 K 的 items 不考慮順序的可能組合. 考慮 N=3, K=2 的話可以如下圖理解 : 
 

公式推導 : 
由問題的提示我們可以知道 C(N,K) = C(N-1,K) + C(N-1,K-1). 但這個公式是怎麼來的呢? 從集合中的某個物件的角度來說, 你可以這麼看 : 

C(N,K) = (某個物件被選取的組合) + (某個物件沒被選取的組合)

那麼我們來看 (某個物件被選取的組合) 這個含意就是說 : 某一個物件被選取下, 剩下 K-1物件從 N-1物件中挑選的組合 -> C(N-1, K-1) 
那麼 (某個物件沒被選取的組合) 也就是說 : 從 N-1 個物件 (去掉該被選取的物件), 取出 K 個物件 -> C(N-1, K) 
所以最後我們得到 : C(N,K) = C(N-1,K) + C(N-1,K-1) 

事實上這是一個很有名的定理 - 巴斯卡法則 : 

在上面 "巴斯卡法則" 鏈結到 wiki 上面有對應的推導過程, 公式推導是死的. 重點要了解背後的物理意義. 我們知道公式如下 : 
 

其中 n! 你可以理解在有 n 個物件的袋子依序取出 n 個物件的可能排列組合(考慮順序). 如 n=3 的話 : 
 
(也就是說 n=3, n!=3*2*1) 

那 m! 指的是我們取出來的 m 個物件中, 這 m 個物件的取出順序是不被考慮的; 而 (n-m)! 則是為了移除在 n! 中那些沒被選到的物件排列組合 : 

範例代碼 :
下面使用代碼利用 Recursion 將公式 C(N,K) = C(N-1,K) + C(N-1,K-1) 實作出來, 可以發現函數 CSize() 得到的結果恰為上面公式 :

view plaincopy to clipboardprint?

1. /** 
2. * BD : C(N,K) = C(N-1,K) + C(N-1,K-1) 
3. *      1. You can treat C(N-1,K-1) -> Specific one is chosen from collection . So K-1 left. from N-1 collection 
4. *      2. You can treat C(N-1,K) -> The item 1 has specific one being chosen.  
5. *         This item is the combination which not including that specific one.   
6. * @param col : The collection with size . 
7. * @param K : The number to pickup from collection . 
8. * @return The size of array of combination of pickup items from collection size= C(N,K). 
9. */  
10. public static int CSize(int N, int K)  
11. {  
12.     if(Nreturn -1; // The collection size should not smaller than .  
13.     else if(N==K) return 1; // If the collection size equals means only one possibility.  
14.     else if(K==0 || N==0) return 1; // If either collection size=0 or K=0, return 1 as defined by question.  
15.     else // If the collection size larger than , fit in the equation : C(N,K)=C(N-1,K) + C(N-1,K-1)  
16.     {  
17.         return CSize(N-1,K)+CSize(N-1,K-1);  
18.     }  
19. }  

接著下面函數 C(int N, int K) 會幫我們從 Collection {1,2,...N} 取出 K 個 Items 中所有可能的 Combination (不考慮順序) :

view plaincopy to clipboardprint?

1. /** 
2. * BD : Return all possible combination of C(N,K). 
3. *      The collection is {1,2,...,N}. 
4. * @param N : The size of collection. 
5. * @param K : K items will be pickup.  
6. * @return The all possible combination of K items from collection. 
7. */  
8. public static Set> C(int N, int K)  
9. {  
10.     Set col = new HashSet();  
11.     for(int i=1; i<=N; i++) col.add(i);  
12.     return C(col, K);  
13. }  
14.   
15. public static Set> C(Set col, int K){  
16.     Set> comb = new HashSet>();  
17.     // Remove duplicate items with different order. 321=123=231 etc.  
18.     return _C(col, "", comb, K);  
19. }  
20.   
21. protected static Set _genSet(Set set, int except)  
22. {  
23.     Set newSet = new HashSet();  
24.     for(Integer i:set) if(i!=except) newSet.add(i);  
25.     return newSet;  
26. }  
27.   
28. public static Set> _C(Set curCol, String inSelect, Set> comb, int K)  
29. {         
30.     if(curCol.size()>K)  
31.     {  
32.         for(Integer i:curCol)  
33.         {  
34.             if(inSelect==null) inSelect = "";  
35.             Set subSet = _genSet(curCol, i);  
36.             _C(subSet, inSelect, comb, K);  
37.             _C(subSet, inSelect+i, comb, K-1);  
38.         }  
39.         return comb;  
40.     }  
41.     else if(curCol.size()==K)  
42.     {  
43.         for(int i:curCol) inSelect=inSelect+i;  
44.         Set charSet = new TreeSet();  
45.         for(int i=0;i
46.         comb.add(charSet);  
47.         return comb;  
48.     }  
49.     else  
50.     {  
51.         return comb;  
52.     }  
53. }  

接著我們可以如下執行上面兩個函數 :

view plaincopy to clipboardprint?

1. public static void main(String args[])  
2. {  
3.     int N = 5, K=3;  
4.     System.out.printf("\t[Info] N=%d; K=%d; C(N,K)=%d.\n", N, K, Combinatoric.CSize(N,K));  
5.     Set> colList = Combinatoric.C(N, K);  
6.       
7.     // Sorting the result  
8.     Set combInStr = new TreeSet();  
9.     for(Set chars:colList) {  
10.         StringBuilder sb = new StringBuilder("");  
11.         for(Character c:chars) sb.append(c);  
12.         combInStr.add(sb.toString());  
13.     }  
14.       
15.     // Printout the combinations  
16.     for(String s:combInStr)  
17.     {  
18.         System.out.printf("\t%s\n", s);  
19.     }  
20. }  

並得到執行結果如下 :

[Info] N=5; K=3; C(N,K)=10.
123
124
125
134
135
145
234
235
245
345

[ numpy ] 線代概念 : 行列式 / 伴隨矩陣 / 反矩陣

行列式 : (Determinant) 
行列式 在數學中，是一個函數，其定義域為 nxn 的矩陣A，取值為一個純量，寫作或 det(A) 或 |A|. 對於簡單的2階和3階的矩陣，行列式的表達式相對簡單，而且恰好是每條主對角線（左上至右下）元素乘積之和減去每條副對角線（右上至左下）元素乘積之和（見圖中紅線和藍線）: 
 
 

- 簡單範例 
求下面矩陣之行列式值 det(A) : 
 

答案為 -6, 如果你要使用 numpy 套件來計算, 可以如下: 
 

伴隨矩陣 : (adjugate matrix) 
在線性代數中，一個方形矩陣的伴隨矩陣是一個類似於逆矩陣的概念. 如果矩陣可逆，那麼它的逆矩陣和它的伴隨矩陣之間只差一個係數. 在此之前先來看看了解 伴隨矩陣 需要知道的一些定義. 
- 定義 
考慮 A 是一個以 R 中元素為係數的 n×n 的矩陣. A的伴隨矩陣可按如下步驟定義 (參考至 wiki) : 
 

- 簡單範例 
來看看範例有助理解, 如果是二維矩陣 : 
 

如果是三維矩陣 : 
 

- Numpy 範例 
考慮下面的 adjugate matrix : 
 

使用 numpy 模組, 我們可以先建立一個函數 adjugate() 將傳入參數 matrix 以其對應的 adjugate matrix 回傳 : 

view plaincopy to clipboardprint?

1. def adjugate(matrix):  
2.     import numpy as np  
3.     C = np.zeros(matrix.shape)  # 初始化 Cofactor matrix    
4.     nrows, ncols = C.shape      # 取出 Cofactor matrix 的 row,col  
5.     # Loop to calculate Cofactor  
6.     for row in xrange(nrows):  
7.         for col in xrange(ncols):  
8.             minor = matrix[np.array(range(row)+range(row+1,nrows))[:,np.newaxis],  
9.                            np.array(range(col)+range(col+1,ncols))]  
10.             C[row, col] = (-1)**(row+col) * np.linalg.det(minor)    # 計算 Cij | i=row,j=col  
11.     return C.transpose()  

接著你便可以如下使用上面定義的函數計算 adjugate matrix : 
 

反矩陣 : (Invertible matrix) 
在線性代數中，給定一個 n 階方陣 ，若存在一 n 階方陣，使得 : 
 

則稱 A 是可逆的，且 B 是 A 的逆矩陣，記作 A^-1. 若方陣 A 的逆陣存在，則稱 A 為非奇異方陣或可逆方陣. 並且如果矩陣 A 可逆, 則 : 
 

- 反矩陣之性質 
 

- 簡單範例 
 

- Numpy 範例 
使用 numpy 模組, 可以如下取得某個 matrix 的 inverse matrix : 
 

或者你可以利用 伴隨矩陣 的特性 來求得 反矩陣 : 
 

其他 Numpy 矩陣操作 : 
底下是一些常見 numpy 上提供的 matrix 操作 : 

- n dimension 的 transpose 
你可以透過 numpy.core.defmatrix.matrix 上的方法或屬性取的該 matrix 的 transpose matrix : 
 

或者 ndarray 上也可進行同樣操作 : 
 

補充說明 : 
* Speed up python code for computing matrix cofactors