Olimpiada masalalari

4. Birikma

M – n ta elementdan tashkil topgan, chegaralangan (tartiblangan bo‘lishi shart emas) to‘plam bo‘lsin.

Esda tuting! n elementning k tadan birikmasi to‘plamning k elementdan iborat ixtiyoriy qism to‘plamiga aytiladi. n elementning k tadan ikkita birikmasini agar ularning birida boshqasida bo‘lmagan aqalli bitta elementi mavjud bo‘lsa, ularni har xil deb hisoblaymiz.

Boshqa so‘z bilan aytganda, brikmalarda elementlarning joylashish o‘rni ahamiyatga ega emas, ularning faqat tarkibi ahamiyatlidir. Masalan, M = {1, 2, 3, 4} to‘plamdan 4 tasidan 3 tadan qilib to‘rtta har xil birikma hosil qilishimiz mumkin: {1, 2, 3}, {1,2,4}, {2, 3, 4}, {1, 3, 4}.

n elementning k tadan birikmalar soni quyidagiga teng:
Agar k = 0, u holda
n elementning k tadan joylashuvi soni

ga tengligini hisobga olgan holda, birikmalar sonini joylashtirishlar soni orqali ifodalash mumkin, u holda biz quyidagi qiymatga ega bo‘lamiz:
.
161-misol. Hech bir uchtasi bitta nuqtada yotmaydigan va hech bir to‘rttasi bitta tekislikda yotmaydigan 10 ta nuqta berilgan. Bu nuqtalardan nechta har xil tekislik o‘tkazish mumkin?

Geometriyadan bizga shunday aksioma ma’lumki, unga ko‘ra bitta tog‘ri chiziqda yotmaydigan uchta nuqtadan tekislik o‘tkazish mumkin, jumladan faqat bitta.

Shunday ekan, u holda, agar tekislik uchta A,B,C nuqtadan o‘tsa, B,A,C yoki C,B,A nuqtalardan huddi shu tekislik o‘tadi, ya’ni tekislik o‘tadigan uchta nuqtaning joylashish tartibi ahamiyatga ega emas. Demak, 10 ta nuqtaning har 3 tasidan o‘tkazilgan har xil tekisliklar soni 10 ta elementning 3 tadan birikmalari soniga teng.
n elementning k tadan birikmalari sonini hisoblovchi protsedura tuzamiz.
Buning uchun ikkinchi formuladan foydalanish qulayroq, chunki unda faqatgina k sonining faktoriali hisoblonadi. formulada esa uchtasini hisoblash kerak (n!, (n - k)! и k!) va bunda berilgan butun turning chegarasidan chiquvchi juda katta sonlar hosil bo‘lishi mumkin.
Birikmalar soni uchun katta sonlarning chiqishini va sonlarning faktoriali hisoblanishini bartaraf etish maqsadida boshqa formuladan foydalansa ham bo‘ladi.

Shunday qilib formuladan foydalanamiz.
#include
#include
using namespace std;
int Almashtirishlar(int n, int k)
{
int S = 1;
for (int i = 1; i <= k; i++)
S *= (n - k + i);
return S;
}
int Fakt(int n)
{
int S=1;
for (int i = 1; i <= n; i++)
S *= i;
return S;
}
int main()
{
long S;
int n, k;
cout << "n="; cin >> n;
cout << "k="; cin >> k;
S = Almashtirishlar(n, k) / Fakt(k);
cout << "S=" << S << endl;
return 0;
}
162-misol. Agar jamoa safiga 3 ta hujumchi, 2 ta himoyachi va 1 ta darvozabon kirishi kerak bo‘lsa, u holda 9 ta hujumchi, 5 ta himoyachi va 3 ta darvozabondan har xil ko‘rinishdagi nechta xokkey jamoasini tuzish mumkin?