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

x1+...+xk = n (2) (Editorial)

Consider a sequence of $n + k - 1$ n + k - 1 positions. In $n$ positions we should place $1$ . In $k - 1$ 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$ x_1 + x_2 + x_3 = 4 (4 ones and $2$ plus signs):

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

Example

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

$(4, 0, 0)$ (4, 0, 0) and its $3$ permutations
$(3, 1, 0)$ (3, 1, 0) and its $6$ permutations'
$(2, 2, 0)$ (2, 2, 0) and its $3$ permutations
$(2, 1, 1)$ (2, 1, 1) and its $3$ permutations

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

Algorithm implementation

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

Python implementation

import math

Read the input data.

k, n = map(int,input().split())

Вычисляем и выводим ответ $C_{n + k - 1}^{k - 1}$ C_{n+k-1}^{k-1}.

res = math.comb(n + k - 1, k - 1)
print(res)