html
The binomial coefficient or choose function (
)
is the number of ways to choose k objects from n objects.
Its formula is well known:
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,
| = | | = | | 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 (
).
For instance, binomial coefficients satisfy the following
property:
| = | ⎧
⎪
⎨
⎪
⎩ | | 1 | if k = 0 or k = n |
| 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 |
| | | | | … | | | | |
||
||
| | | | | () | | | | |
| | | | () | | () | | | |
| | | () | | () | | () | | |
| | () | | () | | () | | () | |
| () | | () | | () | | () | | () |
| | | | | … | | | | |
||
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≤ k≤ n.
Output
For each case, print (
).