Coeficientes Binomiales P93625


Statement
 

pdf   zip

thehtml

El coeficiente binomial o número combinatorio (

n
k

) es el número de maneras de escoger k objectos de un total de n. Su fórmula es bien conocida:



n
k


= 
n! 
k! (nk)! 
 ⁠ ⁠ ,

donde n!=n· (n−1)⋯ 2· 1. Esta fórmula no es demasiado práctica desde un punto de vista computacional, porque se tiene que trabajar con números muy grandes (los factoriales) para acabar obteniendo un resultado mucho más pequeño. Por ejemplo,



20
10


= 
 20! 
10! 10!
 = 
2432902008176640000
1316819440000
 = 184756 ⁠ ⁠ ,

donde se puede ver que, pese a que el número final sólo tiene 6 cifras, nos ha hecho falta calcular 20!, que tiene 19. Esto puede ser un problema, puesto que el tipo int de 32 bits no puede almacenar números de más de 10 cifras.

Este, sin embargo, no es el único modo de calcular (

n
k

). Por ejemplo, los números combinatorios satisfacen la propiedad siguiente:



n
k


= 



1si k = 0 o k = n


n−1
k−1


+ 


n−1
k


si 0<k<n

Esta fórmula recursiva permite calcular los números combinatorios sin multiplicaciones ni divisiones, mediante un procedimiento conocido hoy en día como “Triángulo de Pascal” o “Triángulo de Tartaglia”, aunque tenga referencias históricas con más de 1000 años de antigüedad:

||
    1    
   1 1   
  1 2 1  
 1 3 3 1 
1 4 6 1 1
        
||    ||
    (
0
0
)
    
   (
1
0
)
 (
1
1
)
   
  (
2
0
)
 (
2
1
)
 (
2
2
)
  
 (
3
0
)
 (
3
1
)
 (
3
2
)
 (
3
3
)
 
(
4
0
)
 (
4
1
)
 (
4
2
)
 (
4
3
)
 (
4
4
)
        
||

Para calcular más números combinatorios sólo hay que llenar más filas del triángulo. Usad esta idea para calcular diversos números combinatorios.

Entrada

La entrada consiste en diversos casos, cada uno con dos naturales n y k, donde 0≤ n≤ 30 y 0≤ kn.

Salida

Para cada caso, escribid (

n
k

).

Public test cases
  • Input

    0 0
    1 0
    1 1
    2 0
    2 1
    2 2
    

    Output

    1
    1
    1
    1
    2
    1
    
  • Input

    20 10
    30 15
    30 10
    30 20
    30 0
    30 30
    

    Output

    184756
    155117520
    30045015
    30045015
    1
    1
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Other languages
    Catalan English
    Official solutions
    C++
    User solutions
    C++ Python