Binomial coefficients X29864
The binomial coefficient (N k), 0≤ k≤ N, is an important concept in mathematics. Formally, (N k) represents the number of ways to choose a subset of k elements from a set of N elements. For example, there are three ways to choose a subset of 2 elements from a set {a,b,c} of three elements, namely {a,b}, {a,c} and {b,c}. Hence (3 2) = 3.
To compute (N k), it is convenient to use the following recursive formula:
| (N k) = (N−1 k−1) + (N−1 k). |
The base case given by (N 0)=(N N)=1 for any N≥ 0.
The binomial coefficients can be arranged into Pascal’s triangle:
| 1 | ||||||||||||
| 1 | 1 | |||||||||||
| 1 | 2 | 1 | ||||||||||
| 1 | 3 | 3 | 1 | |||||||||
| 1 | 4 | 6 | 4 | 1 | ||||||||
| 1 | 5 | 10 | 10 | 5 | 1 | |||||||
| 1 | 6 | 15 | 20 | 15 | 6 | 1 |
Each row N≥ 0 contains the binomial coefficients (N 0),…,(N N), and each element is the sum of the two elements immediately above it.
Input
The input starts with an integer C, the number of cases. On each of the following C lines are two integers N and k satisfying 0≤ k≤ N≤ 20.
Output
For each case, output the binomial coefficient (N k) on a single line.
Input
4 0 0 3 2 4 4 6 2
Output
1 3 1 15
- Author
- Anders Jonsson
- Language
- English
- Official solutions
- C++
- User solutions
- C++