C++ 连续二项式系数的乘积之和

问题的陈述包括打印任意正整数N的连续二项式系数的乘积之和，N将由用户输入。

二项式展开中的正系数被称为二项式系数。这些二项式系数可以使用帕斯卡三角形或直接公式来计算。计算二项式系数的公式为：

\mathrm{^nC_{r}=\frac{n!}{(n-r)!r!}}

其中，n和r可以是任意正数，且r不应大于n。

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

在这个问题中，我们将给出一个正整数N，我们的任务是找出连续二项式系数的乘积之和，即
\mathrm{\mathrm{^{i=N-1}{\sum_{i=0}}(^NC_{i}*^NC_{i+1})}}

让我们通过几个例子来理解这个问题。

示例

输入

N=4

输出

56

解释 - 这里我们给出N=4，我们需要求连续二项式系数的乘积之和，即\mathrm{^{i=N-1}{\sum_{i=0}}(^NC_{i}*^NC_{i+1})}

对于N=4，

\mathrm{(^4C_{0}*^4C_{1})+(^4C_{1}*^4C_{2})+(^4C_{2}*^4C_{3})+(^4C_{3}*^4C_{4})}

使用公式计算二项式系数的值，我们得到(1*4)+(4*6)+(6*4)+(4*1)=4+24+24+4=56

所以我们要求的输出是56。

输入

N=1

输出

1

解释 − 输入中N的值为1。我们需要找到二项式系数的乘积之和，从i=0到i=N−1，即0。

所以所需的和是，
\mathrm{^{i=N-1}{\sum_{i=0}}(^NC_{i}*^NC_{i+1})=(^1C_{0}*^1C_{1})=1*1=1}

让我们了解一下找到任意N的连续二项式系数乘积之和的算法。

算法

如果我们为每种情况计算二项式系数的值，然后找到连续二项式系数的乘积之和，这个过程可能会非常冗长。

我们将使用帕斯卡三角形的概念来计算正数N的二项式系数的值，这将作为输入给出。

帕斯卡三角形是一个三角形数组，三角形中的每个值表示二项式系数的值。帕斯卡三角形可以如下所示：

1
                            1        1
                        1        2        1
                      1      3         3       1
                   1     4       6        4        1  
                1     5     10       10        5       1

使用相同的逻辑，可以进一步扩展帕斯卡三角形，直到无穷。帕斯卡三角形中的每个数字表示二项式系数的值，其中每一行代表n（从0开始），每一列代表r（从0开始），在公式\mathrm{^nC_{r}}中。

我们将创建一个大小为(N+1)*(N+1)的二维矩阵，用于存储二项式系数的值，其中N是输入中给定的正数。为了在二维矩阵中存储帕斯卡三角形的值，我们将使用动态规划的概念。

以下步骤是存储帕斯卡三角形值的指南：

• 我们将在mat[0][0]处存储1，因为\mathrm{^0C_{0}}等于1。对于第一行剩余列的索引，我们将将值保持为0，因为在公式\mathrm{^nC_{r}}中，r永远不会大于n。

• 从i=1到i<N+1的for循环中进行迭代，因为我们需要N的二项式系数的值。

• 我们将用每次迭代中的1来更新mat[i][0]，因为\mathrm{^nC_{0}}总是等于1。

• 现在，我们将对每个i的值从j=1到j<N+1进行嵌套的for循环迭代，以计算二项式系数的值\mathrm{^nC_{r}}，其中r的范围从0到n。

• 二项式系数之间存在一个关系，可以表示为\mathrm{^nC_{r}=^{n-1}C_{r-1}+^{n-1}C_{r}}。对于每个i和j的值，其中0<i,j<N+1，并且i表示二项式系数中的n，j表示r，mat[i][j]的值将等于mat[i−1][j−1]+mat[i−1][j]。

• 我们可以以这种方式更新帕斯卡三角形，直到N。

一旦我们获得了帕斯卡三角形，我们可以简单地取所需的二项式系数的值来找到连续二项式系数乘积的和。

连续二项式系数乘积的和可以表示为\mathrm{^{i=N-1}{\sum_{i=0}}(^NC_{i}*^NC_{i+1})}。因此，为了找到和，我们可以在一个for循环中从i=0到i<N进行迭代，因为i的范围从0到N−1，并计算mat[N][i]*mat[N][i+1]的乘积，并将其加入总和中，这将给出我们需要的结果。

我们将根据上述算法来实现我们的方法，以解决找到连续二项式系数乘积和的问题。

方法

以下是我们可以实施上述算法以找到连续二项式系数乘积和的方法：

• 为了找到和，我们将创建一个函数。

• 我们将创建一个大小为(N+1)*(N+1)的2-D向量，用于存储Pascal三角形的值。

• 在函数中，我们将根据算法中讨论的步骤更新2-D向量的值。

• 一旦向量更新，我们将再次迭代一个for循环，计算从i=0到\mathrm{i<N(^{i=N-1}{\sum_{i=0}}(^NC_{i}*^NC_{i+1}))}的二项式系数的乘积。

• 我们将通过mat[N][i]*mat[N][i+1]更新二项式系数的乘积和。

• 我们将返回作为输出的变量，这是所需的和。

示例

// C++ code for calculating sum of product of consecutive binomial 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+1;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=18;

    vector<vector<long long int>> mat(N+1,vector<long long int>(N+1,0));  
     //initialise a 2d vector to store values of pascal triangle

    pascaltriangle(N,mat); //calling the function to update values in vector

   long long int ans=0; //variable to store sum of product of consecutive binomial coefficients
    for(int i=0;i<N;i++){
        ans = ans + (mat[N][i]*mat[N][i+1]); // (NCi*NCi+1) for i>=0 and i<=N-1
    }

    cout<<"The sum of product of consecutive binomial coefficients for N is : "<<ans<<endl;

    return 0;
}

输出

The sum of product of consecutive binomial coefficients for N is :       8597496600

时间复杂度 - O(N^2)，其中N是输入，因为我们在嵌套循环中迭代，更新大小为(N+1)*(N+1)的2D向量的值。

空间复杂度 - O(N^2)，因为我们创建了一个大小为(N+1)*(N+1)的二维矩阵来存储杨辉三角形的值。

总结

本文讨论了对于任何正数N打印连续二项式系数之和的问题。我们在方法中使用了杨辉三角的概念，找到了N的所有二项式系数的值，即\mathrm{^NC_{r}}，其中r的范围从0到N，并计算连续二项式系数的乘积并求和。

我希望您在阅读本文之后能理解我们用C++解决这个问题所使用的算法。