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

x1+...+xk = n (2) (Həll təhlili)

$n + k - 1$ n + k - 1 mövqedən ibarət ardıcıllığı nəzərdən keçirək. $n$ mövqeyə $1$ qoymaq lazımdır. $k - 1$ k - 1 mövqe üçün '+' simvolu qoyulmalıdır (beləliklə, $k$ toplananları əldə etmək üçün).

Hər hansı bir mövqeyə $1$ və '+' işarələrinin qoyulması müəyyən bir uyğun həllə cavab verəcəkdir. Məsələn, $x_{1} + x_{2} + x_{3} = 4$ x_1 + x_2 + x_3 = 4 (4 ədəd və 2 üstəgəl) tənliyinin bəzi həlləri:

$n + k - 1$ n + k - 1 mövqeyə $k - 1$ k - 1 üstəgəl işarəsi daxil etməliyik. Bunu $C_{n + k - 1}^{k - 1}$ C_{n+k-1}^{k-1} üsulla etmək mümkündür.

Nümunə

$x_{1} + x_{2} + x_{3} = 4$ x_1 + x_2 + x_3 = 4 tənliyini nəzərdən keçirək. Onun həll yolları olacaqdır:

$(4, 0, 0)$ (4, 0, 0) və onun $3$ permutasiyaları
$(3, 1, 0)$ (3, 1, 0) və onun $6$ permutasiyaları
$(2, 2, 0)$ (2, 2, 0) və onun $3$ permutasiyaları
$(2, 1, 1)$ (2, 1, 1) və onun $3$ permutasiyaları

Cəmi $3 + 6 + 3 + 3 = 15$ 3 + 6 + 3 + 3 = 15 həll var.

Alqoritmin icrası

Cnk funksiyası $C_{n}^{k}$ C_n^k binomial əmsalını hesablayır.

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++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

Cavabı $C_{n + k - 1}^{k - 1}$ C_{n+k-1}^{k-1} hesablayır və çıxardırıq.

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

Python icrası

import math

Giriş məlumatlarını oxuyuruq.

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

Cavabı $C_{n + k - 1}^{k - 1}$ C_{n+k-1}^{k-1} hesablayır və çıxardırıq.

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