1. Birlashmalar va uning elementlari. O’rin almashtirish

3-masala. Bir vazifaga ko'rsatilgan 10 nomzoddan uch kishi saylanishi kerak. Saylovdagi turli ehtimollar qancha bo'lishi mumkin?
Echish: Saylovdagi ehtimollar soni 10 elementni 3 tadan joylashtirib tuzish mumkin bo'lgan barcha gruppalashlar soniga teng bo'ladi, ya’ni

1. 0

Bu jadval buyuk frantsuz matematigi B. Paskal nomi bilan atalib “Paskal uchburchagi” deyiladi. Paskal uchburchagidagi har bir satrda uning boshidan va oxiridan bir xil uzoqlikda turgan sonlar teng bo'ladi. Masalan,

Bu xossa umumiy xususiyatga ega: istalgan n va m uchun
(14)
tenglik o'rinli bo'ladi. Bu formulani isbotlaylik

(14) tenglik ning qiymatini topishni juda osonlashtiradi.

2. Gruppalashda
(15)
tenglik ham o'rinli bo'ladi.
Agar (13) formuladan foydalansak


Bu tengliklarni qo'shib, umumiy maxrajga keltirib, olamiz:

3. yig'indi n ta elementdan iborat bo'lgan to'plamning barcha qism to'plamlarining yig'indisini ifodalaydi. SHuning uchun

tenglik quyidagi teoremaning natijasi bo'ladi.
Teorema. n ta elementdan iborat bo'lgan to'plam barcha qism to'plamlarining soni 2ⁿ ga teng bo'ladi.
Bu teoremaning tasdig'ini yuqorida 3 ta elementli to'plam uchun barcha qism to'plamlarining soni 8 ta, ya’ni 2³ ga tengligini ko'rsatgan edik. n=0 bo'lganda bo'sh to'plamni olamiz. Bo'sh to'plam o'zidan iborat bo'lgan yagona qism to'plamga ega. n>1 uchun esa teoremani matematik induktsiya usuli yordamida isbotlaymiz.
1) Bitta elementdan iborat bo'lgan to'plam, masalan {a} to'plam ikkita qism to'plamga ega: bo'sh to'plam va {a} to'plamning o'zidan iborat. n=1 bo'lganda teorema isbotlandi; chunki 2¹=2.
2) A(k)=A(k+1) bo'lishligini, ya’ni k ta elementga ega bo'lgan to'plam 2^k ta qism to'plamga ega bo'lishligidan k+1 ta elementga ega bo'lgan to'plamning 2^k+1 ta qism to'plamga ega bo'lishligining kelib chiqishligini ko'rsataylik.
k+1 ta elementga ega bo’lgan B={b₁ ,b₂ ,....,b_k, b_k+1} to'plamni qaraylik. B¹ to'plam esa B to'plamning b_k+1 elementidan boshqa barcha elementlaridan tashkil topgan bo'lsin.
^B1={b₁ ,b₂ ,....,b_k}
A(k) mulohazaga ko'ra B¹ to'plam 2^k ta to'plam ostiga ega. Bu qism to'plamlarning har biridan, ularning har biriga b_k+1 elementni qo’shib, yangi to'plamlar hosil qilamiz. Natijada B to'plamning yana 2^k ta qism to'plamlarini olamiz. Bunday holda B to'plamning 2^k+2^k=2x2^k=2^k+1 ta qism to'plamlarini olamiz.
Matematik induktsiya printsipiga ko'ra teorema isbotlandi. Fikrimizning n=k hol uchun to'g'riligidan uning n=k+1 hol uchun to'g'riligini ko'rsata oldik. SHuning uchun fikrimiz istalgan N natural son uchun o'rinli bo'ladi.