Coeficients binomials P93625


Statement
 

pdf   zip

thehtml

El coeficient binomial o nombre combinatori (

n
k

) és el nombre de maneres de triar k objectes d’un total de n. La seva fórmula és ben coneguda:



n
k


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

on n!=n· (n−1)⋯ 2· 1. Aquesta fórmula no és massa pràctica des d’un punt de vista computacional, perquè s’ha de treballar amb nombres molt grossos (els factorials) per acabar obtenint un resultat molt més petit. Per exemple,



20
10


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

on es pot veure que, tot i que el nombre final només té 6 xifres, ens ha fet falta calcular 20!, que en té 19. Això pot ser un problema, ja que el tipus int de 32 bits no pot emmagatzemar nombres amb més de 10 xifres.

Aquesta, però, no és l’única manera de calcular (

n
k

). Per exemple, els nombres combinatoris satisfan la propietat següent:



n
k


= 



1si k = 0 o k = n


n−1
k−1


+ 


n−1
k


si 0<k<n

Aquesta fórmula recursiva permet calcular els nombres combinatoris sense multiplicacions ni divisions, mitjançant un procediment conegut avui en dia com a “Triangle de Pascal” o “Triangle de Tartaglia”, encara que tingui referències històriques amb més de 1000 anys d’antiguitat:

||
    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
)
        
||

Per calcular més nombres combinatoris només cal omplir més files del triangle. Feu servir aquesta idea per calcular diversos nombres combinatoris.

Entrada

La entrada consisteix en diversos casos, cadascun amb dos naturals n i k, on 0≤ n≤ 30 i 0≤ kn.

Sortida

Per a cada cas, cal escriure (

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
    Catalan
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    English Spanish
    Official solutions
    C++
    User solutions
    C++ Python