x1+...+xk = n#11550

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

"Toplar və arakəsmələr" ("stars and bars") üsulundan istifadə edək. $n$ ədəd vahidi ardıcıl yazaq: $11...1$ . Qonşu vahidlər arasında $n - 1$ n - 1 aralıq var. Onlardan istənilən $k - 1$ k - 1 ədədini seçib hər seçilmiş aralığa ' $+$ ' işarəsi qoyaq. Vahidlər $k$ ədəd ardıcıl qrupa bölünəcək; $i$ -ci qrupdakı vahidlərin sayını $x_{i}$ x_i ilə işarə edək. Məsələn, $n = 6$ n = 6 olduqda $11 + 111 + 1$ 11+111+1 yazısı $x_{1} + x_{2} + x_{3} = 6$ x_1 + x_2 + x_3 = 6 tənliyinin $(2, 3, 1)$ (2, 3, 1) həllini müəyyən edir.

Hər belə düzülüş tənliyin natural həllini müəyyən edir. Həqiqətən, bütün qrupların ölçülərinin cəmi $n$ -ə bərabərdir, hər qrup isə boş deyil: birinci vahiddən əvvəl və sonuncu vahiddən sonra ' $+$ ' işarəsi qoyulmur, və bir aralığa iki işarə qoymaq olmaz. Deməli, bütün $x_{i} \geq 1$ x_i \ge 1.

Tənliyin həlləri ilə $n - 1$ n - 1 aralıqdan $k - 1$ k - 1 ədədini seçmə üsulları arasında qarşılıqlı birqiymətli uyğunluq mövcuddur. Buna görə axtarılan həllərin sayı $C_{n - 1}^{k - 1}$ C_{n-1}^{k-1}-ə bərabərdir.

Məsələn, $n = 5, k = 3$ n = 5, k = 3 olduqda $n - 1 = 4$ n - 1 = 4 aralıq var, onlardan $k - 1 = 2$ k - 1 = 2-sini seçmək lazımdır. Bunu $C_{4}^{2} = 6$ C_4^2 = 6 üsulla etmək olar, və hər seçimə $x_{1} + x_{2} + x_{3} = 5$ x_1 + x_2 + x_3 = 5 tənliyinin düz bir həlli uyğun gəlir:

Misal

$x_{1} + x_{2} + x_{3} = 4$ x_1 + x_2 + x_3 = 4 tənliyinə baxaq. Onun $3$ müsbət tam ədədli həlli var: $(1, 1, 2), (1, 2, 1), (2, 1, 1)$ (1, 1, 2), (1, 2, 1), (2, 1, 1).

Məsələn, $n = 4$ n = 4 vahidi $k = 3$ k = 3 toplananlara $C_{2}^{3} = 3$ C_2^3 = 3 üsulla bölmək olar:

Qeyd

Bu məsələnin bir neçə variantına baxaq:

Müəllimə sinfə $n$ ədəd eyni konfet gətirib və onları $k$ şagirdə elə paylamaq istəyir ki, hər biri ən azı bir konfet alsın. Bunu neçə üsulla etmək mümkün olduğunu tapın.
Parta üzərində $n$ ədəd eyni dəftər var. Onları $k$ qalaq şəklində elə düzmək lazımdır ki, hər qalaqda ən azı bir dəftər olsun. Bunu neçə üsulla etmək mümkün olduğunu müəyyən edin.

Alqoritmin reallaşdırılması

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

long long Cnk(long long k, long long n)
{
  long long res = 1;
  if (k 
    res = res * (n - i + 1) / i;
  return res;
}

C++

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

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

$C_{n - 1}^{k - 1}$ C_{n-1}^{k-1} cavabını hesablayıb çıxarırıq.

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

Python reallaşdırılması

import math

Giriş məlumatlarını oxuyuruq.

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

$C_{n - 1}^{k - 1}$ C_{n-1}^{k-1} cavabını hesablayıb çıxarırıq.

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