Loading [MathJax]/jax/output/HTML-CSS/jax.js

r 与 r 次二项式系数乘积之和 (r * nCr)

问题要求我们确定 r 与 r 次二项式系数乘积的和 (r*nCr)。

二项式定理中作为系数的正数称为二项式系数。可以使用帕斯卡三角形和一个简单的公式来确定二项式系数。

二项式系数的公式为

ncr=n!(n−r)!r!

注意：0! 的值始终等于 1。

在这个等式中，n 和 r 可以是任何非负整数，并且 r 永远不能大于 n。

这个问题的目标是计算 r 与 r 次二项式系数的乘积，并确定从 r=0 到 r=n 的所有乘积的总和，其中 n 是用户输入的任何正数。

让我们通过几个例子来研究这个问题

输入

N=5

输出

80

解释：我们计算了 r 与 r 次二项式系数的所有乘积，并将它们加起来以获得输出，其中 r 的值范围从 0 到 N（即 r>=0 且 r=N）。

对于 r=0，0 * 5C0=0，使用上面提到的公式计算 5C0 的值。

对于 r=1，1 * 5C1=5。

对于 r=2，2 * 5C2=20，因为 5C2=10。

对于 r=3，3 * 5C3=30。

对于 r=4，4 * 5C4=20。

对于 r=5，5 * 5C5=5。

上面列出了 r=0 到 r=5 的二项式系数及其各自的乘积 r 和 r 次系数。我们需要的输出是 0+5+20+30+20+5=80，这是 r 与 r 次二项式系数乘积之和。

输入

N=4

输出

32

解释：对于范围 [0,4] 内的所有 r 值，r 与 r 次二项式系数乘积之和为：

∑(r∗NCr) 对于所有 r >=0 且 r <=N

∑(r∗NCr)=0∗4C0+1∗4C1+2∗4C2+3∗4C3+4∗4C4

=0+4+12+12+4=32

让我们看看解决这个问题的方法。

方法一（帕斯卡三角形）

使用帕斯卡三角形解决这个问题的思路是得到所有需要的二项式系数的值。众所周知，帕斯卡三角形描绘了二项式系数的值。帕斯卡三角形如下图所示

       1
      1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1

可以使用相同的逻辑进一步扩展这个三角形。帕斯卡三角形中的每个值都代表从 n=0 开始的行中的二项式系数，并且每一行中的每个值都代表 ncr，其中 r 的范围是从 r=0 到 r=n。

我们将创建一个大小为 (N+1)*(N+1) 的矩阵，其中 N 是输入中给出的任何正数，并将帕斯卡三角形的数值存储在其中。使用动态规划将帕斯卡三角形的数值存储在矩阵中可以简化这个过程。

如何在矩阵中存储帕斯卡三角形的数值？

  • 对于第一行，我们将 matrix[0][0] 存储为 1，因为 0c0=1。对于 i=0 的其余列，我们将存储 0，因为在表达式 nCr 中，r 永远不能大于 n。

  • 对于每个 i>0 的值，将 matrix[i][0] 存储为 1，因为 nC0 始终等于 1。

  • 数学中二项式系数存在一个关系，即 nCr=n−1Cr−1+n−1Cr。对于每个 i 和 j 的值，其中 0

通过这种方式，我们可以用帕斯卡三角形的数值填充矩阵，其中 matrix[i][j] 将代表 iCj 的值。

我们可以使用矩阵来计算 r 与 r 次二项式系数乘积之和。

为了使用这种方法来解决问题，我们必须遵循以下步骤

  • 声明一个大小为 (N+1)*(N+1) 的矩阵来存储帕斯卡三角形的数值。

  • 我们将创建一个函数，使用上述方法将帕斯卡三角形的数值存储在矩阵中。

  • 一旦数值存储在矩阵中，我们就可以通过迭代 for 循环来简单地得到 r 与 r 次二项式系数乘积之和。

  • 在 for 循环中从 i=0 迭代到 i<=N，并将每次 i 与 i 次二项式系数的乘积添加到变量 sum 中。

  • 存储在变量 sum 中的值将是我们的输出。

该方法的 C++ 代码为

示例

Open Compiler
// C++ code for calculating sum of product of r and rth binomial coefficients for N
#include <bits/stdc++.h>

using namespace std;

//function to store values of Pascal's triangle in 2d matrix
void pascaltriangle(int N,vector<vector<long long int>>& mat){
   mat[0][0]=1; //C(0,0)=1
   
   for(int i=1;i<=N;i++){ //iterating in matrix to update the values of Pascal's triangle
   
      mat[i][0]=1;  //nC0 is always equal to 1
      
      for(int j=1;j<=i;j++){  //since r can never be greater than n in nCr
         
         mat[i][j] = mat[i-1][j-1] + mat[i-1][j];  //nCr= (n-1)C(r-1) + (n-1)Cr
         
      }
   }
}


int main()
{
   int N=8;
   
   vector<vector<long long int>> mat(N+1,vector<long long int>(N+1,0));  
    //initialise a 2d vector to store values
   
   pascaltriangle(N,mat); //calling the function to update values in mat
   
   long long int sum=0; //variable to store sum of product of r and rth coefficients
   for(int i=0;i<=N;i++){
      sum = sum + (i * mat[N][i]); //mat[N][i] represents value of NCi
   }
   
   cout<<"The sum of product of r and rth binomial coefficients for N is "<<sum<<endl;

   return 0;
}

输出

The sum of product of r and rth binomial coefficients for N is 1024

时间复杂度：O(N^2)

空间复杂度：O(N^2)

方法二（使用直接公式）

我们将使用一个直接公式来计算 r 与 r 次二项式系数乘积之和，其中 r 的范围为 [0,N]。我们将推导出一个公式来计算这个和。

r 与 r 次二项式系数乘积之和可以表示为

$$\mathrm{\sum(r*^n{C_{r}})}$ $对于所有 r>=0 且 r <=N

所以我们需要找到

∑(r∗nCr)

我们可以将 r 写成 rC1，因为 nCr 始终等于 n，

∑(rC1∗nCr)

使用公式 nCr=n!(n−r)!r!，我们可以将上述表达式写成：

∑(r!(r−1)!1!∗N!(N−r)!r!)=∑(N!(N−r)!(r−1)!)=∑N∗((N−1)!(N−r)!(r−1)!)

因为 n−1cr−1=(N−1)!(N−1−(r−1))!(r−1)!，简化后可以写成 (N−1)!(N−r)!(r−1)!

所以用 n−1Cr−1 替换 (N−1)!(N−r)!(r−1)!，表达式将为

N∗∑(n−1Cr−1)=N∗2N−1(因为∑ncr=2N，其中0<=r<=N)

可以使用公式 N∗2N−1 计算 r 与 r 次二项式系数乘积之和，其中 N 为某个正值。可以使用 C++ 中的 pow() 函数计算此表达式的值。

语法

int a=pow(2,N);

这将返回等于 2N 的值给 a。

使用直接公式解决问题的 C++ 代码

示例

Open Compiler
#include<bits/stdc++.h>

using namespace std;

//function to calculate sum of product of r and rth binomial coefficients
long long int sum(int N){
   long long int ans=0; //to store the answer
   
   ans = N * pow(2,(N-1));  //using direct formula derived 
   
   return ans; // return the answer
}

int main()
{
   int N;
   
   N=4;
   cout<<"The sum of product of r and rth binomial coefficients is "<<sum(N)<<endl;
   
   N=15;
   cout<<"The sum of product of r and rth binomial coefficients is "<<sum(N)<<endl;
   

   return 0;
}

输出

The sum of product of r and rth binomial coefficients is 32
The sum of product of r and rth binomial coefficients is 245760

时间复杂度：O(log N)，因为 pow() 函数运行时间复杂度为 O(log N)。

空间复杂度：O(1)，因为我们没有使用任何额外的空间。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

结论

本文使用两种不同的方法，利用多个 C++ 函数和库，讨论了在 C++ 中计算 r 与 r 次二项式系数乘积之和的主题。通过建立计算输出的公式，我们能够将解决问题的暴力方法转换为有效的方法。

阅读完这篇文章后，我希望您对这个问题有了很好的理解。

更新于：2023年8月21日

浏览量：179

启动您的 职业生涯

通过完成课程获得认证

开始学习
广告