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

x1+...+xk = n (2) (Розбір)

Розгляньмо послідовність із $n + k - 1$ n + k - 1 позицій. У $n$ позиціях слід поставити $1$ . У $k - 1$ k - 1 позицію слід поставити символ ' $+$ ' (щоб отримати $k$ доданків).

Будь-якій розстановці одиниць і знаків ' $+$ ' по позиціях відповідатиме деяке розв'язання заданого рівняння. Наприклад, розгляньмо деякі рішення рівняння $x_{1} + x_{2} + x_{3} = 4 (4$ x_1 + x_2 + x_3 = 4 (4 одиниці і $2$ плюса):

Нам слід вставити $k - 1$ k - 1 плюс на $n + k - 1$ n + k - 1 позицій. Це можна зробити $C_{n + k - 1}^{k - 1}$ C_{n+k-1}^{k-1} способами.

Приклад

Розгляньмо рівняння $x_{1} + x_{2} + x_{3} = 4$ x_1 + x_2 + x_3 = 4. Його розв'язаннями будуть:

$(4, 0, 0)$ (4, 0, 0) і її $3$ перестановки
$(3, 1, 0)$ (3, 1, 0) і її $6$ перестановок
$(2, 2, 0)$ (2, 2, 0) і її $3$ перестановки
$(2, 1, 1)$ (2, 1, 1) і її $3$ перестановки

Усього маємо $3 + 6 + 3 + 3 = 15$ 3 + 6 + 3 + 3 = 15 рішень.

Реалізація алгоритму

Функція Cnk обчислює значення біноміального коефіцієнта $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++

Основна частина програми. Читаємо вхідні дані.

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

Обчислюємо і виводимо відповідь $C_{n + k - 1}^{k - 1}$ C_{n+k-1}^{k-1}.

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

Python реалізація

import math

Читаємо вхідні дані.

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)