[ 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