Número de soluciones integrales de la ecuación x1 + x2 +…. + xN = k

Dados N y K. La tarea es contar el número de soluciones integrales de una ecuación lineal que tiene N variable como se indica a continuación: 
 

x1 + x2+ x3…+ xN-1+…+xN = K

Ejemplos : 
 

Input: N = 3, K = 3
Output: 10
Explaination: Possible solutions are: (1,1,1),(1,0,2),(2,0,1),(1,2,0),(2,1,0),(0,1,2)
(0,2,1),(3,0,0),(0,3,0),(0,0,3).

Input: N = 2, K = 2
Output: 3

Enfoque: Este problema se puede resolver usando el concepto de Permutación y Combinación. A continuación se encuentran las fórmulas directas para encontrar soluciones integrales positivas y no negativas, respectivamente.
 

¡ El número de soluciones integrales no negativas de la ecuación x1 + x2 + …… + xn = k viene dado por (n+k-1)! / (n-1)!*k!.  
¡ El número de soluciones integrales positivas de la ecuación x1 + x2 + ….. + xn = k viene dado por (k-1)! / (n-1)! * (kn)!. 
 

Tenga en cuenta aquí que las soluciones integrales no negativas ya incluyen las soluciones integrales positivas. Por lo tanto, no hay necesidad de sumar el número de soluciones integrales positivas a la respuesta.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ program for above implementation
#include<iostream>
 
using namespace std ;
 
int nCr(int n, int r)
{
    int fac[100] = {1} ;
     
    for (int i = 1 ; i < n + 1 ; i++)
    {
        fac[i] = fac[i - 1] * i ;
    }
     
    int ans = fac[n] / (fac[n - r] *
                        fac[r]) ;
    return ans ;
}
 
// Driver Code
int main()
{
    int n = 3 ;
    int k = 3 ;
     
    int ans = nCr(n + k - 1 , k);
    cout << ans ;
     
    return 0 ;
}
 
// This code is contributed
// by ANKITRAI1

// Java program for above implementation
import java.io.*;
 
class GFG
{
static int nCr(int n, int r)
{
    int fac[] = new int[100] ;
    for(int i = 0; i < n; i++)
    fac[i] = 1;
     
    for (int i = 1 ; i < n + 1 ; i++)
    {
        fac[i] = fac[i - 1] * i ;
    }
     
    int ans = fac[n] / (fac[n - r] *
                        fac[r]);
    return ans ;
}
 
// Driver Code
public static void main (String[] args)
{
    int n = 3 ;
    int k = 3 ;
     
    int ans = nCr(n + k - 1 , k);
     
    System.out.println(ans) ;
}
}
 
// This code is contributed
// by anuj_67

# Python implementation of
# above approach
 
# Calculate nCr i.e binomial
# cofficent nCr = n !/(r !*(n-r)!)
def nCr(n, r):
 
    # first find factorial
    # upto n
    fac = list()
    fac.append(1)
    for i in range(1, n + 1):
        fac.append(fac[i - 1] * i)
 
    # use nCr formula
    ans = fac[n] / (fac[n - r] * fac[r])
    return ans
 
# n = number of variables
n = 3
 
# sum of n variables = k
k = 3
 
# find number of solutions
ans = nCr(n + k - 1, k)
 
print(ans)
 
# This code is contributed
# by ChitraNayal

// C# program for above implementation
using System;
 
class GFG
{
static int nCr(int n, int r)
{
    int[] fac = new int[100] ;
    for(int i = 0; i < n; i++)
    fac[i] = 1;
     
    for (int i = 1 ; i < n + 1 ; i++)
    {
        fac[i] = fac[i - 1] * i ;
    }
     
    int ans = fac[n] / (fac[n - r] *
                        fac[r]);
    return ans ;
}
 
// Driver Code
public static void Main ()
{
    int n = 3 ;
    int k = 3 ;
     
    int ans = nCr(n + k - 1 , k);
     
    Console.Write(ans) ;
}
}
 
// This code is contributed
// by ChitraNayal

<?php
// PHP implementation of above approach
 
// Calculate nCr i.e binomial
// cofficent nCr = n !/(r !*(n-r)!)
function nCr($n, $r)
{
    // first find factorial
    // upto n
    $fac = array();
    array_push($fac, 1);
    for($i = 1; $i < $n + 1; $i++)
        array_push($fac, $fac[$i - 1] * $i);
 
    // use nCr formula
    $ans = $fac[$n] / ($fac[$n - $r] *
                       $fac[$r]);
    return $ans;
}
 
// Driver Code
 
// n = number of variables
$n = 3;
 
// sum of n variables = k
$k = 3;
 
// find number of solutions
$ans = nCr($n + $k - 1, $k);
 
print($ans);
 
// This code is contributed
// by mits
?>

<script>
 
// Javascript program for above implementation
function nCr(n, r)
{
    var fac = Array(100).fill(1);
     
    for (var i = 1 ; i < n + 1 ; i++)
    {
        fac[i] = fac[i - 1] * i ;
    }
     
    var ans = fac[n] / (fac[n - r] *
                        fac[r]) ;
    return ans ;
}
 
// Driver Code
var n = 3 ;
var k = 3 ;
 
var ans = nCr(n + k - 1 , k);
 
document.write(ans );
 
// This code is contributed by noob2000.
</script>

10

Aplicaciones de los conceptos anteriores: 
 

1. El número de soluciones integrales no negativas de la ecuación x1 + x2 +…+ xn = k es igual al número de formas en que k bolas idénticas se pueden distribuir en N cajas únicas.
2. El número de soluciones integrales positivas de la ecuación x1 + x2 + … + xn = k es igual al número de formas en que k bolas idénticas se pueden distribuir en N cajas únicas, de modo que cada caja debe contener al menos 1 bola.