Mmedv2 years ago

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}$ \{1, 2, 3, 4, 5\}. The sets ${2, 1, 3}$ \{2, 1, 3\} and ${3, 2, 1}$ \{3, 2, 1\} are identical as combinations (though different as permutations) because they consist of the same elements ${1, 2, 3}$ \{1, 2, 3\}.

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

C_{n}^{k} = \frac{n !}{k ! \cdot ( n - k )!}

C_n^{k} = {n! \over k! \cdot (n - k)!}

The numbers $C_{n}^{k}$ C_n^{k} 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}^{0}$ C_n^{0} 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$ .

C_{n}^{0} = \frac{n !}{0 ! \cdot ( n - 0 )!} = \frac{n !}{1 ! \cdot n !} = 1

C_n^{0} = {n! \over 0! \cdot (n - 0)!} = {n! \over 1! \cdot n!} = 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}$ \{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}^{1}$ C_n^{1} equals $n$ because there are $n$ ways to choose one element from a set of $n$ elements.

C_{n}^{1} = \frac{n !}{1 ! \cdot ( n - 1 )!} = n

C_n^{1} = {n! \over 1! \cdot (n - 1)!} = n

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 \cdot (n - 1)$ n \cdot (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}^{2}$ C_n^{2} equals $n \cdot (n - 1) /2$ n \cdot (n - 1) / 2.

C_{n}^{2} = \frac{n !}{2 ! \cdot ( n - 2 )!} = \frac{n \cdot ( n - 1 )}{2}

C_n^{2} = {n! \over 2! \cdot (n - 2)!} = {n \cdot (n - 1) \over 2}

Symmetry rule: $C_{n}^{k} = C_{n}^{n - k}$ C_n^{k} = C_n^{n - k}.

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}^{n - k}$ C_n^{n - k} ways to not choose $(n - k)$ elements from $n$ . Therefore $C_{n}^{k} = C_{n}^{n - k}$ C_n^{k} = C_n^{n - k}.

Exercise. Calculate the values of the following binomial coefficients:

1) $C_{5}^{2}$ C_5^{2}	3) $C_{5}^{4}$ C_5^{4}	5) $C_{8}^{1}$ C_8^{1}
2) $C_{8}^{3}$ C_8^{3}	4) $C_{7}^{5}$ C_7^{5}	6) $C_{8}^{5}$ C_8^{5}

Summation formula: $C_{n}^{k} = C_{n - 1}^{k - 1} + C_{n - 1}^{k}$ C_n^{k} = C_{n-1}^{k-1} + C_{n-1}^{k}.

Proof. Let’s calculate the value of the right-hand side of the equation:

C_{n - 1}^{k - 1} + C_{n - 1}^{k} = \frac{( n - 1 )!}{( k - 1 )! \cdot ( n - k )!} + \frac{( n - 1 )!}{k ! \cdot ( n - k - 1 )!} =

C_{n-1}^{k-1} + C_{n-1}^{k} = {(n - 1)! \over (k - 1)! \cdot (n - k)!} + {(n - 1)! \over k! \cdot (n - k - 1)!} =

\frac{( n - 1 )! \cdot k + ( n - 1 )! \cdot ( n - k )}{k ! \cdot ( n - k )!} = \frac{( n - 1 )! \cdot ( k + n - k )}{k ! \cdot ( n - k )!} = \frac{n !}{k ! \cdot ( n - k )!} = C_{n}^{k}

{(n - 1)! \cdot k + (n - 1)! \cdot (n - k) \over k! \cdot (n - k)!} = {(n - 1)! \cdot (k + n - k)\over k! \cdot (n - k)!} = {n! \over k! \cdot (n - k)!} = C_n^{k}

Eolymp #3260: How many?

Preparing for the calculus exam, Petya spread out $n$ different cheat sheets in front of himself. They were his salvation, as throughout the entire semester Petya had never bothered to properly study the material. There were so many cheat sheets that they didn’t fit into any pocket. Therefore, Petya decided to calculate the maximum number of cheat sheets he could take with him to the exam. And then the question arose: how many ways are there in total to choose the required number of cheat sheets?

Input. Contains the total number of cheat sheets $n (1 \leq n \leq 12)$ n~(1 \le n \le 12) and the number of cheat sheets $k (0 \leq k \leq n)$ k~(0 \le k \le n) that Peter can take with him.

Output. Print the number of ways to choose $k$ cheat sheets from $n$ .

Open problem

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;
}

C++

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

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

Eolymp #5329. Party

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 \leq k \leq n \leq 500)$ k~(0 \le k \le n \le 500).

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

Open problem

Declare the constants and array $c nk$ , where $c nk [n] [k] = C_{n}^{k} m o d 9929$ cnk[n][k] = C_n^{k}~mod~9929.

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

The c function computes the value of the binomial coefficient $C_{n}^{k} m o d 9929$ C_n^{k}~mod~9929.

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;
}

C++

The main part of the program. Initialize the $c nk$ 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:

(x + y)^{n} = k = 0 \sum n C_{n}^{k} x^{k} y^{n - k}

(x + y)^n = \sum_{k=0}^n C_n^{k}x^{k}y^{n-k}

Let’s look at examples:

(x + y)^{2} = C_{2}^{0} x^{2} y^{0} + C_{2}^{1} x^{1} y^{1} + C_{2}^{2} x^{0} y^{2} = x^{2} + 2 x y + y^{2},

(x + y)^2 = C_2^{0}x^{2}y^{0} + C_2^{1}x^{1}y^{1} + C_2^{2}x^{0}y^{2} = x^2 + 2xy + y^2,

(x + y)^{3} = C_{3}^{0} x^{3} y^{0} + C_{3}^{1} x^{2} y^{1} + C_{3}^{2} x^{1} y^{2} + C_{3}^{3} x^{0} y^{3} = x^{3} + 3 x^{2} y + 3 x y^{2} + y^{3}

(x + y)^3 = C_3^{0}x^{3}y^{0} + C_3^{1}x^{2}y^{1} + C_3^{2}x^{1}y^{2} + C_3^{3}x^{0}y^{3} = x^3 + 3x^2y + 3xy^2 + y^3

Eolymp #9892. C0n + ... + Cnn

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

C_{n}^{0} + C_{n}^{1} + ... + C_{n}^{n}

C_n^{0} + C_n^{1} + ... + C_n^{n}

Input. One non-negative integer $n (n \leq 60)$ n~(n \le 60).

Output. Print the value of the sum.

Open problem

Eolymp #11271. Sum of squares Cnk

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

(C_{n}^{0})^{2} + (C_{n}^{1})^{2} + (C_{n}^{2})^{2} + ... + (C_{n}^{n})^{2}

(C_n^{0})^2 + (C_n^{1})^2 + (C_n^{2})^2 + ... + (C_n^{n})^2

Input. One non-negative integer $n (n \leq 30)$ n~(n \le 30).

Output. Print the value of the sum.

Open problem

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

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;
}

C++

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

Eolymp #11550. x1 + x2 + ... + xk = n

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

x_{1} + x_{2} + ... + x_{k} = n

x_1 + x_2 + ... + x_k = n

Input. Two positive integers $k$ and $n (k \leq n \leq 100)$ n~(k \le n \le 100).

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

Open problem

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

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;
}

C++

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

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

Eolymp #11551. x1+...+xk = n (2)

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

x_{1} + x_{2} + ... + x_{k} = n

x_1 + x_2 + ... + x_k = n

Input. Two positive integers $k$ and $n (k \leq n \leq 100)$ n~(k \le n \le 100).

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

Open problem

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

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;
}

C++

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

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

Eolymp #318. Binomial coefficients 1

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

n! = 1 \cdot 2 \cdot ... \cdot n (0! = 1),

n! = 1 \cdot 2 \cdot ... \cdot n~(0! = 1),

C_{n}^{k} = \frac{n !}{k ! \cdot ( n - k )!} (0 \leq k \leq n)

C_n^{k} = {n! \over k! \cdot (n - k)!} (0 \le k \le n)

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

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

Output. Print $t$ lines, each contains the value $C_{n}^{k}$ C_n^{k} for corresponding test.

Open problem

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}^{k}$ C_n^k.

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;
}

C++

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

C++

Eolymp #11488. Binomial sum

Given a positive integer $n$ . Find the value of the next sum

1 \cdot C_{n}^{0} + 2 \cdot C_{n}^{1} + 3 \cdot C_{n}^{2} + ... + (n + 1) \cdot C_{n}^{n}

1 \cdot C_n^{0} + 2 \cdot C_n^{1} + 3 \cdot C_n^{2} + ... + (n + 1) \cdot C_n^{n}

Input. One positive integer $n (n \leq 30)$ n~(n \le 30).

Output. Print the sum value.

Open problem

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 implementation – function

Declare an array to store the results: $d p [n] [k] = C_{n}^{k}$ dp[n][k] = C_n^k.

int dp[31][31];

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

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;
}

C++

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

Eolymp #10668. Paths on a grid

You have a piece of paper and you choose a rectangle of size $n \cdot m$ n \cdot 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.

Open problem

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

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;
}

C++

The main part of the program. Read the input data.

scanf("%lld %lld", &n, &m);

Compute and print the answer $C_{n + m}^{n}$ C_{n+m}^n.

res = Cnk(n + m, n);
printf("%lld\n", res);

Eolymp #4008. Binomial coefficients

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}^{k}$ C_n^{k} is a number defined by

C_{n}^{k} = \frac{n !}{k ! \cdot ( n - k )!}

C_n^{k} = {n! \over k! \cdot (n - k)!}

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

Gunnar uses his program to calculate $C_{n}^{k}$ C_n^{k} 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 \leq m \leq 1 0^{15})$ m~(2 \le m \le 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}^{k} = m$ C_n^{k} = 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.

Open problem

Store the required pairs in the vector of pairs $r es$ .

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

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

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}^{k} = m$ C_n^k = 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_{2 k}^{k} \leq m$ C_{2k}^k ≤ m.

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

Find the value of $n (2 k \leq n \leq m)$ n~(2k \le n \le 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_{l o}^{k} = m$ C_{lo}^k = 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));
    }
  }

C++

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:

C_{n}^{0} < C_{n}^{1} < ... < C_{n}^{⌊ n /2 ⌋} \geq C_{n}^{⌊ n /2 ⌋ + 1} > ... > C_{n}^{n}

C_n^0 < C_n^1 < ... < C_n^{\lfloor n/2 \rfloor} \ge C_n^{\lfloor n/2 \rfloor + 1} > ... > C_n^n

Theorem 2. $C_{2 n}^{n} < 4^{n}$ C_{2n}^n < 4^n. Follows from the fact that $\sum_{k = 0}^{2 n} C_{2 n}^{k} = (1 + 1)^{2 n} = 2^{2 n} = 4^{n}$ \sum_{k = 0}^{2n} C_{2n}^k = (1 + 1)^{2n} = 2^{2n} = 4^n

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

Theorem 4. Stirling formula. $n! \approx 2 π n (\frac{n}{e})^{n}$ n! ≈ \sqrt{2 \pi n}\left({n \over e} \right) ^ n.

A more accurate approximation is:

n! \approx 2 π n (\frac{n}{e})^{n} (1 + \frac{1}{12 n} + \frac{1}{288 n ^{2}} - \frac{139}{51849 n ^{3}} - \frac{571}{2488320 n ^{4}})

n! ≈ \sqrt{2 \pi n} \left({n \over e} \right) ^ n \left( 1 + {1 \over 12n} + {1 \over 288n^2} - {139 \over 51849n^3} - {571 \over 2488320n^4} \right)

Theorem 5.

C_{2 n}^{n} \approx \frac{4 π n ( \frac{2 n}{e} ) ^{2 n}}{( 2 π n ( \frac{n}{e} ) ^{n} ) ^{2}} = \frac{4 ^{n}}{π n}

C_{2n}^n ≈ {\sqrt{4 \pi n}\left({2n \over e} \right) ^ {2n} \over \left( \sqrt{2 \pi n}\left({n \over e} \right) ^ n \right) ^2} = {4^n \over \sqrt{\pi n}}

Theorem 6.

C_{n}^{k} = \frac{n !}{k ! ( n - k )!} = \frac{n \cdot ( n - 1 ) \cdot ( n - 2 ) \cdot ... \cdot ( n - k + 1 )}{1 \cdot 2 \cdot 3 \cdot ... \cdot k} =

C_n^k = {n! \over k!(n - k)!} = { n \cdot (n - 1) \cdot (n - 2) \cdot ... \cdot (n - k + 1) \over 1 \cdot 2 \cdot 3 \cdot ... \cdot k} =

\frac{n !}{k !} \cdot (1 - \frac{1}{n}) \cdot (1 - \frac{2}{n}) \cdot ... \cdot (1 - \frac{k - 1}{n}) =

{n! \over k!} \cdot \left( 1 - {1 \over n} \right) \cdot \left( 1 - {2 \over n} \right) \cdot ... \cdot \left( 1 - {k - 1 \over n} \right) =

\frac{n !}{k !} \cdot e^{l n (1 - \frac{1}{n}) + l n (1 - \frac{2}{n}) + ... + l n (1 - \frac{k - 1}{n})} \leq (u se t h e in e q u a l i t y l n (1 - x) \leq - x)

{n! \over k!} \cdot e ^{ln \left( 1 - {1 \over n} \right) + ln \left( 1 - {2 \over n} \right) + ... + ln \left( 1 - {k - 1 \over n} \right)} \le (use~the~inequality~ln(1 - x) \le -x)

\frac{n !}{k !} \cdot e^{- \frac{1}{n} - \frac{2}{n} - ... - \frac{k - 1}{n}} = \frac{n !}{k !} \cdot e^{- \frac{k \cdot ( k - 1 )}{2 n}}

{n! \over k!} \cdot e ^{-{1 \over n} - {2 \over n} - ... - {k - 1 \over n}} = {n! \over k!} \cdot e^{-{k \cdot (k - 1) \over 2n}}

Binomial coefficient

Asymptotic nonations for the Binomial Coefficients

List of problems

Comments