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

3-misol. “Ixtiyoriy natural son uchun son 2ga qoldiqsiz bo‘linadi” degan tasdiqni tekshirishda matematik induksiya usulining baza qismi talabini bajarmasdan faqat induksion o‘tishni tekshiramiz.
Bu tasdiq uchun to‘g‘ri bo‘lsin, ja’ni son 2ga qoldiqsiz bo‘linsin deb faraz qilamiz. U holda son ham, qo‘shiuvchilarining har biri 2ga qoldiqsiz bo‘linganligi sababli, 2ga qoldiqsiz bo‘linadi. Shuning uchun tenglik asosida son 2ga qoldiqsiz bo‘linadi degan xulosa kelib chiqadi. Demak, yuqoridagi tasdiq uchun to‘g‘ri, ya’ni induksion o‘tish bajarildi deb hisoblash mumkin.
Shunday qilib, matematik induksiya usulining baza qismini tekshirmasdan “ixtiyoriy natural son uchun son 2ga qoldiqsiz bo‘linadi” degan xulosa qilish noto‘g‘ridir, chunki ixtiyoriy natural son uchun sonni 2ga bo‘lganda 1 qoldiq qoladi.
4-misol. “Ixtiyoriy natural son uchun ifodaning qiymati tub sondir” degan tasdiqni tekshirish maqsadida matematik induksiya usulining faqat baza qismi talabini dastlabki 15ta natural sonlar uchun bajaramiz.
bo‘lganda tub son hosil bo‘ladi. bo‘lganda ham ifodaning qiymati sifatida 23, 29, 37, 47, 59, 73, 89, 107, 127, 149, 173, 199, 227 va 257 tub sonlarni hosil qilamiz.
Induksion o‘tishni tekshirmasdan “ixtiyoriy natural son uchun ifodaning qiymati tub sondir” degan xulosa qilish noto‘g‘ridir, chunki, masalan, agar bo‘lsa, u holda bu ifodaning qiymati murakkab sondir: .
5-misol. Biror natural son uchun son butun sonning kvadrati bo‘ladimi? Bu savolga javob berish uchun, ning dastlabki o‘n, yuz, ming, million, milliard, hattoki, trillionta qiymatlari uchun ifoda tekshirilganda, uning qiymatlaridan birortasi ham butun son kvadrati bo‘lmasligi qayd etilgan. Shunday bo‘lishiga qaramasdan bu tasdiq asosida, induksion o‘tishni bajarmasdan, “ixtiyoriy natural son uchun ifodaning qiymati butun sonning kvadrati bo‘lmaydi” degan xulosa qilish mumkin emas. ifodaning qiymati butun sonning kvadrati bo‘ladigan natural sonning borligi va bunday sonning eng kichigini o‘nli sanoq sistemasida yozganda 29ta (!) raqam bilan ifodala-nishi komp’yuter yordamida aniqlangan ([34]ga qarang).
Matematik induksiya usulining tadbiqiga yana bir misol sifatida quyidagi teoremani isbotlaymiz.