二项式系数：定义、实施和使用

介绍

在统计学中，二项式系数主要与分布一起使用。 但是，当应用于计算算法时，它们还有更多的意义。 它们广泛用于统计机器学习和动态规划领域。 关于二项式系数的最基本概念来自二项式分布。 系数用于二项式定理，因此得名。

首先，二项式系数有两个定义。 它们如下：

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 个以上实用的实践顶点项目和顶级公司的工作协助。