組合數公式(組合數怎么計算？)

組合數怎樣盤算？

組合數是指從 n 個不同元素中，任取 m (m≤n) 個元素并成一組，叫作從 n 個不同元素中取出 m 個元素的一個組合；從 n 個不同元素中取出 m (m≤n) 個元素的一切組合的個數，叫作 n 個不同元素中取出 m 個元素的組合數1。用標記 C (n,m) 表現。

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

那么怎樣盤算 C (n,m) 呢？有以下幾種辦法：

• 使用公式法

依據分列數和組合數之間的干系，可以取得以下公式1：

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

此中 A (n,m) 表現從 n 個不同元素中取出 m 個元素的分列數，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

這種辦法比力簡便直接，但是當 n 和 m 很大時，階乘運算會很繁復。

• 使用遞推法

依據楊輝三角形（帕斯卡三角形）的實質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 … 以此類推

這種辦法可以制止階乘運算，但是必要存儲前方盤算過的后果。

• 使用編程言語

假如使用編程言語來完成盤算組合數，可以使用以上兩種辦法大概其他優化算法。比如，在 Python 中：

# 辦法一：使用 math 模塊提供的階乘函數 import math def comb_1(n,m):     return math.factorial(n)//(math.factorial(m)*math.factorial(n-m)) # 辦法二：使用遞歸函數和緩存裝飾器 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)