組合數(shù)是指從 n 個(gè)不同元素中，任取 m (m≤n) 個(gè)元素并成一組，叫作從 n 個(gè)不同元素中取出 m 個(gè)元素的一個(gè)組合；從 n 個(gè)不同元素中取出 m (m≤n) 個(gè)元素的所有組合的個(gè)數(shù)，叫作 n 個(gè)不同元素中取出 m 個(gè)元素的組合數(shù)1。用符號(hào) C (n,m) 表示。

例如，從 {a,b,c,d} 中任取兩個(gè)元素，可以得到六種組合：{a,b}、{a,c}、{a,d}、{b,c}、{b,d}、{c,d}。所以 C (4,2) = 6。

那么如何計(jì)算 C (n,m) 呢？有以下幾種方法：

• 利用公式法

根據(jù)排列數(shù)和組合數(shù)之間的關(guān)系，可以得到以下公式1：

C (n,m) = A (n,m) / m! = n! / [(n-m)! * m!]

其中 A (n,m) 表示從 n 個(gè)不同元素中取出 m 個(gè)元素的排列數(shù)，n! 表示 n 的階乘（即 n * (n-1) * … * 1），m! 表示 m 的階乘。

例如，C (4,2) = A (4,2) / 2! = [4 * (4-1)] / [(4-2)! * 2!] = 12 / [2 * 2] = 6

這種方法比較簡(jiǎn)單直接，但是當(dāng) n 和 m 很大時(shí)，階乘運(yùn)算會(huì)很復(fù)雜。

• 利用遞推法

根據(jù)楊輝三角形（帕斯卡三角形）的性質(zhì)4，可以得到以下遞推公式：

C (n,m) = C (n-1,m-1) + C (n-1,m)

其中 C(n,0)=C(n,n)=1

例如，

C(0,0)=1 C(1,0)=C(1,1)=1 C(2,0)=C(2,2)=1 C(2,1)=C(1,0)+C(1,1)=2 … 以此類推

這種方法可以避免階乘運(yùn)算，但是需要存儲(chǔ)前面計(jì)算過的結(jié)果。

• 利用編程語言

如果使用編程語言來實(shí)現(xiàn)計(jì)算組合數(shù)，可以利用以上兩種方法或者其他優(yōu)化算法。例如，在 Python 中：

#?方法一：利用?math?模塊提供的階乘函數(shù)
import?math
def?comb_1(n,m):??
??return?math.factorial(n)//(math.factorial(m)*math.factorial(n-m))
#?方法二：利用遞歸函數(shù)和緩存裝飾器
from?functools?import?lru_cache
@lru_cache(maxsize=None)
def?comb_2(n,m):????
????if?m?==?0?or?m?==?n:????????
????return?1
????else:???????
?????return?comb_2(n-1,m-1)+comb_2(n-1,m)