22-Ma’ruza. Kombinatorikaning umumiy tushunchalari, usullari va qoidalari. Asosiy kombinasiyalar reja

2-teorema. ta elementdan tadan o‘rinlashtirishlar soni eng kattasi ga teng bo‘lgan ta ketma-ket natural sonlarning ko‘paytmasiga tengdir, ya’ni .
Isboti. – ixtiyoriy natural son bo‘lsin. Teoremani isbotlash uchun matematik induksiya usulini qo‘llab, teorema tasdig‘ining dan oshmaydigan ixtiyoriy natural son uchun to‘g‘riligini ko‘rsatamiz (ya’ni induksiyani bo‘yicha bajaramiz).
Baza: yuqorida ekanligi aniqlangan edi, ya’ni teorema tasdig‘i uchun to‘g‘ridir.
Induksion o‘tish: formula uchun to‘g‘ri bo‘lsin deb faraz qilamiz va uning uchun ham to‘g‘ri ekanligini ko‘rsatamiz. ta elementdan tadan o‘rinlashtirishlarning ixtiyoriy bittasini quyidagicha hosil qilish mumkin. Bunday o‘rinlashtirishning birinchi elementi sifatida berilgan to‘plamning istalgan elementini, masalan, ni tuzilayotgan o‘rinlashtirishga joylashtiramiz. Undan keyin umumiy soni ga teng bo‘lgan ta elementdan tadan o‘rinlashtirishlarning ixtiyoriy biridagi barcha elementlarni joylashtiramiz. Birinchi elementi dan iborat bo‘lgan barcha ta elementdan tadan o‘rinlashtirishlarning soni ga tengdir. Bunday o‘rinlashtirishlarning birinchi elementi sifatida to‘plamning ixtiyoriy elementini tanlash mumkinligini e’tiborga olsak, ko‘paytirish qoidasiga binoan, berilgan ta elementdan tadan o‘rinlashtirishlar soni quyidagicha aniqlanishi kelib chiqadi:

.
Bu munosabat isbotlanayotgan formulaning uchun to‘g‘riligini ko‘rsatadi.
3-misol. Guruh 25 nafar talabadan tashkil topgan bo‘lsin. Bu guruhda guruh sardori, guruh sardorining yordamchisi va kasaba uyushmasining guruh bo‘yicha vakilini saylash zarur. Har bir talaba bu vazifalardan faqat bittasini bajaradi deb hisoblansa, saylov natijalari uchun qancha imkoniyat mavjud?
Bu yerda 25ta elementli talabalar to‘plamining tartiblangan uchta elementli (guruh sardori, guruh sardorining yordamchisi va kasaba uyushmasining guruh bo‘yicha vakili) qism to‘plamlari sonini aniqlash zarur. Bu esa 25ta elementdan uchtadan o‘rinlashtirishlar sonini topish demakdir. Qo‘yilgan savolga javob topish maqsadida 2-teoremadagi isbotlangan formulani va bo‘lgan holda qo‘llab, ekanligini aniqlaymiz. Demak, guruhdagi saylov natijalari uchun 13800ta imkoniyat mavjud.
formulani ko‘rinishda ham yozish mumkin. Haqiqatdan ham,
.
Yuqorida ta’kidlaganganidek, ta elementdan tadan o‘rilashtirishlar elementli to‘plamning bir-biridan tarkibi bilan ham, elementlarining joylashishi bilan ham farqlanadigan qism to‘plamlaridan iboratdir. Agar bu o‘rinlashtirishlarda ta elementli to‘plamning barcha elementlari qatnashsa (ya’ni bo‘lsa), ta elementli to‘plam uchun barcha o‘rin almashtirishlar hosil bo‘lishi tabiiydir. Shu tufayli, o‘rin almashtirishlarning oldin keltirilgan ta’rifiga ekvivalent quyidagi ta’rifni ham berish mumkin.
ta elementli to‘plam uchun o‘rin almashtirishlar deb ta elementdan tadan o‘rinlashtirishlarga aytiladi. Bunda har bir element faqat bir marta qatnashadi va ular bir-biridan faqat o‘zaro joylashishlari bilan farq qiladilar.
O‘rin almashtirishlarning bu ta’rifiga asoslanib ta elementli to‘plam uchun o‘rin almashtirishlar soni formulasini o‘rinlashtirishlar soni formulasi yordamida hosil qilish mumkin. Haqiqatdan ham,

yoki .