极客笔记C++ 求和 r 和第r个二项式系数的乘积 (r * nCr)
问题声明我们必须确定 r 和第r个二项式系数的乘积 (r * nCr) 的总和。
在二项式定理中，正数系数被称为二项式系数。可以使用帕斯卡三角形和直接公式来确定二项式系数。
二项式系数的公式如下：
\mathrm{n_{c_{r}}=\frac{n!}{(n-r)!r!}}
注意：0! 的值总是等于1。
在这个方程中，n和r可以是任何非负整数，r不应大于n。
这个问题的目标是计算r和第r个二项式系数的乘积，并确定用户输入的任何正数n中，从r=0到r=n的所有乘积的总和。
让我们通过一些示例来说明这个问题：
输入
N=5
输出结果
80
解释：我们计算了所有的r和rth二项系数的乘积，并将它们相加以获得输出。其中r的值从0到N（即r>=0且r=N）。
对于r=0，0 * \mathrm{^5{C_{0}} = 0}，使用上述公式计算\mathrm{^5{C_{0}}}的值。
对于r=1，1 * \mathrm{^5{C_{1}} = 5}。
对于r=2，2 * \mathrm{^5{C_{2}} = 20}，因为\mathrm{^5{C_{2}} = 10}。
对于r=3，3 * \mathrm{^5{C_{3}} = 30}。
对于r=4，4 * \mathrm{^5{C_{4}} = 20}。
对于r=5，5 * \mathrm{^5{C_{5}} = 5}。
r=0到r=5的二项系数及其相应的乘积r和rth均在上面列出。我们期望的输出是0+5+20+30+20+5=80，即r和rth二项系数的乘积的和。
输入
N=4
输出
32
解释：对于范围为[0,4]的所有r的值，r和rth二项式系数乘积的和为，
\mathrm{\sum(r*^N{C_{r}})} 对于所有满足 r >= 0 且 r <= N。
\mathrm{\sum(r_^N{C_{r}})=0_^4{C_{0}}+1_^4{C_{1}}+2_^4{C_{2}}+3_^4{C_{3}}+4_^4{C_{4}}}
\mathrm{= 0 + 4 + 12 + 12 + 4 = 32}
让我们来看看解决这个问题的方法。
方法一（帕斯卡三角形）
使用帕斯卡三角形解决这个问题的思路是获取所有所需二项式系数的值。正如我们所知，帕斯卡三角形描绘了二项式系数的值。帕斯卡三角形如下所示：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
这个三角形可以用相同的逻辑进一步展开。Pascal三角形中的每个值代表组合系数，从n=0开始作为行数，每个行数中的每个值代表\mathrm{n_{c_{r}}}，其中r的范围从r=0到r=n。
我们将创建一个大小为(N+1)*(N+1)的矩阵，其中N是输入中给定的任何正数，并在其中存储Pascal三角形的值。使用动态规划将Pascal三角形的值存储在矩阵中可以使过程变得简单。
如何将Pascal三角形的值存储在矩阵中？
对于第一行，我们将在matrix[0][0]存储1，因为\mathrm{0_{c_{0}}=1}。对于i=0的其余列，我们将存储0，因为在表达式\mathrm{^n{C_{r}}}中r永远不会大于n。
对于每个i>0的值，在matrix[i][0]处存储1，因为\mathrm{^n{C_{0}}}始终等于1。
数学中有一个关于组合系数的关系，它说明\mathrm{^n{C_{r}}=^{n-1}{C_{r-1}}+^{n-1}{C_{r}}}。对于每个i和j的值，其中0
通过这种方式，我们可以用Pascal三角形的值填充矩阵，其中matrix[i][j]将代表\mathrm{^i{C_{j}}}的值。
我们可以使用矩阵来计算r和第r个组合系数的乘积之和。
要使用此方法解决问题，我们必须按以下步骤操作：
- 声明一个大小为
(N+1)*(N+1)的矩阵，用于存储Pascal三角形的值。 -
我们将使用上述方法创建一个函数，在矩阵中存储Pascal三角形的值。
-
一旦将值存储在矩阵中，我们可以通过在for循环中迭代来简单地获得r和第r个组合系数的乘积之和。
-
在for循环中从i=0到i<=N进行迭代，并将每个i和第i个组合系数的乘积添加到变量sum中。
-
变量sum中存储的值将是我们的输出。
此方法的C++代码如下：
示例
// 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和rth二项式系数乘积之和，其中r的范围为[0, N]。我们将推导一个计算该和的公式。
r和rth二项式系数乘积之和可以表示为：
\mathrm{\sum(r*^n{C_{r}})}对于所有满足r≥0且r≤N的r
因此，我们需要找到
\mathrm{\sum(r*^n{C_{r}})}
我们可以将r写成\mathrm{r_{C_{1}}}，因为\mathrm{n_{C_{r}}}始终等于n，
\mathrm{\sum(^r{C_{1}}*^n{C_{r}} )}
使用公式\mathrm{^n{C_{r}}=\frac{n!}{(n-r)!r!}}，我们可以将上述表达式写成，
\mathrm{\sum(\frac{r!}{(r-1)!1!}_\frac{N!}{(N-r)!r!})=\sum(\frac{N!}{(N-r)!(r-1)!})=\sum N_(\frac{(N-1)!}{(N-r)!(r-1)!})}
由于\mathrm{{n-1}_{c_{r-1}}=\frac{(N-1)!}{(N-1-(r-1))!(r-1)!}}，经过化简后可以写成\mathrm{\frac{(N-1)!}{(N-r)!(r-1)!}}
因此，将\mathrm{\frac{(N-1)!}{(N-r)!(r-1)!}}代替\mathrm{{n-1}_{C_{r-1}}}，表达式将变为
\mathrm{N_\sum({n-1}_{C_{r-1}})=N_2^{N-1}(as \sum n_{c_{r}}=2^{N}, where 0<=r <=N)}
使用公式\mathrm{N*2^{N-1}}可以计算r和rth二项式系数乘积之和，其中N为正值。可以使用C++中的pow()函数计算该表达式的值。
语法
int a=pow(2,N);
这将返回等于\mathrm{2^{N}}的值给a。
问题的C++代码使用的是直接公式：
示例
#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)，因为我们没有使用任何额外的空间。
结论
本文讨论了使用两种不同方法利用几个C++函数和库来计算C++中r和rth二项式系数之和的主题。通过建立计算输出的公式，我们能够将问题的暴力解法转化为一种有效的方法。
阅读本文之后，希望您对这个问题有了较好的理解。