# Binomial coefficient

A combination of $n$ elements taken $k$ at a time is a set of $k$ elements chosen from the given $n$ 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 $5$ elements: ${1,2,3,4,5}$. The sets ${2,1,3}$ and ${3,2,1}$ are identical as combinations (though different as permutations) because they consist of the same elements ${1,2,3}$.

The formula for calculating the number of combinations of $n$ elements taken $k$ at a time is

The numbers $C_{n}$ are called binomial coefficients.

When we choose zero elements from a set of $n$ 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 $n$ balls, and you want to choose $0$ of them. Even if you don’t choose anything, it is still a valid choice. Thus, $C_{n}$ is the number of ways to choose $0$ elements from $n$, which is equal to $1$.

We can think of this as the one and only way to not choose any elements from the set, which gives the result of $1$.

When we choose one element from a set of $n$ elements, we have $n$ options to choose from: we can choose any one of the $n$ elements. For example, if we have a set of numbers from $1$ to $5$ (${1,2,3,4,5}$), we can choose one number from this set, and we have $5$ options for this choice.

The value $C_{n}$ equals $n$ because there are $n$ ways to choose one element from a set of $n$ elements.

When choosing $2$ elements from a set of $n$ 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 $n$ elements.

After choosing the first element, we have $n–1$ 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 $n$ elements is the product of the number of ways to choose the first and second elements: $n⋅(n–1)$.

However, each pair is counted twice, as the order of elements in the pair does not matter. For example, $(p,q)$ and $(q,p)$ are considered the same pair. To account for this, the total number of combinations should be divided by $2$. Therefore, the value $C_{n}$ equals $n⋅(n–1)/2$.

Symmetry rule: $C_{n}=C_{n}$.

The number of ways to choose $k$ elements from $n$ is equal to the number of ways to not choose $(n–k)$ elements from $n$. There are $C_{n}$ ways to not choose $(n–k)$ elements from $n$. Therefore $C_{n}=C_{n}$.

Exercise. Calculate the values of the following binomial coefficients:

1) $C_{5}$ | 3) $C_{5}$ | 5) $C_{8}$ |

2) $C_{8}$ | 4) $C_{7}$ | 6) $C_{8}$ |

Summation formula: $C_{n}=C_{n−1}+C_{n−1}$.

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 $res$ and initialize it with a value of $1$. Then multiply $res$ by $n$ and divide the result by $1$. After that multiply $res$ by $n–1$ and divide by $2$. Continue this process of multiplication and division $k$ times (the numerator and denominator of $C_{n}$ after simplification by $(n–k)!$ contain $k$ 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 $k$ out of $n$ participants in the summer math camp, each of whom will receive kefir? Print the answer modulo $9929$.

Input. Two integers $n$ and $k(0≤k≤n≤500)$.

Output. Print the number of ways modulo $9929$.

6 3

20

The answer to the problem will be the value of $C_{n}mod9929$. Since we need to find the binomial coefficient by modulo, we’ll try to avoid division during calculations. To achieve this, use the relation: $C_{n}=C_{n−1}+C_{n−1},C_{n}=1$.

Since $k≤n≤500$, we use the memoization technique.

Declare the constants and array $cnk$, where $cnk[n][k]=C_{n}mod9929$.

#define MAX 510 #define MOD 9929 int cnk[MAX][MAX];

The c function computes the value of the binomial coefficient $C_{n}mod9929$.

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 $cnk$ 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 $n$, find the sum of binomial coefficients

Input. One non-negative integer $n(n≤60)$.

Output. Print the value of the sum.

2

4

The formula of the binomial theorem is as follows:

If we set $a=b=1$, then this relation takes the following form:

or

Thus, the indicated sum equals $2_{n}$.

Example

If $n=1$, then $C_{1}+C_{1}=1+1=2$

If $n=2$, then $C_{2}+C_{2}+C_{2}=1+2+1=4$

If $n=3$, then $C_{3}+C_{3}+C_{3}+C_{3}=1+3+3+1=8$

Read the input value of $n$.

scanf("%lld", &n);

Compute and print the result, the value of $2_{n}$.

res = 1LL << n; printf("%lld\n", res);

Given a non-negative integer $n$, find the sum of binomial coefficients

Input. One non-negative integer $n(n≤30)$.

Output. Print the value of the sum.

3

20

Let’s consider $2n$ objects $a_{1},...,a_{2n}$ and find the number of ways to select $n$ objects out of $2n$.

We’ll divide the set in half: ${a_{1},a_{2},...,a_{n},a_{n+1},...,a_{2n}}$. To choose $n$ objects from $2n$, we’ll select $k(k≤n)$ objects from the left half (from the set ${a_{1},a_{2},...,a_{n}})$ and $n–k$ objects from the right half (from the set ${a_{n+1},a_{n+2},...,a_{2n}})$. The number of ways to make such a selection, according to the rule of multiplication, is equal to $C_{n}⋅C_{n}=(C_{n})_{2}$. Since $k$ can take values from $0$ to $n$, то $∑_{k=0}(C_{n})_{2}$ is equal to the number of ways to choose $n$ objects from $2n$, which is equal to $C_{2n}$. Thus,

Example

For $n=3$ the answer is $(C_{3})_{2}+(C_{3})_{2}+(C_{3})_{2}+(C_{3})_{2}=1_{2}+3_{2}+3_{2}+1_{2}=20$

At the same time $C_{6}=3!⋅3!6! =64⋅5⋅6 =20$.

The Cnk function computes the value of the binomial coefficient $C_{n}$.

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 $n$.

scanf("%lld", &n);

Compute and print the answer.

res = Cnk(2*n, n); printf("%lld\n", res);

Given the values of $k$ and $n$, find the number of positive integral solutions for the equation

Input. Two positive integers $k$ and $n(k≤n≤100)$.

Output. Print the number of positive integral solutions for the given equation. It is known that the answer is no more than $10_{18}$.

3 4

3

Consider a sequence of $n$ ones: $111...11$. You can insert a ‘$+$’ sign between any two ones. For example, $11+111+1$. Such notation denotes the sum $2+3+1$, where each term represents the number of ones adjacent to each other. The number of positions where a ‘$+$’ sign can be inserted is $n–1$. Since the sum must consist of $k$ terms, $k–1$ ‘$+$’ signs should be inserted.

We should insert $k–1$ pluses in $n–1$ places. This can be done in $C_{n−1}$ ways.

Example

Consider the equation $x_{1}+x_{2}+x_{3}=4$. It has $3$ positive integer solutions:

$(1,1,2)$

$(1,2,1)$

$(2,1,1)$

For example, $n=4$ ones can be divided into $k=3$ terms in $C_{2}=3$ ways:

The Cnk function computes the value of the binomial coefficient $C_{n}$.

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 $C_{n−1}$.

res = Cnk(k - 1, n - 1); printf("%lld\n", res);

Given values of $k$ and $n$, find the number of nonnegative integral solutions for the equation

Input. Two positive integers $k$ and $n(k≤n≤100)$.

Output. Print the number of nonnegative integral solutions for the given equation. It is known that the answer is no more than $10_{18}$.

3 4

15

Consider a sequence of $n+k–1$ positions. In $n$ positions we should place $1$. In $k–1$ positions we should place the '$+$' symbol (to obtain $k$ terms).

Any arrangement of $1$s and '$+$' signs among these positions will correspond to some solution of the given equation. For example, consider some solutions of the equation $x_{1}+x_{2}+x_{3}=4(4$ ones and $2$ plus signs):

We should insert $k–1$ plus signs into $n+k–1$ positions. This can be done in $C_{n+k−1}$ ways.

Example

Consider the equation $x_{1}+x_{2}+x_{3}=4$. Its solutions are:

$(4,0,0)$ and its $3$ permutations;

$(3,1,0)$ and its $6$ permutations;

$(2,2,0)$ and its $3$ permutations;

$(2,1,1)$ and its $3$ permutations;

There are $3+6+3+3=15$ solutions.

The Cnk function computes the value of the binomial coefficient $C_{n}$.

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 $C_{n+k−1}$.

res = Cnk(k - 1, n + k - 1); printf("%lld\n", res);

Let $n$ be a non-negative integer. Let

You are given the numbers $n$ and $k$. Calculate $C_{n}$.

Input. The first line contains the number of test cases $t(t≤50)$. Each of the next $t$ lines contains two integers $n$ and $k(0≤n<2_{64},0≤C_{n}<2_{64})$.

Output. Print $t$ lines, each contains the value $C_{n}$ 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 $64$-bit unsigned integers (unsigned long long). Its obvious that

Let’s assign the value of the variable $res$ to $1$. Then multiply it by $in−i+1 $ for all $i$ from $1$ to $k$. Each time the division by $i$ will yield an integer result, but multiplication can cause overflow. Let $d=GCD(res,i)$. Then let’s rewrite the operation

as

In this implementation we’ll avoid overflow (the answer is $64$-bit unsigned integer). Note that first we need to perform the division $(n–i+1)/(i/d)$, and then multiply $res/d$ by the resulting quotient.

To compute $C_{n}$, we must run $k$ iterations. But what to do if we want to compute $C_{2000000000}$? The answer is no more than $2_{64}$, so such input values are possible. As long as $C_{n}=C_{n}$, then for $n–k<k$ we should assign $k=n–k$.

Example

Consider the next sample:

Let $res=15$, and we need to make a multiplication $res⋅34 =15∗34 $. Compute $d=GCD(15,3)=3$. So $15⋅34 =(15/3)⋅3/34 =5⋅14 =20$.

The gcd function computes the greatest common divisor of $a$ and $b$.

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 $C_{n}$.

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 $n$. Find the value of the next sum

Input. One positive integer $n(n≤30)$.

Output. Print the sum value.

3

20

Rewrite the sum in the form:

The sum in parentheses is $2_{n}$. If in Newton’s binomial formula

we set $a=b=1$, then we get the relation: $(1+1)_{n}=∑_{i=0}C_{n}1_{i}1_{n−i}$, or

Let’s compute the remaining sum:

So the answer is $2_{n}+n⋅2_{n−1}=(n+2)⋅2_{n−1}$.

Example

Compute the value for $n=3$. For direct calculation:

When calculated using the formula: $5⋅2_{2}=20$.

Read the input value of $n$.

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: $dp[n][k]=C_{n}$.

int dp[31][31];

The Cnk function computes the value of the binomial coefficient $C_{n}$.

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 $n$.

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 $n⋅m$ 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:

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 $n$ and $m$.

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 $64$-bit signed integer.

3 4

35

1 1

2

The required path is a broken line consisting of $n+m$ links. Of these, $n$ links must be vertical, and the rest must be horizontal. The number of ways to choose $n$ vertical links out $n+m$ is equal to $C_{n+m}$.

Example

For the first test case $n=3,m=4$. The answer is $C_{7}=3!⋅4!7! =1⋅2⋅37⋅6⋅5 =35$.

For the second test case $n=1,m=1$. The answer is $C_{2}=1!⋅1!2! =2$.

The Cnk function computes the value of the binomial coefficient $C_{n}$.

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 $C_{n+m}$.

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 $C_{n}$ is a number defined by

where $n$ and $k$ are non-negative integers.

Gunnar uses his program to calculate $C_{n}$ and obtains a number $m$ as a result. Unfortunately, being forgetful, he forgot the numbers of $n$ and $k$ 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 $n$ and $k$ from the obtained answer. Can you help him find all possible values?

Input. The first line contains the number of test cases, at most $100$. Each test is given in a single line and contains an integer $m(2≤m≤10_{15})$ — 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 $m$ using the binomial coefficient. The second line should contain all pairs $(n,k)$ such that $C_{n}=m$. Pairs should be sorted in increasing order of $n$, and in case of equality, in increasing order of $k$. 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 $C_{n}=m$, then $C_{n}=m$. It is sufficient to find the solution for $k≤n/2$ and, along with the pair $(k,n)$, also print the pair $(k,n–k)$. For $k=n/2$ these two pairs coincide.

Let $p$ be the smallest number for which $C_{2p}>m$. Then it is obvious that $0≤k<p$.

Choose $k$ such that $C_{2k}≤m$ and consider the function $f(n)=C_{n}$. Then for $2k≤n≤m$, the function $f(n)$ is monotonically increasing. Therefore, you can solve the equation $f(n)=m$ by binary search.

To solve the problem, one should iterate over the values of $k(0≤k<p)$, and for each such $k$, solve the equation $C_{n}=m$ relatively $n$ with binary search. The found value of $n$ must be an integer.

Example

Consider the equation $C_{n}=3003$. Given that $C_{12}=924$ and $C_{14}=3432$, it is sufficient to iterate over $0≤k≤6$.

Let $k=2$, consider the equation $C_{n}=3003$ or $2n⋅(n−1) =3003$, $n⋅(n–1)=6006$. By binary search in the interval $4≤n≤3003$, we find an integer solution $n=78$. Since $n=2⋅k$, we have two solutions: $C_{78}=C_{78}=3003$.

Store the required pairs in the vector of pairs $res$.

vector<pair<long long,long long> > res;

The Cnk function computes the value of binomial coefficient $C_{n}$.

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 $m$ (we are searching for a solution to the equation $C_{n}=m$), 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 $k$ from $0$ until $C_{2k}≤m$.

for(k = 0; Cnk(2*k,k) <= m; k++) {

Find the value of $n(2k≤n≤m)$ 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 $C_{lo}=m$, 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. $C_{2n}<4_{n}$. Follows from the fact that $∑_{k=0}C_{2n}=(1+1)_{2n}=2_{2n}=4_{n}$

Theorem 3. $C_{2n}>2n+14_{n} $. Follows from the fact that $∑_{k=0}C_{2n}=4_{n}$, and the number of coefficients is $2n+1$. Therefore, the largest of the coefficients will be greater than $2n+14_{n} $.

Theorem 4. Stirling formula. $n!≈2πn (en )_{n}$.

A more accurate approximation is:

Theorem 5.

Theorem 6.