O’RINLASHTIRISH, O’RIN ALMASHTIRISHLAR. GRUPPALASHLAR Reja: 1. O‘rin almashtirishlar. 2. O‘rinlashtirishlar. 3. Gruppalashlar. 1. O‘rin almashtirishlar. Elementlari a1,a2,a3,...,an bo‘lgan to‘plamni qaraymiz. Bu to‘plam elementlarini har xil tartibda joylashtirib (yozib), tuzilmalar ( kombinatsiyalar ) hosil qilish mumkin, masalan, a1,a2,a3,...,an ; a2,a1,a3,...,an ; a2,a3,a1,...,an . Bu tuzilmalarning har birida berilgan to‘plamning barcha elementlari ishtirok etgan holda ular bir-biridan faqat elementlarning joylashish o‘rinlari bilan farq qiladilar. Shu usul yordamida hosil qilingan kombinatsiyalarning har biri berilgan {a1,a2,a3,...,an} to‘plam elementlarining o‘rin almashtirishi deb ataladi. Aslida “o‘rin almashtirish” iborasi to‘plam elementlarining o‘rinlarini o‘zgartirish harakatini anglatsada, bu yerda uni shu harakat natijasidagi hosil bo‘lgan tuzilma sifatida qo‘llaymiz. Bu iboradan uning asl ma’nosida ham foydalanamiz. O‘rin almashtirishni ifodalashda uning elementlarini ajratuvchi belgi sifatida yuqorida “,” (vergul) belgisidan foydalanildi. Ammo bu muhim emas, bu yerda boshqa belgidan ham foydalanish, hattoki, yozuvning ixchamligi maqsadida, elementlar orasidagi ajratuvchi belgilarni tushirib qoldirilish ham mumkin. Bu eslatma bundan keyin bayon etiladigan boshqa kombinatorik tuzilmalar uchun ham o‘rinlidir. To‘plam tushunchasiga asoslanib, bu yerda qaralayotgan o‘rin almashtirishlar tarkibida elementlarning takrorlanmasligini eslatib o‘tamiz. Shu sababli bunday o‘rin almashtirishlarni betakror ( takrorli emas ) o‘rin almashtirishlar deb ham atash mumkin. Ushbu bobning 4- paragraf ida takrorli o‘rin almashtirishlar ko‘riladi.

Berilgan n ta elementli to‘plam uchun barcha o‘rin almashtirishlar sonini Pn bilan belgilash qabul qilingan 1 . Bitta elementli {a} to‘plam uchun faqat bitta a ko‘rinishdagi o‘rin almashtirish borligi ravshandir: P1=1 . Ikkita elementli {a,b} to‘plam elementlaridan o‘rin almashtirishlarni bitta elementli {a} to‘plam uchun a o‘rin almashtirishidan foydalanib quyidagicha tashkil qilamiz: b element a elementdan keyin yozilsa ab o‘rin almashtirishga, oldin yozilsa esa ba o‘rin almashtirishga ega bo‘lamiz. Demak, ko‘paytirish qoidasiga (ushbu bobning 1-paragraf iga qarang ) binoan ikkita o‘rin almashtirish bor: P2=2=1⋅2 . Uchta elementli {a,b,c} to‘plam uchun o‘rin almashtirishlar tashkil qilishda ikkita elementli {a,b} to‘plam uchun tuzilgan ab va ba o‘rin almashtirishlardan foydalanish mumkin. Berilgan to‘plamning c elementini ab va ba o‘rin almashtirishning har biriga uch xil usul bilan joylashtirish mumkin: ularning elementlaridan keyin, elementlarining orasiga va elementlaridan oldin. Ko‘paytirish qoidasi ni qo‘llasak, uchta elementli {a,b,c} to‘plam uchun oltita ( P3= 6=1⋅2⋅3 ) har xil o‘rin almashtirishlar hosil bo‘lishini aniqlaymiz. Ular quyidagilardir: abc, acb, cab, bac, bca, cba . To‘rtta elementli {a,b,c,d} to‘plamni qarab, uchta elementli {a,b,c} to‘plam uchun tuzilgan oltita o‘rin almashtirishlarning har biriga d elementni to‘rt xil usul bilan joylashtirish imkoniyati borligini e’tiborga olsak, ko‘paytirish qoidasi ga ko‘ra, P4= 24 = 1⋅2⋅3⋅4 bo‘lishini topamiz . Bu yerda barcha o‘rin almashtirishlar quyidagilardir: abcd ,abdc ,adbc ,dabc , acbd ,acdb ,adcb ,dacb , cabd ,cadb ,cdab ,dcab , bacd ,badc ,bdac ,dbac , 1 Fransuzcha “permution” so‘zi o‘rin almashtirish ma’nosini anglatadi.

bcad ,bcda ,bdca ,dbca, cbad ,cbda ,cdba ,dcba . Shu tarzda davom etib “ n ta elementli to‘plam uchun barcha o‘rin almashtirishlar soni birdan n gacha bo‘lgan barcha natural sonlarning ko‘paytmasiga teng” deb faraz qilish mumkin: Pn=1⋅2⋅...⋅(n−1)n . Bu farazning to‘g‘riligi quyidagi 1-teoremada isbot qilinadi. Dastlabki n ta natural sonlar ko‘paytmasini n! ko‘rinishida 2 belgilash qabul qilingan, ya’ni 1⋅2⋅3⋅...⋅n= n! . n! belgisidan bunday ma’noda birinchi bo‘lib K. Kramp 3 1808 yilda nashr etilgan algebra bo‘yicha qo‘llanmada foydalangan. 1⋅2⋅3⋅...n ifodada n=1 bo‘lganda faqat 1 soni ishtirok etadi , shuning uchun , ta ’ rif sifatida 1!=1 deb hisoblash qabul qilingan . Bundan tashqari, n=0 bo‘lganda esa n! ifoda umuman ma’nosini yo‘qotadi. Lekin, ta’rif sifatida 0!=1 deb qabul qilinadi. 1- t e o r e m a . Elementlari soni n ta bo‘lgan to‘plam uchun o‘rin almashtirishlar soni n! ga teng, ya’ni Pn=n! . I s b o ti . Teoremani isbotlash uchun matematik induksiya usulidan foydalanamiz. Asos to‘g‘riligini, ya’ni teoremaning tasdig‘i n=1 uchun to‘g‘riligini yuqorida ko‘rdik. Induksion o‘tish uchun teoremaning tasdig‘i biror natural n=k uchun to‘ g‘ ri bo‘lsin deb faraz qilamiz, ya’ni Pk=k! bo‘lsin. Ravshanki, (k+1) ta elementli to‘plamni k ta elementli to‘plamga yangi (k+1) -elementni kiritish yordamida h osil qilish mumkin. Bu (k+1) -elementni k elementli to‘plam uchun barcha k! ta o‘rin almashtirishlarning h ar biriga quyidagicha (k+1) xil usul bilan kiritish mumkin: 1-elementdan oldin, 1-va 2-elementlar orasiga, 2-va 3-elementlar orasiga, ................................................ 2 “En faktorial” deb o‘qiladi; faktorial so‘zi lotincha “factor” so‘zidan olingan bo‘lib, ko‘paytuvchi ma’nosini anglatadi. 3 Kristian Kramp (Christian, 1760-1826) – olmon matematigi. Asosiy ishlari kombinatorika, geometriya va algebraga ba g‘ ishlangan.

(k−1)-va k -elementlar orasiga, k -elementdan keyin. Shunday qilib, ko‘paytirish qoidasi ga binoan, (k+1) ta elementli to‘plam uchun jami k!(k+1)=(k+1)! ta o‘rin almashtirishlar hosil bo‘ladi, ya’ni Pk+1=(k+1)! . 1- m i s o l . Besh nafar tomoshabinlarning beshta o‘rinni egallash imkoniyatlari (variantlari) sonini toping. Agar tomoshabinlarni a,b,c,d,e harflar bilan belgilasak, u holda T={a,b,c,d,e} tomoshabinlar to‘plamiga ega bo‘lamiz. Tomoshabinlarni o‘rinlarga joylashtirish imkoniyatlarining (variantlarining) har biriga tomoshabinlar T to‘plami elementlarining qandaydir o‘rin almashtirishi mos keladi. T to‘plam beshta elementli bo‘lgani uchun, 1-teoremaga asosan, P5= 1⋅2⋅3⋅4⋅5= 120 bo‘ladi. Demak, besh nafar tomoshabinning beshta o‘rinni egallash imkoniyatlari soni 120ga teng. 2- m i s o l . Shaxmat bo‘yicha musobaqada har birining tarkibida to‘rt nafar o‘yinchi bo‘lgan ikkita komanda ishtirok etmoqda. Har bir komanda rahbariga to‘rtta shaxmat taxtasida o‘yinlar o‘tkazish uchun o‘yinchilarni ixtiyoriy ravishda tartiblash imkoniyati berilgan. Musobaqa qatnashchilarining shaxmat taxtalarini egallash imkoniyatlari (variantlari) sonini toping. H ar bir komanda a’zolari uchun shaxmat taxtalarini egallash imkoniyatlarini Pn=n! formula yordamida hisoblash mumkin: Р4=4!=24 . Komandalardagi o‘yinchilarni ixtiyoriy ravishda tartiblash mumkin bo‘lganligidan, ko‘paytirish qoidasiga ko‘ra, musobaqa qatnashchilarining shaxmat taxtalarini egallash imkoniyatlari (variantlari) soni 24 ⋅24 =576 bo‘ladi . 2. O‘rinlashtirishlar. n ta elementli {a1,a2,a3,...,an} to‘plam berilgan bo‘lsin. Shu to‘plamning ixtiyoriy m ta elementidan hosil qilingan tartiblangan ¿ ¿ tuzilmaga (kombinatsiyaga) n ta elementdan m tadan o‘rinlashtirish deb ataladi. Bu ta’rifdan ko‘rinib turibdiki, elementlari soni bir xil bo‘lgan ikkita h ar xil o‘rinlashtirishlar bir-biridan elementlari bilan yoki bu elementlarning joylashish tartibi bilan farq qiladilar. Bundan tashqari, n ta elementdan m tadan o‘rinlashtirishlar uchun m≤ n bo‘lishi h am ravshan. Bu yerda qaralayotgan

o‘rinlashtirishlar tarkibidagi elementlarning takrorlanmasligini eslatib o‘tamiz. Shu sababli bunday o‘rinlashtirishlar ni betakror ( takrorli emas ) o‘rinlashtirishlar deb ham atash mumkin. Ushbu bobning 4- paragraf ida takrorli o‘rinlashtirish lar ko‘riladi. Berilgan n ta elementdan m tadan o‘rinlashtirishlar soni, odatda, An m bilan belgilanadi 4 . Ravshanki, berilgan n ta a1,a2,a3,...,an elementlardan bittadan o‘rinlashtirishlar n ta bo‘ladi (bular: a1 ; a2 ; va hokazo, an ), ya’ni An 1=n . n ta elementdan bittadan o‘rinlashtirishlar yordamida n ta elementdan ikkitadan o‘rinlashtirishlarni quyidagicha tuzish mumkin. n ta elementdan bittadan o‘rinlashtirishlarning har biridagi elementdan keyin yoki oldin qolgan (n−1) ta elementlardan ixtiyoriy bittasini joylashtirsa bo‘ladi. Natijada, ko‘paytirish qoidasiga binoan, jami soni An 2= n(n−1) ta bo‘lgan n ta elementdan ikkitadan o‘rinlashtirishlarni h osil qilamiz. Shu kabi, n ta elementdan uchtadan o‘rinlashtirishlarni hosil qilish uchun n ta elementdan ikkitadan o‘rinlashtirishlarga murojaat qilish mumkin. Bu yerda n ta elementdan ikkitadan o‘rinlashtirishlarning har biri uchun uni tashkil etuvchi ikkita elementlardan oldin, elementlar orasiga yoki elementlardan keyin qolgan (n−2) ta elementlardan ixtiyoriy bittasini joylashtirish imkoniyati bor. Ko‘paytirish qoidasiga ko‘ra natijada jami soni An 3=n(n−1)(n−2) ta bo‘lgan n ta elementdan uchtadan o‘rinlashtirishlarni h osil qilamiz. Shunga o‘xshash mulohaza yuritib, n ta elementdan to‘rttadan, beshtadan va hokazo o‘rinlashtirishlar soni uchun mos ifodalarni aniqlash qiyin emas. 2- t e o r e m a . n ta elementdan m tadan o‘rinlashtirishlar soni eng kattasi n ga teng bo‘lgan m ta ketma-ket natural sonlarning ko‘paytmasiga tengdir, ya’ni An m=n(n−1)...(n−m+1) . I s b o ti . n – ixtiyoriy natural son bo‘lsin. Teoremani isbotlash uchun matematik induksiya usulini qo‘llab, teorema tasdig‘ining n dan oshmaydigan ixtiyoriy m natural son uchun to‘g‘riligini ko‘rsatamiz (ya’ni induksiyani m bo‘yicha bajaramiz). 4 Fransuzcha “arrangement” so‘zi o‘rinlashtirish ma’nosini beradi.