Дәріс №1 Кіріспе. Жиындар теориясының негізгі ұғымдары. Жиындарға амалдар қолдану
Жиындардың декарттық көбейтіндісі
жүктеу/скачать 1,12 Mb.
|
Лекция дискретка каз
- Бұл бет үшін навигация:
- Бақылаусұрақтары
- Дәріс №3. Комбинаторика. Орынауыстыру және теру
- Комбинаторика ұғымы
- Орынауыстырулар
- 3.Алмастырулар
| Жиындардың декарттық көбейтіндісі
Кортеж ұғымына сүйеніп, екі жиынның декарттық көбейтіндісін анықтауға болады. Ол үшін, шекті екі жиын A={a;b;c} және В={3,5} берілсін. Енді осы жиындардың элементтерінен бірінші компоненті А жиынында, екінші компоненті В жиынында жататын элементтерден тұратын барлық парлардың, яғни ұзындығы 2-ге тең кортеждердің жиынын құрайық. Олар {(а;3),(а;5),(b;3),(b;5),(с;3),(с;5)}. Анықтама. X жиыны мен Y жиынының декарттық көбейтіндісі деп, бірінші компоненті X-ке, екінші компоненті Y-ке жататын элементтерден тұратын барлық парлар жиынын айтады. Екі жиынның декарттық көбейтіндісін X × Y өрнегімен белгілейді. Сонымен X × Y = {(x; у) / xX,уY}. Егер X және Y жиындары тең болса, яғни X = Y, онда X × X декарттық көбейтіндісі компоненттері тек X жиынында жататын элементтерден тұратын, x X, у Y,(х;у)парлардың жиыны болады.Мысалы,егер X={m;п;p},онда
× X = {(m; m),(m; n),( m;р),(п; m),(п;п),(п;р),(р; m),(р;п),(р;р)}. Декарттық көбейтінді үшін коммутативтік, ассоциативтік заңдары орындалмайды, яғни: егер, X = Y, онда X ×Y =Y ×X; егер X,Y және Z жиындарының ешқайсысы бос жиын болмаса, онда X ×(Y ×Z) = (X ×Y) ×Z. Шынында да X × Y жиынының элементтері (х;у) мұндағы x X, у Y парлардан, ал Y × X жиынының элементтері (у;х), мұндағы у Y, x X парлардан тұрады. Ал, (х;у) және (у;х) егер х≠у болғанда, әртүрлі парлар, сондықтан, егер X≠Y болғанда, X × Y≠Y × X. Екі шекті жиындардың декарттық көбейтіндісін таблица түрінде беруге болады, ол үшін тік бағанада Х жиынының элементтерін, горизонталь жолда Y жиынының элементтерін орналастырсақ, онда сәйкес жолдар мен бағаналардың түйіліскен жерінде X × Y жиынының элементтері орналасады. Мына таблицада X = {a;b;c} және Y = {3;5}жиындарының декарттық көбейтіндісі кескінделген.
Сол сияқты, екіден артық жиындардың да декарттық көбейтіндісін табуға болады. Мысалы, Х1;Х2;Х3;...;Хm жиындары берілсін. Осы жиындардың элементтерінен, ұзындықтары m-ге тең болатын, бірінші компоненті Х1 жиынында, екінші компоненті Х2 жиынында, үшінші компоненті Х3 жиынында, т.с.с. m-ші компоненті Хm жиынында жататын элементтерден тұратын барлық кортеждерді құрайық. Осындай кортеждердің жиынын m жиындардың декарттық көбейтіндісі деп атайды, яғни Х1× Х2× Х3×... × Хm= {(х1;х2;х3;...;хm) \х1 Х1,х2 Х2,х3 Х3,...,хm Хm}.Мысалы, A = {a,b,c}, В = {m,k}, С = {е,p} болсын. Сонда А×В×С ={(a‚m‚e),(a‚m‚p),(a‚k‚e),(a‚k‚p),(b‚m‚p),(b‚m‚e),(c‚m‚e),(b‚k‚e),(b‚k‚p), (c‚m‚p),(c‚k‚e),(c‚k‚p)}.
Дискретті математика пәні Жиын дегеніміз не? 3.Жиынның қандай түрлері бар? 4.Жиындарға қандай амалдар қолданамыз? 5.Кортеж
6.Декарттық көбейтінді қалай табылады? Дәріс №3. Комбинаторика. Орынауыстыру және теру Дәріс мақсаты:Комбинаторика ұғымын,оның амалдарымен таныстыру. Кілттік сөздер:комбинаторика,орналастыру,теру,алмастыру,инверсия. Жоспары: Комбинаторика ұғымы Орынауыстырулар Алмастырулар 4.Терулер Комбинаторика ұғымы Саны шектеулі элементтерден әр түрлі комбинациялар құрастыруға және белгілі бір ереже бойынша құрастырылған барлық мүмкін комбинациялар санын есептеуге тура келетін жағдайлар жиі кездесіп отырады. Мұндай есептер комбинаторлық есептер, ал оларды шешумен шұғылданатын математика бөлімі комбинаторика деп аталады.Комбинаторикада тек шектеулі жиындар ғанақарастырылады. Математиканың бұл бөлімінің ықтималдық теориясында, басқарушы жүйелер теориясында есептеу машиналарында және ғылым мен техниканың басқа да көптеген салаларында маңызы зор. Біз тек кейбір қарапайым комбинаторикалық есептермен танысамыз. Орынауыстырулар Қайталамалы орынауыстырулар. Қайталамалы орынауыстыруда есепкелесі түрде қойылады: а1,а2,..., түрінде берілген 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. 3.Алмастырулар Алмастырулар. n-нен бойыншаkалынған қайталанбайтынорынауыстырулар құру кезінде біз бір-бірінен құрамы немесе элементтерінің реті бойынша айырмашылығы бар ауыстыруларды алдық. Егер барлық n элементтен тұратын, бірақ олар бір-бірінен тек орналасу реті бойынша айырмашылығы бар орынауыстырулар алатын болсақ, ондай орынауыстыру n элементтен алынған алмастыру деп аталады, ал олардың саны арқылы белгіленеді. Мысал3. 1,2,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 ) = = = 60 Терулер Терулер. nәртүрлі элементінен элементті теру деп осы элементтердентұратын және бір-біріненэлементтердің реті бойынша емес, тек құрамы бойынша айырмашылығы бар ұзындығы k-ға тең барлық мүмкін болатын орынауыстырулар аталады. Терудің жалпы саны белгіленеді. Оның формуласы төмендегідей болады: Және де терулер үшін мына формула орындалады: . Мысал4. Топта25студент бар.Неше тәсілмен кезекшілікке4адамдыбөлуге болады? Шешуі: n=25, k=4. Қайталамалы теру. Әртүрліnзат бар делік.Әр түрінің элементтерініңсаны шектеусіз болсын. Егер элементтердің ретін ескермесек, онда ұзындығы m-ға тең бірнеше ауыстыру жазуға болады. Мұндай ауыстырулар қайталамалытеру деп аталады және ол төмендегі формуламен есептеледі:
Мысал5. 3бала бақтан63алма жинады.Неше әдіспен олар алманы өзарабөліп алуы мүмкін? Шешуі: n=3, m=63 жүктеу/скачать 1,12 Mb. Достарыңызбен бөлісу:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||