x1+...+xk = n#11550

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

Скористаємося методом "куль і перегородок" ("stars and bars"). Випишемо підряд $n$ одиниць: $11...1$ . Між сусідніми одиницями є $n - 1$ n - 1 проміжок. Виберемо будь-які $k - 1$ k - 1 з них і поставимо в кожен вибраний проміжок знак ' $+$ '. Одиниці розіб'ються на $k$ послідовних груп; позначимо через $x_{i}$ x_i кількість одиниць у $i$ -й групі. Наприклад, при $n = 6$ n = 6 запис $11 + 111 + 1$ 11+111+1 задає розв'язок $(2, 3, 1)$ (2, 3, 1) рівняння $x_{1} + x_{2} + x_{3} = 6$ x_1 + x_2 + x_3 = 6.

Кожна така розстановка задає натуральний розв'язок рівняння. Дійсно, сума розмірів усіх груп дорівнює $n$ , а кожна група непорожня: знак ' $+$ ' не ставиться перед першою та після останньої одиниці, і в один проміжок не можна поставити два знаки. Отже, усі $x_{i} \geq 1$ x_i \ge 1.

Між розв'язками рівняння та способами вибрати $k - 1$ k - 1 проміжок з $n - 1$ n - 1 існує взаємно однозначна відповідність. Тому шукана кількість розв'язків дорівнює $C_{n - 1}^{k - 1}$ C_{n-1}^{k-1}.

Наприклад, при $n = 5, k = 3$ n = 5, k = 3 є $n - 1 = 4$ n - 1 = 4 проміжки, з яких потрібно вибрати $k - 1 = 2$ k - 1 = 2. Це можна зробити $C_{4}^{2} = 6$ C_4^2 = 6 способами, і кожному вибору відповідає рівно один розв'язок рівняння $x_{1} + x_{2} + x_{3} = 5$ x_1 + x_2 + x_3 = 5:

Приклад

Розглянемо рівняння $x_{1} + x_{2} + x_{3} = 4$ x_1 + x_2 + x_3 = 4. Воно має $3$ додатних цілочислових розв'язки: $(1, 1, 2), (1, 2, 1), (2, 1, 1)$ (1, 1, 2), (1, 2, 1), (2, 1, 1).

Наприклад, $n = 4$ n = 4 одиниці на $k = 3$ k = 3 доданки можна розбити $C_{2}^{3} = 3$ C_2^3 = 3 способами:

Примітка

Розглянемо кілька варіантів цієї задачі:

Вчителька принесла в клас $n$ однакових цукерок і хоче роздати їх $k$ учням так, щоб кожен отримав хоча б одну цукерку. Знайдіть, скількома способами можна це зробити.
На парті лежать $n$ однакових зошитів. Їх потрібно розкласти в $k$ стопок так, щоб у кожній стопці був хоча б один зошит. Визначте, скількома способами можна це зробити.

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

Функція Cnk обчислює значення біноміального коефіцієнта $C_{n}^{k}$ C_n^k.

long long Cnk(long long k, long long n)
{
  long long res = 1;
  if (k 
}

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

scanf("%lld %lld",

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

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

Python реалізація

import math

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

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

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

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