Guliston davlat universiteti

kC =(n-k+1)C
Bu tenglikdan C ni topib olsak :



A toʻplamning bir elementli qism toʻplamlar soni n elementlar miqdoriga teng .C oʻrniga n sonini qoʻyib , (1) ni hosil qilamiz.
n elementli toʻplamning ixtiyoriy k – elementli qism toʻplami n ta elementdan k tadan tuzilgan birikma deyiladi .
Qism toʻplamda elementlarning tartibi ahamiyatga ega emas . Ba’zida “birikma” soʻzi oʻrniga kombinatsiya termini qoʻllaniladi -n ta elementdan k tadan .
Biz aniqladikki , n ta elementdan k tadan birikma soni

ga teng.

1.2-misol:Necha usul bilan oʻquvchi 5 kitobdan 3 tasini tanlashi mumkin ?

Yechish: Usullarning izlangan sonibesh elementli toʻplamning uch elementli qism toʻplamning soniga teng :

1.3-misol:Necha usul bilan 7 kishidan 3 kishilik komissiya tanlash mumkin ?

Yechish: Kamissiyaning barcha imkoniyatlarini koʻrib chiqish uchun 7 kishidan tuzilgan toʻplamning 3 elementli qism toʻplamining barcha elementlarini koʻrib chiqish kerak .
Usullarning izlangan soni quyidagiga teng :

1.4-misol:Turnirda n shaxmatchi ishtirok etdi va har ikki shaxmatchi bir martadan uchrashishdi . Turnirda necha partiya oʻyin oʻynaldi ?
Yechish: n ta elementli toʻplamda nechita ikki elementli qism toʻplam ajratish mumkin boʻlsa , shuncha partiya oʻynalgan .

1.5–Masala. Ixtiyoriy uchtasi bir toʻgʻri chiziqda yotmaydigan 6 ta nuqta berilgan. Shu 6 ta nuqtalar orqali nechta turlcha toʻgʻri chiziq oʻtkazish mumkin?
Yechish. Berilgan 6 ta nuqtani 6 elementli toʻplam deb qarash mumkin. Har 2 ta nuqta orqali bitta toʻgʻri chiziq oʻtkazish mumkin. Demak, 6 elementli toʻplamdan ikki elementli qism toʻplamlar ajratishimiz kerak. Bu berilgan 6 ta nuqta orqali ta turlicha toʻgʻri chiziq oʻtkazish mumkin”

1.6–Masala. 20 kishi ichidan 4 vakilni necha usul bilan saylash mumkin?

Yechish. Berilgan 20 kishini 20 elementli toʻplam deb qarash mumkin. 20 elementli toʻplamdan 4 elementli qism toʻplamlar ajratishimiz kerak.

1.7–Masala. Bir aylanada yotgan 5 ta nuqta ustidan nechta vatar oʻtkazish mumkin.

Yechish. Berilgan 5 ta nuqtani 5 elementli toʻplam deb qarash mumkin. Aylanada har ikki nuqta orqali vatar oʻtkazish mumkin. Demak, 5 elementli toʻplamdan ikki elementli qism toʻplamlar ajratishimiz kerak.



1.8–Masala. Bir kishida 10 ta kitob, ikkinchisida 12 ta kitob bor. Almashtirish uchun ularning har biri necha usul bilan 3 tadan kitob tashlashlari mumkin.
Yechish. Bu masalamizda 2 ta toʻplam boʻladi. 10 elementli va 12 elementli toʻplam deb qaraymiz. Ularning har biridan 3 elementli qism toʻplamlar ajratib koʻpaytiramiz.:



1.9–Masala. Latereya biletidagi 49 nomerdan 5 tasini nech xil usul bilan oʻchirish mumkin.
Yechish. Berilgan 49 nomerni 49 elementli toʻplam deb qaraymiz. Shu toʻplamdan 5 toʻplam qism toʻplamlar ajratamiz.

1.10-misol: n- qavariq burchaklikning diaganallari nechita nuqtada kesishadi ?

agarda ularning uchtasidan hech qaysisi bir nuqtada kesishmasa ?
Yechish:Ikki diaganal kesishmasining har bir nuqtasiga n –burchaklikning 4 choʻqqisi mos boʻladi . n –burchaklikning har bir 4 choʻqqisiga esa kesishmaning bir nuqtasi mos keladi .(toʻrtburchak diaganalining kesishma nuqtasi choʻqqilari bilan toʻrt nuqtada berilgan ). Shuning uchun kesishmaning barcha nuqtalar soni shunday usullar soniga tengki, ular bilan n choʻqqilar orasidan 4 choʻqqini tanlash mumkin :

Biz C soni uchun qiziqarli geometric talqinini beradigan quyidagi masalani qaraymiz :
1.11-misol : (Shaxmat shaharchasi )
m n oʻlchamli toʻgʻri burchakli toʻrni qaraymiz .Bu toʻr m n toʻgʻri burchakli kvartallardan iborat boʻlib , u n-1 ta “gorizontal” va m-1 ta “vertikal koʻchalar ” ga boʻlingan.(3-rasm).
Chap quyi burchaklardan va ((0;0) nuqtalar ) oʻng yuqori burchakka ((m;n) nuqtaga) olib boruvchi turli qisqa yoʻlning soni qanday ?
Yechish (0;0) nuqtadan (m;n) nuqtagacha har bir qisqa yoʻl m+n kesmalardan iborat boʻlib , jumladan ularning m tasi gorizontal, n tasi vertikal kesmalar boʻladi.
Turli yoʻllar faqat gorizontal va vertical kesmalarning oʻrni almashishi bilangina farqlanadi . Shuning uchun ham umumiy yoʻllar soni n+m kesmalardan n ta vertical kesmalarni tanlash usuliga bogʻliq boʻladi va bu ajratib olishlar soni ya’ni .
Xuddi shunday bu tanlash usullarini m ta gorizontal olishimiz mumkin , ya’ni
.
Quyidagi tenglikning oʻrinli ekanligini kombinatsiyalar sonini faktariallar orqali ham ifodalash mumkin .
= .
Shunday qilib (0;0) nuqtadan (m;n) nuqtagacha qisqa yoʻllarning soni
=
ga teng .
1.2- Teorema: (2)
tenglama oʻrinlidir.
Isbot1:
Formulani qoʻllagan holda (2) tenglikning toʻgʻriligiga ishonch hosil qilish qiyin emas.
Demak



tengliklarni yozib oldik. Endi (2) tenglikka etib qoʻyamiz :


Yana isbotning boshqa usullarini keltiramiz :
Isbot2: n –elementdan tashkil topgan A toʻplamning ayrim a elementini va barcha A toʻplamning k –elementli qism toʻplamni koʻrib chiqamiz (Bunday qism toʻplam soni ga teng).
A toʻplamning barcha k –elementli qism toʻplamlarini ikki guruhga ajratamiz:
1) tarkibiga a kiruvchi qism toʻplam ,
2) tarkibiga a kirmaydigan qism toʻplam;
Birinchi gruppadagi qism toʻplam soni ga teng . Har bir qism toʻplam a ga A toʻplamning ayrim (k-1)–elementli qism toʻplamning qoʻyilishidan hosil boʻladi.
Ikkinchi gruppadagi qism toʻplamning soni gat eng . Har bir shunday qism toʻplam A -{a} toʻplamning k –elementli qism toʻplamidir . Bundan

tenglik oʻrinli ekanligi kelib chiqadi .

Isbot3: O(0;0) nuqtadan A(k;n-k) nuqtaga qisqacha yoʻl soni ga teng.(4-rasm)
Barcha bunday yoʻllarni ikki gruppaga boʻlish mukin :
A (k-1;n-1) nuqta orqali oʻtuvchi yoʻllar (ular soni ga teng) va nuqta orqali oʻtuvchi yoʻllar (ular soni ga teng ).
Bundan
tenglik oʻrinli ekanligi kelib chiqadi.
1.12-Masala. 2 n ta elementdan n+1 tadan tuzilgan kombinatsiyalar soninig 2n+1 elementdan n-1 tadan tuzilgan kombinatsiyalar soniga nisbati 3:5 kabi. n ni toping.
Yechish. Masalani shartiga koʻra ushbu tenglamani tuzamiz.





5(n+2)=3(2n+1)
5n+10=6n+3
n=7

1.13-misol :

(3)
ayniyatni isbotlang.
Yechish: O(0;0) nuqtadan A(n;n) nuqtaga qisqacha yoʻl soni gat eng . Har bir bunday yoʻl BD diaganalga yotuvchi A (k;n-k) boʻlgan bitta va faqat bitta nuqta orqali oʻtadi .(5-rasm)
O nuqtadan A nuqtaga yoʻllar soni gat eng . A nuqtadan A nuqtaga yoʻl esa ga teng, shuning uchun A orqali oʻtuvchi O dan A ga yoʻl soni ga teng (koʻpaytirish jadvali).
Har bir A (k=0,1,…,n) nuqtadan oʻtuvchi yoʻllar miqdorini qoʻshib ,O dan A gacha yoʻlning umumiy miqdorini hosil qilamiz, tabiiyki . Bu mulohaza (3) tenglikni isbotlaydi .