Негізгі комбинаториканың объектілері
жүктеу/скачать 91,25 Kb.
|
Негізгі комбинаториканың объектілері
- Бұл бет үшін навигация:
- Комбинаторика ұғымы
- Орынауыстырулар
- Алмастырулар
|
Негізгі комбинаториканың объектілері. Комбинаторика ұғымы Орынауыстырулар Алмастырулар Терулер Комбинаторика ұғымы Саны шектеулі элементтерден әр түрлі комбинациялар құрастыруға және белгілі бір ереже бойынша құрастырылған барлық мүмкін комбинациялар санын есептеуге тура келетін жағдайлар жиі кездесіп отырады. Мұндай есептер комбинаторлық есептер, ал оларды шешумен шұғылданатын математика бөлімі комбинаторика деп аталады. Комбинаторикада тек шектеулі жиындар ғана қарастырылады. Математиканың бұл бөлімінің ықтималдық теориясында, басқарушы жүйелер теориясында есептеу машиналарында және ғылым мен техниканың басқа да көптеген салаларында маңызы зор. Біз тек кейбір қарапайым комбинаторикалық есептермен танысамыз. Орынауыстырулар Қайталамалы орынауыстырулар. Қайталамалы орынауыстыруда есеп келесі түрде қойылады: а1,а2,...,аn түрінде берілген n зат бар делік. Осылардан ұзындығы k-ға тең болатын орынауыстырулар құрылады. Мұндай орынауыстырулар n-нен k бойынша алынған қайталамалы орынауыстыру деп аталады. Біртекті элементтері қайталануы мүмкін орынауыстырудың жалпы санын тауып көрейік. Ол үшін { } элементтеріне тең бола-тын жиынын қарастырамыз. Мұндағы барлық қайталамалы орынауыстырулар осы жиындардың көбейтіндісін береді: Тікелей көбейту ережесі бойынша саны | Оны мына түрде белгілейміз: Мысал1. 4 элементтен неше 3 орынды орынауыстыру алуға болады? Шешуі: n=4, k=3. =64 Қайталанбайтын орынауыстырулар. Қайталанбайтын орынауысты-рулар кезінде элементтер қайталанбайды және арқылы белгіленеді. Мұндай орынауыстыруды құру кезінде алдымен бірінші орынға n затты қоямыз, 2-ші орынға n-1 затты қоямыз, сол сияқты k-шы орынға n-k+1 затты қоямыз. Тікелей көбейту ережесі бойынша n-нен бойынша k алынған қайталанбайтын орынауыстырулардың жалпы саны Мысал2. Хоккей турниріне 17 команда қатысады. Алтын, күміс, қола медальдар ұтқан командаларға беріледі. Неше әдіспен медальды бөлуге болады? Шешуі: n=17, k=3. Алмастырулар Алмастырулар. n-нен k бойынша алынған қайталанбайтын орынауыстырулар құру кезінде біз бір-бірінен құрамы немесе элементтерінің реті бойынша айырмашылығы бар ауыстыруларды алдық. Егер барлық n элементтен тұратын, бірақ олар бір-бірінен тек орналасу реті бойынша айырмашылығы бар орынауыстырулар алатын болсақ, ондай орынауыстыру n элементтен алынған алмастыру деп аталады, ал олардың саны арқылы белгіленеді. Pn=n! Мысал3. 1,2,3 цифрларынан неше үш орынды сан алуға болады (цифрлар қайталанбайды)? Шешуі Pn=3!=6. Қайталамалы алмастырулар. Мульти жиын әр түрлі к зат бар дерлік бір типті, екінші типті және т.с.с к-сыншы типті элементтен неше алмастыру алуға болады. Мыс : М={ a,a,a,b,b,c,d,d,d,d } М мульти жиынын қарастырайық, мұнда а – элементі 3, b - элементі 2, с- элементі 1, d – элементі 4. Мульти жиын бұл да жиынның түрі, бірақ онда бірдей элементтер болуы мүмкін. Элементтің қайталануын басқа да әдіспен көрсетуге болады. Олай болса қайталамалы алмастыру бұл мульти жиын элементімен алмастыру. Егер М жиынның элементтері ір түрлі болып және оларды х индекстеп қойсақ М = { }, онда он болатын еді. Бірақ олардың индекстерін алып тастағанда бірдей элемент бар екенін көреміз. М жиынында әрбір алмастыру 3!*2! *1! *4! кездескен болар еді. Сондықтан М жиынында алмастыру саны Сонымен мультижиынындағы қайталамалы алмастыру мынадай полиноминалды коэффицентке тең: Қайталамалы алмастыру терумен тығыз байланысты: Мысалы: Уссуру сөзіндегі әріптерді алмастырып неше сөз алуға болады ? P (2c, 3y,1p)= 6!/(2!*3!*1!)=60 Терулер Терулер. n әртүрлі элементінен элементті теру деп осы элементтерден тұратын және бір-біріненэлементтердің реті бойынша емес, тек құрамы бойынша айырмашылығы бар ұзындығы k-ға тең барлық мүмкін болатын орынауыстырулар аталады. Терудің жалпы саны белгіленеді. Оның формуласы төмендегідей болады: Және де терулер үшін мына формула орындалады: Мысал4. Топта 25 студент бар. Неше тәсілмен кезекшілікке 4 адамды бөлуге болады? Шешуі: n=25, k=4. Қайталамалы теру. Әртүрлі n зат бар делік. Әр түрінің элементтерінің саны шектеусіз болсын. Егер элементтердің ретін ескермесек, онда ұзындығы m-ға тең бірнеше ауыстыру жазуға болады. Мұндай ауыстырулар қайталамалы теру деп аталады және ол төмендегі формуламен есептеледі: Cnm= Мысал5. 3 бала бақтан 63 алма жинады. Неше әдіспен олар алманы өзара бөліп алуы мүмкін? Шешуі: n=3, m=63 жүктеу/скачать 91,25 Kb. Достарыңызбен бөлісу:
|