Suma de coeficientes binomiales

Dado un entero positivo n , la tarea es encontrar la suma del coeficiente binomial, es decir,
ⁿ C ₀ + ⁿ C ₁ + ⁿ C ₂ + ……. + ⁿ C _n-1 + ⁿ C _n
Ejemplos:

Input : n = 4
Output : 16
⁴C₀ + ⁴C₁ + ⁴C₂ + ⁴C₃ + ⁴C₄
= 1 + 4 + 6 + 4 + 1
= 16

Input : n = 5
Output : 32

Método 1 (Fuerza bruta):
La idea es evaluar cada término de coeficiente binomial, es decir, ⁿ C _r , donde 0 <= r <= n y calcular la suma de todos los términos.
A continuación se muestra la implementación de este enfoque:

C++

// CPP Program to find the sum of Binomial
// Coefficient.
#include <bits/stdc++.h>
using namespace std;
 
// Returns value of Binomial Coefficient Sum
int binomialCoeffSum(int n)
{
    int C[n + 1][n + 1];
 
    // Calculate value of Binomial Coefficient
    // in bottom up manner
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= min(i, n); j++) {
            // Base Cases
            if (j == 0 || j == i)
                C[i][j] = 1;
 
            // Calculate value using previously
            // stored values
            else
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
 
    // Calculating the sum.
    int sum = 0;
    for (int i = 0; i <= n; i++)
        sum += C[n][i];
 
    return sum;
}
 
/* Driver program to test above function*/
int main()
{
    int n = 4;
    printf("%d", binomialCoeffSum(n));
    return 0;
}

Java

// Java Program to find the sum
// of Binomial Coefficient.
 
class GFG {
     
    // Returns value of Binomial
    // Coefficient Sum
    static int binomialCoeffSum(int n)
    {
        int C[][] = new int[n + 1][n + 1];
     
        // Calculate value of Binomial
        // Coefficient in bottom up manner
        for (int i = 0; i <= n; i++)
        {
            for (int j = 0; j <= Math.min(i, n); j++)
            {
                // Base Cases
                if (j == 0 || j == i)
                    C[i][j] = 1;
     
                // Calculate value using previously
                // stored values
                else
                    C[i][j] = C[i - 1][j - 1] +
                              C[i - 1][j];
             
                 
            }
        }
     
        // Calculating the sum.
        int sum = 0;
        for (int i = 0; i <= n; i++)
            sum += C[n][i];
     
        return sum;
    }
     
    /* Driver program to test above function*/
    public static void main(String[] args)
    {
        int n = 4;
        System.out.println(binomialCoeffSum(n));
    }
}
 
// This code is contributed by prerna saini.

Python3

# Python  Program to find the sum
# of Binomial Coefficient.
  
import math   
  
# Returns value of Binomial
# Coefficient Sum
def binomialCoeffSum( n):
     
        C = [[0]*(n+2) for i in range(0,n+2)]
      
        # Calculate value of Binomial
        # Coefficient in bottom up manner
        for i in range(0,n+1):
            for j in range(0, min(i, n)+1):
             
                # Base Cases
                if (j == 0 or j == i):
                    C[i][j] = 1
      
                # Calculate value using previously
                # stored values
                else:
                    C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
      
        # Calculating the sum.
        sum = 0
        for i in range(0,n+1):
            sum += C[n][i]
      
        return sum
     
      
# Driver program to test above function
n = 4
print(binomialCoeffSum(n))
 
# This code is contributed by Gitanjali.

C#

// C# program to find the sum
// of Binomial Coefficient.
using System;
 
class GFG {
 
    // Returns value of Binomial
    // Coefficient Sum
    static int binomialCoeffSum(int n)
    {
        int[, ] C = new int[n + 1, n + 1];
 
        // Calculate value of Binomial
        // Coefficient in bottom up manner
        for (int i = 0; i <= n; i++)
        {
            for (int j = 0; j <= Math.Min(i, n); j++)
            {
                // Base Cases
                if (j == 0 || j == i)
                    C[i, j] = 1;
 
                // Calculate value using previously
                // stored values
                else
                    C[i, j] = C[i - 1, j - 1] + C[i - 1, j];
            }
        }
 
        // Calculating the sum.
        int sum = 0;
        for (int i = 0; i <= n; i++)
            sum += C[n, i];
 
        return sum;
    }
 
    /* Driver program to test above function*/
    public static void Main()
    {
        int n = 4;
        Console.WriteLine(binomialCoeffSum(n));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP Program to find the
// sum of Binomial Coefficient.
// Returns value of Binomial
// Coefficient Sum
 
function binomialCoeffSum($n)
{
    $C[$n + 1][$n + 1] = array(0);
 
    // Calculate value of
    // Binomial Coefficient
    // in bottom up manner
    for ($i = 0; $i <= $n; $i++)
    {
        for ($j = 0;
             $j <= min($i, $n); $j++)
        {
            // Base Cases
            if ($j == 0 || $j == $i)
                $C[$i][$j] = 1;
 
            // Calculate value
            // using previously
            // stored values
            else
                $C[$i][$j] = $C[$i - 1][$j - 1] +
                             $C[$i - 1][$j];
        }
    }
 
    // Calculating the sum.
    $sum = 0;
    for ($i = 0; $i <= $n; $i++)
        $sum += $C[$n][$i];
 
    return $sum;
}
 
// Driver Code
$n = 4;
echo binomialCoeffSum($n);
 
// This code is contributed by ajit
?>

Javascript

<script>
 
// JavaScript Program to find the sum
// of Binomial Coefficient.
 
    // Returns value of Binomial
    // Coefficient Sum
    function binomialCoeffSum(n)
    {
        let C = new Array(n + 1);
         
        // Loop to create 2D array using 1D array
        for (var i = 0; i < C.length; i++) {
            C[i] = new Array(2);
        }
       
        // Calculate value of Binomial
        // Coefficient in bottom up manner
        for (let i = 0; i <= n; i++)
        {
            for (let j = 0; j <= Math.min(i, n); j++)
            {
                // Base Cases
                if (j == 0 || j == i)
                    C[i][j] = 1;
       
                // Calculate value using previously
                // stored values
                else
                    C[i][j] = C[i - 1][j - 1] +
                              C[i - 1][j];
               
                   
            }
        }
       
        // Calculating the sum.
        let sum = 0;
        for (let i = 0; i <= n; i++)
            sum += C[n][i];
       
        return sum;
    }
 
// Driver code
         
        let n = 4;
        document.write(binomialCoeffSum(n));
                   
</script>

Producción:

Método 2 (usando la fórmula):

Esto se puede demostrar de 2 maneras.
Primera prueba: uso del principio de inducción.

Para el paso básico, n = 0
LHS = ⁰ C ₀ = (0!)/(0! * 0!) = 1/1 = 1.
RHS= 2 ⁰ = 1.
LHS = RHS
Para el paso de inducción:
Sea k un entero tal que k > 0 y para todo r, 0 <= r <= k, donde r pertenece a números enteros,
la fórmula es verdadera.
Por lo tanto,
^k C ₀ + ^k C ₁ + ^k C ₂ + ……. + ^k C _k-1 + ^k C _k = 2 ^k
Ahora, tenemos que probar para n = k + 1,
^k+1 C ₀ + ^k+1do ₁ + ^k+1 do ₂ + ……. + ^k+1 C _k + ^k+1 C _k+1 = 2 ^k+1
LHS = ^k+1 C ₀ + ^k+1 C ₁ + ^k+1 C ₂ + ……. + ^k+1 C _k + ^k+1 C _k+1
(Usando ⁿ C ₀ = 0 y ⁿ⁺¹ C _r = ⁿ C _r + ⁿ C _r-1 )
= 1 + ^kC ₀ + ^k C ₁ + ^k C ₁ + ^k C ₂ + …… + ^k C _k-1 + ^k C _k + 1
= ^k C ₀ + ^k C ₀ + ^k C ₁ + ^k C ₁ + …… + ^k C _k-1 + ^k C _k-1 + ^k C _k + ^k C _k
= 2 X ∑ ^norteC _r
= 2 X 2 ^k
= 2 ^k+1
= lado derecho

Segunda prueba: usando la expansión del teorema binomial

Estado de expansión binomial,
(x + y) ⁿ = ⁿ C ₀ x ⁿ y ⁰ + ⁿ C ₁ x ^n-1 y ¹ + ⁿ C ₂ x ^n-2 y ² + ……… + ⁿ C _n-1 x ¹ y ^n-1 + ⁿ C _n x ⁰ y ⁿ
Poner x = 1, y = 1
(1 + 1) ⁿ = ⁿ C ₀ 1 ^norte 1 ⁰+ ^norte C ₁ x ^n-1 1 ¹ + ^norte C ₂ 1 ^n-2 1 ² + ……… + _norte^C n _-1 1 ¹ 1 ^n-1 + ^norte C _norte 1 ⁰ 1 norte 2 ^norte = ^norte^C 0 + ⁿ C ₁ + ⁿ C ₂ + ……. + ^norte C _n-1 + ^norte C _norte

A continuación se muestra la implementación de este enfoque:

C++

// CPP Program to find sum of Binomial
// Coefficient.
#include <bits/stdc++.h>
using namespace std;
 
// Returns value of Binomial Coefficient Sum
// which is 2 raised to power n.
int binomialCoeffSum(int n)
{
    return (1 << n);
}
 
/* Driver program to test above function*/
int main()
{
    int n = 4;
    printf("%d", binomialCoeffSum(n));
    return 0;
}

Java

// Java Program to find sum
// of Binomial Coefficient.
import java.io.*;
 
class GFG
{
    // Returns value of Binomial
    // Coefficient Sum which is
    // 2 raised to power n.
    static int binomialCoeffSum(int n)
    {
        return (1 << n);
    }
 
    // Driver Code
    public static void main (String[] args)
    {
        int n = 4;
        System.out.println(binomialCoeffSum(n));
    }
}
 
// This code is contributed
// by akt_mit.

Python3

# Python  Program to find the sum
# of Binomial Coefficient.
  
import math    
# Returns value of Binomial
# Coefficient Sum
def binomialCoeffSum( n):
     
    return (1 << n);
 
# Driver program to test
# above function
n = 4
print(binomialCoeffSum(n))
 
# This code is contributed
# by Gitanjali.

C#

// C# Program to find sum of
// Binomial Coefficient.
using System;
 
class GFG {
 
    // Returns value of Binomial Coefficient Sum
    // which is 2 raised to power n.
    static int binomialCoeffSum(int n)
    {
        return (1 << n);
    }
 
    /* Driver program to test above function*/
    static public void Main()
    {
        int n = 4;
        Console.WriteLine(binomialCoeffSum(n));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP Program to find sum
// of Binomial Coefficient.
 
// Returns value of Binomial
// Coefficient Sum which is
// 2 raised to power n.
function binomialCoeffSum($n)
{
    return (1 << $n);
}
 
// Driver Code
$n = 4;
echo binomialCoeffSum($n);
 
// This code is contributed
// by akt_mit
?>

Javascript

<script>
    // Javascript Program to find sum of Binomial Coefficient.
     
    // Returns value of Binomial Coefficient Sum
    // which is 2 raised to power n.
    function binomialCoeffSum(n)
    {
        return (1 << n);
    }
     
    let n = 4;
      document.write(binomialCoeffSum(n));
     
</script>

Producción:

Publicación traducida automáticamente

Artículo escrito por anuj0503 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

PHP

Javascript

C++

Java

Python3

C#

PHP

Javascript

Deja una respuesta Cancelar la respuesta