二項式係數：定義、實施和使用

介紹

在統計學中，二項式係數主要與分佈一起使用。 但是，當應用於計算算法時，它們還有更多的意義。 它們廣泛用於統計機器學習和動態規劃領域。 關於二項式係數的最基本概念來自二項式分佈。 係數用於二項式定理，因此得名。

首先，二項式係數有兩個定義。 它們如下：

1. 尋找組合的二項式係數

二項式係數用於查找從提供的對像池中選擇一定數量的對象的方法數量。 從統計上講，二項式係數可以幫助找到可以從總共 x 個對像中選擇 y 個對象的方式的數量。 來自 x 的 y 元素子集的數量。

公式推導如下：

為了從 x 個對像中選擇 y 個元素子集，二項式係數或可能的組合是 xCy = x! /y！ * (xy)！

當必須從大量對像中計算出可能的組合數量時，這種方法可能非常有用。 但這適用於什麼地方？

例子

想像有一個班級有 15 名學生。 如果你需要選擇一個由 7 名學生組成的團隊進行比賽，你需要找出可能的組合。 使用二項式係數公式，可以很容易地計算出答案。

總組合 = 15！ /7！ *（15-7）！ = 15！ /7！ * 8！

許多其他情況要復雜得多，其中使用了二項式係數。 例如，選擇一個政黨進行選舉，或者更具體地說，是一個辛迪加。 想像有一項法案要通過，而你是執政黨的多數黨鞭子。 您需要決定有哪些選票以及需要多少成員投票支持該法案。 成員必須來自執政黨和反對黨。 可以應用組合算法來找到要從中投票的成員。

閱讀： 13個有趣的數據結構項目想法和初學者主題

2. 分佈的二項式係數

這個定義更加正式和統計。 這意味著找到多項式展開的係數。 簡單來說，二項式係數C(a, b)可以定義為(x+1)^a的分佈形式的x^b的係數。

讓我們通過一個例子來理解這一點。

例子

例如，您需要 (x+1)^2 的多項式展開。 如果我們將其與我們的定義進行比較，我們會得到 a=2 和 b=0,1,2。

通過手動計算，我們知道 (x+1)^2 = x^2 + 2x + 1 的展開。但是，這些係數是如何計算的呢？

讓我們應用這個公式：

x^0 的係數 = C(2,0)

x^1 的係數 = C(2,1)

x^2 的係數 = C(2,2)

因此，展開式可以寫成：C(2,0)x^0 + C(2,1)x^1 + C(2,2)x^2

公式保持不變。 C(a,b) = a! /乙！ * (ab)！

在這裡應用相同的公式，C(2,0) = 2！ /0！ *（2-0）！ = 1

C(2,1) = 2！ / 1！ *（2-1）！ = 2

C(2,2) = 2！ /2！ *（2-2）！ = 1

現在，如果我們在展開式中替換這些值，我們得到 x^2 + 2x + 1。

這是我們需要的確切答案。 由於這是一個較小的擴展，您可能會覺得簡單的乘法方式更好。 但是，如果需要計算 (x+1)^17 的展開形式怎麼辦？

你不可能乘以那麼多倍，這將是一項令人厭煩的工作。 但是，有了二項式係數的概念，工作就變得簡單了。

閱讀： Python 遞歸函數概念：Python 初學者教程

Python 實現

在執行求二項式係數的公式之前，有必要注意幾點。 實現該功能需要兩個部分。 一是子結構，二是重複子結構的功能。

為了遞歸地找到 C(a, b) 的值，我們可以使用以下子結構：

C(a, 0) 和 C(a, a) = 1

C(a, b) = C(a-1, b) + C(a-1, b-1)

使用這兩個公式，可以實現遞歸函數。 請注意，在更高程度的擴展中，許多子結構將被重複。 如果不必要地重複計算，可能會增加計算時間。 因此，為了有效地實現，重要的是維護一個包含所有先前計算的字典。

這種類型的實現具有 O(a*b) 的時間複雜度。 空間複雜度因實現而異，但可以限制為 O(b)。

如果您使用 Python 並且不想自己實現該功能，則可以使用 Python 的庫 SciPy。 SciPy 中的特殊模塊具有函數 binom()。 以下是它的使用方法：

只需輸入 scipy.special.binom(a, b) ，它就會提供相同的值。 例如，scipy.special.binom(4,3)； 將給出輸出 - 4.0

用法

上面已經討論了二項式係數的主要用途。 二項式係數用於分析以及二項式分佈的基礎。 一個鮮為人知的用法是二項式係數表示帕斯卡三角形中的條目。 這些類型的統計原因使得二項式係數有必要理解。

還結帳： Python中的二項式分佈與真實世界的例子

結論

因此，從統計和實施的角度來看，這都是關於二項式係數的。 我們討論了二項式係數的兩個定義，用於組合和計算膨脹係數。 討論了實施策略以及庫實施。

二項式係數還有更多的統計應用，尤其是當它們與分佈一起出現時。 因此，在研究基於統計的高級概念（如核心機器學習和分析算法）之前，了解二項式係數至關重要。

如果您有興趣了解有關機器學習的更多信息，請查看 IIIT-B 和 upGrad 的機器學習和人工智能 PG 文憑，該文憑專為工作專業人士設計，提供 450 多個小時的嚴格培訓、30 多個案例研究和作業、IIIT- B 校友身份、5 個以上實用的實踐頂點項目和頂級公司的工作協助。