Binomial coefficients P93625


Statement
 

pdf   zip

thehtml

The binomial coefficient or choose function (

n
k

) is the number of ways to choose k objects from n objects. Its formula is well known:



n
k


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

where n!=n· (n−1)⋯ 2· 1. This formula is not very useful from a computational point of view, because we have to deal with huge numbers (the factorial numbers) to obtain much smaller results. For instance,



20
10


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

Despite the fact that the final number has only 6 digits, we need to compute 20!, which has 19 digits. This can be a problem because the type int of 32 bits cannot store numbers with more than 10 digits.

However, this is not the only way to compute (

n
k

). For instance, binomial coefficients satisfy the following property:



n
k


= 



1if k = 0 or k = n


n−1
k−1


+ 


n−1
k


if 0<k<n

This recursive formula allow us to compute binomial coefficients with no multiplications nor divisions, by using a procedure known nowadays as “Pascal’s triangle” or “Tartaglia’s triangle”, although it has historical references more than 1000 years old:

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

To compute more binomial coefficients, you only have to fill more rows of the triangle. Use this idea to compute the value of several binomial coefficients.

Input

Input consists of several cases, each with two natural numbers n and k, where 0≤ n≤ 30 and 0≤ kn.

Output

For each case, print (

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