Binomial coefficient
A combination of elements taken at a time is a set of elements chosen from the given elements. In this context, sets that differ only in the order of the elements (but not in their composition) are considered identical. It is precisely this property of combinations that distinguishes them from permutations.
For example, consider a set of elements: . The sets and are identical as combinations (though different as permutations) because they consist of the same elements .
The formula for calculating the number of combinations of elements taken at a time is
The numbers are called binomial coefficients.
When we choose zero elements from a set of elements, we are essentially making an “empty” choice. The empty set, in this context, is considered a valid combination. Imagine you have a box with balls, and you want to choose of them. Even if you don’t choose anything, it is still a valid choice. Thus, is the number of ways to choose elements from , which is equal to .
We can think of this as the one and only way to not choose any elements from the set, which gives the result of .
When we choose one element from a set of elements, we have options to choose from: we can choose any one of the elements. For example, if we have a set of numbers from to (), we can choose one number from this set, and we have options for this choice.
The value equals because there are ways to choose one element from a set of elements.
When choosing elements from a set of elements, we form combinations of pairs. To build such a pair, we first choose one element, and then the second.
The first element can be chosen from elements.
After choosing the first element, we have elements left to choose the second element (since we cannot choose the same element again).
Thus, the total number of combinations of pairs of elements that can be chosen from a set of elements is the product of the number of ways to choose the first and second elements: .
However, each pair is counted twice, as the order of elements in the pair does not matter. For example, and are considered the same pair. To account for this, the total number of combinations should be divided by . Therefore, the value equals .
Symmetry rule: .
The number of ways to choose elements from is equal to the number of ways to not choose elements from . There are ways to not choose elements from . Therefore .
Exercise. Calculate the values of the following binomial coefficients:
1) | 3) | 5) |
2) | 4) | 6) |
Summation formula: .
Proof. Let’s calculate the value of the right-hand side of the equation:
To compute the binomial coefficient, you can use the following formula:
Declare a variable and initialize it with a value of . Then multiply by and divide the result by . After that multiply by and divide by . Continue this process of multiplication and division times (the numerator and denominator of after simplification by contain factors).
The Cnk function returns the binomial coefficient using an iterative method.
int Cnk(int n, int k) { int res = 1; for(int i = 1; i <= k; i++) res = res * (n - i + 1) / i; return res; }
The main part of the program. Read the input data.
scanf("%d %d",&n,&k);
Compute and print the answer.
res = Cnk(n,k); printf("%d\n",res);
For the recursive implementation of the binomial coefficient, use the following formula:
The Cnk function returns the binomial coefficient using a recursive method.
int Cnk(int n, int k) { if (n == k) return 1; if (k == 0) return 1; return Cnk(n - 1, k - 1) + Cnk(n - 1, k); }
The main part of the program. Read the input data.
scanf("%d %d",&n,&k);
Compute and print the answer.
res = Cnk(n,k); printf("%d\n",res);
How many ways are there to choose out of participants in the summer math camp, each of whom will receive kefir? Print the answer modulo .
Input. Two integers and .
Output. Print the number of ways modulo .
6 3
20
The answer to the problem will be the value of . Since we need to find the binomial coefficient by modulo, we’ll try to avoid division during calculations. To achieve this, use the relation: .
Since , we use the memoization technique.
Declare the constants and array , where .
#define MAX 510 #define MOD 9929 int cnk[MAX][MAX];
The c function computes the value of the binomial coefficient .
int c(int n, int k) { if (cnk[n][k] > 0) return cnk[n][k]; if (n - k < k) return c(n,n-k); if (!k) return cnk[n][k] = 1; return cnk[n][k] = (c(n-1,k) + c(n-1,k-1)) % MOD; }
The main part of the program. Initialize the array with zeros. Read the input data.
memset(cnk,0,sizeof(cnk)); scanf("%d %d",&n,&k);
Compute and print the answer.
printf("%d\n",c(n,k));
Binomial coefficients appear in Newton’s binomial:
Let’s look at examples:
Given a non-negative integer , find the sum of binomial coefficients
Input. One non-negative integer .
Output. Print the value of the sum.
2
4
The formula of the binomial theorem is as follows:
If we set , then this relation takes the following form:
or
Thus, the indicated sum equals .
Example
If , then
If , then
If , then
Read the input value of .
scanf("%lld", &n);
Compute and print the result, the value of .
res = 1LL << n; printf("%lld\n", res);
Given a non-negative integer , find the sum of binomial coefficients
Input. One non-negative integer .
Output. Print the value of the sum.
3
20
Let’s consider objects and find the number of ways to select objects out of .
We’ll divide the set in half: . To choose objects from , we’ll select objects from the left half (from the set and objects from the right half (from the set . The number of ways to make such a selection, according to the rule of multiplication, is equal to . Since can take values from to , то is equal to the number of ways to choose objects from , which is equal to . Thus,
Example
For the answer is
At the same time .
The Cnk function computes the value of the binomial coefficient .
long long Cnk(long long n, long long k) { long long res = 1; if (k > n - k) k = n - k; for (long long i = 1; i <= k; i++) res = res * (n - i + 1) / i; return res; }
The main part of the program. Read the value of .
scanf("%lld", &n);
Compute and print the answer.
res = Cnk(2*n, n); printf("%lld\n", res);
Given the values of and , find the number of positive integral solutions for the equation
Input. Two positive integers and .
Output. Print the number of positive integral solutions for the given equation. It is known that the answer is no more than .
3 4
3
Consider a sequence of ones: . You can insert a ‘’ sign between any two ones. For example, . Such notation denotes the sum , where each term represents the number of ones adjacent to each other. The number of positions where a ‘’ sign can be inserted is . Since the sum must consist of terms, ‘’ signs should be inserted.
We should insert pluses in places. This can be done in ways.
Example
Consider the equation . It has positive integer solutions:
For example, ones can be divided into terms in ways:
![](https://eolympusercontent.com/images/giccui9p8p54fdl71it9jo0rj8.gif?width=640)
The Cnk function computes the value of the binomial coefficient .
long long Cnk(long long k, long long n) { long long res = 1; if (k > n - k) k = n - k; for (long long i = 1; i <= k; i++) res = res * (n - i + 1) / i; return res; }
The main part of the program. Read the input data.
scanf("%lld %lld", &k, &n);
Compute and print the answer — the value of .
res = Cnk(k - 1, n - 1); printf("%lld\n", res);
Given values of and , find the number of nonnegative integral solutions for the equation
Input. Two positive integers and .
Output. Print the number of nonnegative integral solutions for the given equation. It is known that the answer is no more than .
3 4
15
Consider a sequence of positions. In positions we should place . In positions we should place the '' symbol (to obtain terms).
Any arrangement of s and '' signs among these positions will correspond to some solution of the given equation. For example, consider some solutions of the equation ones and plus signs):
![](https://eolympusercontent.com/images/tr1uv7jbql2p114fj6s5th62a0.gif?width=750)
We should insert plus signs into positions. This can be done in ways.
Example
Consider the equation . Its solutions are:
and its permutations;
and its permutations;
and its permutations;
and its permutations;
There are solutions.
The Cnk function computes the value of the binomial coefficient .
long long Cnk(long long k, long long n) { long long res = 1; if (k > n - k) k = n - k; for (long long i = 1; i <= k; i++) res = res * (n - i + 1) / i; return res; }
The main part of the program. Read the input data.
scanf("%lld %lld", &k, &n);
Compute and print the answer — the value of .
res = Cnk(k - 1, n + k - 1); printf("%lld\n", res);
Let be a non-negative integer. Let
You are given the numbers and . Calculate .
Input. The first line contains the number of test cases . Each of the next lines contains two integers and .
Output. Print lines, each contains the value for corresponding test.
6 0 0 1 0 1 1 2 0 2 1 2 2
1 1 1 1 2 1
Computations will be performed using -bit unsigned integers (unsigned long long). Its obvious that
Let’s assign the value of the variable to . Then multiply it by for all from to . Each time the division by will yield an integer result, but multiplication can cause overflow. Let . Then let’s rewrite the operation
as
In this implementation we’ll avoid overflow (the answer is -bit unsigned integer). Note that first we need to perform the division , and then multiply by the resulting quotient.
To compute , we must run iterations. But what to do if we want to compute ? The answer is no more than , so such input values are possible. As long as , then for we should assign .
Example
Consider the next sample:
Let , and we need to make a multiplication . Compute . So .
The gcd function computes the greatest common divisor of and .
unsigned long long gcd(unsigned long long a, unsigned long long b) { return (!b) ? a : gcd(b,a % b); }
The Cnk function computes the value of the binomial coefficient .
unsigned long long Cnk(unsigned long long n, unsigned long long k) { unsigned long long CnkRes = 1, t, i; if (k > n - k) k = n - k; for(i = 1; i <= k; i++) { t = gcd(CnkRes, i); CnkRes = (CnkRes / t) * ((n - i + 1) / (i / t)); } return CnkRes; }
The main part of the program. Read the input data. Sequentially process the test cases.
scanf("%d",&t); while(t--) { scanf("%llu %llu",&n,&k); res = Cnk(n,k); printf("%llu\n",res); }
Given a positive integer . Find the value of the next sum
Input. One positive integer .
Output. Print the sum value.
3
20
Rewrite the sum in the form:
The sum in parentheses is . If in Newton’s binomial formula
we set , then we get the relation: , or
Let’s compute the remaining sum:
So the answer is .
Example
Compute the value for . For direct calculation:
When calculated using the formula: .
Read the input value of .
scanf("%lld", &n);
Compute and print the answer.
res = (1LL << (n - 1)) * (n + 2); printf("%lld\n", res);
Algorithm realization – function
Declare an array to store the results: .
int dp[31][31];
The Cnk function computes the value of the binomial coefficient .
int Cnk(int n, int k) { if (n == k) return 1; if (k == 0) return 1; if (dp[n][k] != -1) return dp[n][k]; return dp[n][k] = (Cnk(n - 1, k - 1) + Cnk(n - 1, k)) % 9929; }
The main part of the program. Read the input value of .
scanf("%d", &n); memset(dp, -1, sizeof(dp));
Compute the required sum.
res = 0; for (i = 0; i <= n; i++) res += (i + 1) * Cnk(n, i);
Print the answer.
printf("%d\n", res);
You have a piece of paper and you choose a rectangle of size on it. Let’s call this rectangle together with the lines it contains a grid. Starting at the lower left corner of the grid, you move your pencil to the upper right corner, taking care that it stays on the lines and moves only to the right or up. The result is shown on the left:
![](https://static.e-olymp.com/content/80/8021b44b850c456955b17634a2557ab86c47bb3c.gif)
Really a masterpiece, isn’t it? Repeating the procedure one more time, you arrive with the picture shown on the right. Now you wonder: how many different works of art can you produce?
Input. Two positive integers and .
Output. Print the number of different art works that can be generated using the procedure described above. You may safely assume that this number fits into a -bit signed integer.
3 4
35
1 1
2
The required path is a broken line consisting of links. Of these, links must be vertical, and the rest must be horizontal. The number of ways to choose vertical links out is equal to .
Example
For the first test case . The answer is .
For the second test case . The answer is .
The Cnk function computes the value of the binomial coefficient .
long long Cnk(long long n, long long k) { long long res = 1; if (k > n - k) k = n - k; for (long long i = 1; i <= k; i++) res = res * (n - i + 1) / i; return res; }
The main part of the program. Read the input data.
scanf("%lld %lld", &n, &m);
Compute and print the answer .
res = Cnk(n + m, n); printf("%lld\n", res);
Gunnar is quite an elderly and forgetful researcher. Currently, he is writing a paper on security in social networks that involves some combinatorics. He developed a program to calculate binomial coefficients to assist him in verifying some of his calculations.
The binomial coefficient is a number defined by
where and are non-negative integers.
Gunnar uses his program to calculate and obtains a number as a result. Unfortunately, being forgetful, he forgot the numbers of and he used as input. These two numbers were the result of lengthy computations and were written on one of the many sheets scattered across his desk. Instead of searching through the papers, he decided to reconstruct the numbers and from the obtained answer. Can you help him find all possible values?
Input. The first line contains the number of test cases, at most . Each test is given in a single line and contains an integer — the result of the Gunnar’s program.
Output. For each test, print two lines. The first line should contain the number of ways to express using the binomial coefficient. The second line should contain all pairs such that . Pairs should be sorted in increasing order of , and in case of equality, in increasing order of . The output format of pairs is given in the example.
2 2 15
1 (2,1) 4 (6,2) (6,4) (15,1) (15,14)
If , then . It is sufficient to find the solution for and, along with the pair , also print the pair . For these two pairs coincide.
Let be the smallest number for which . Then it is obvious that .
Choose such that and consider the function . Then for , the function is monotonically increasing. Therefore, you can solve the equation by binary search.
To solve the problem, one should iterate over the values of , and for each such , solve the equation relatively with binary search. The found value of must be an integer.
Example
Consider the equation . Given that and , it is sufficient to iterate over .
Let , consider the equation or , . By binary search in the interval , we find an integer solution . Since , we have two solutions: .
Store the required pairs in the vector of pairs .
vector<pair<long long,long long> > res;
The Cnk function computes the value of binomial coefficient .
long long Cnk(long long n, long long k) { long long i, Res = 1; if (k > n - k) k = n - k; for(i = 1; i <= k; i++) {
If at the next iteration the result exceeds (we are searching for a solution to the equation ), then stop computations. Exiting the function at this point avoids overflow.
if (1.0 * Res * (n - i + 1) / i > m) return m + 1; Res = Res * (n - i + 1) / i; } return Res; }
The main part of the program. Read the input data.
scanf("%d",&tests); while (tests--) { res.clear(); scanf("%lld",&m);
Iterate over the values of from until .
for(k = 0; Cnk(2*k,k) <= m; k++) {
Find the value of using binary search.
long long lo = 2*k, hi = m; while (lo < hi) { long long n = (lo + hi) / 2; if (Cnk(n,k) < m) lo = n + 1; else hi = n; }
If , then a solution is found. Include one or two pairs of solutions in the result.
if (Cnk(lo,k) == m) { res.push_back(make_pair(lo,k)); if (lo != 2*k) res.push_back(make_pair(lo,lo - k)); } }
Sort the pairs.
sort(res.begin(),res.end());
Print the answer — the number of found pairs and the pairs themselves.
printf("%d\n",res.size()); for(i = 0; i < res.size(); i++) printf("(%lld,%lld) ", res[i].first,res[i].second); printf("\n"); }
Asymptotic nonations for the Binomial Coefficients
Theorem 1. There exists a relationship between the binomial coefficients:
Theorem 2. . Follows from the fact that
Theorem 3. . Follows from the fact that , and the number of coefficients is . Therefore, the largest of the coefficients will be greater than .
Theorem 4. Stirling formula. .
A more accurate approximation is:
Theorem 5.
Theorem 6.