Комбинаторика элементтері

Жұмыс түрі: Реферат
Тегін: Антиплагиат
Көлемі: 11 бет
Таңдаулыға:

Қазақстан Республикасының ғылым және білім министрлігі
Қарағанды мемлекеттік техникалық университеті

Реферат

Тақырыбы: Комбинаторика элементтері

Қабылдаған: Абилдаева Г.Б.
Орындаған: Балкаева М.Г.

Қарағанды 2019

Мазмұны
Кіріспе.
Комбинаторика.
1. Қосынды және көбейтінді ережелері
2. Алмастырулар.
3. Қайталанбайтын орналастырулар.
4. Қайталанбалы орналастырулар.
5. Қайталанбайтын алмастырулар.
6. Қайталанбалы алмастырулар.
7. Қайталанбайтын терулер.
8. Қайталанбалы терулер.
Пайдаланған әдебиеттер

Кіріспе

Комбинаторикалық ұйғарту адамның математикалық мәдениетінің компоненттерінің бірі болады. Шынында да математиканың қандай саласы болса да оның комбинаторикаға байланысты есептері табылады. Сондықтан студенттердің комбинаторикалық ұйғарту қабілетін дамыту маңызды мәселе болады. Осы жұмыстың мақсаты: комбинаториканың негіздерін беру, оқиғалардың ықтималдығын табу.

Комбинаторика
Комбинаторика ақырлы жиындардың құрастыру әдістерін зерттейді. Комбинаторика екі түрлі есептерді зерттейді: таңдау есептерін және орналастыру есептерін.
Таңдау есептерінде берілген жиыннан элементтерді таңдап алудың ережелері анықталады.
Орналастыру есептерінде берілген элементтерден жаңа жиындар құралады.
Кез келген жағдайда комбинаторикалық конфигурациялардың құрастырылуымен байланысты болады, сондықтан комбинаторикалық конфигурациялардың бар болуы, конфигурация санын зерттеу, құрастыру алгоритмі сияқты мәселелерді шешуге тура келеді.
Комбинаторикалық конфигурациялардың негізгі түрлеріне мыналар жатады: біріктіру, алмастырулар, терулер, орналастырулар, композициялар, бөліктеулер.

Қосынды және көбейтінді ережелері
Қосындылар ережесі. Егер a заты m тәсілмен таңдап алынатын болса, ал b заты басқа n тәсілмен таңдап алынса, онда "немесе a, немесе b" таңдауын m + n тәсілін таңдап алуға болады.
Бұл ережені басқаша былай айтуға болады. A және B - ақыры жиындар болсын. Онда n(A È B) = n(A) + n(B).
N(A) бірнеше жиындар үшін бұл ереже былай жалпыланады. Егер X1, X2,..., Xk - қос қостан қиылыспалы ақыры жиындар болса, онда n(X1È...È Xk) = n(X1) +...+ n(Xk).
Мысал.Дүкенде 6 түрлі шоколад кәмпит және 10 түрлі карамель кәмпит бар. Кәмпиттің бір түрін неше тәсілмен сатып алуға болады?
А және В - шоколад және карамельді кәмпиттердің жиыны болсын. Бұл жиындар қиылыспайды, сондықтан n(A ÈB) = n(A) + n(B) = 6 + 10 = 16. Кәмпиттің бір түрін 16 тәсілмен сатып алуға болады.
Көбейтінділер ережесі. Егер А заты m түрлі тәсілмен таңдап алынатын болса және осындай әр таңдаудан кейін В заты n тәсілмен таңдап алынса, онда "a және b" таңдауын mxn тәсілмен таңдап алуға болады.
Бұл ережені басқаша былай айтуға болады. A және B - ақырлы жиындар болсын. Онда n(A'B) = n(A) x n(B).
Бірнеше жиындар үшін бұл ереже былай жалпыланады.
Егер X1, X2,..., Xk - ақырлы жиындар болса, онда n(X1'...' Xk) = n(X1)x ...x n(Xk).
Есеп. А пунктен В пункт арқылы С пунктқа дейін маршруттар санын табу керек. А-дан В-ға дейін 5 жол бар, В-дан С-ға дейін 3 жол бар.
Екі жиынды қараймыз S = {s1, s2, s3, s4, s5} - A-дан B-ға баратын жолдар, T = {t1, t2, t3} - B-дан C-ға баратын жолдар. Енді A-дан C-ға баратын жолды (si, tj) түрінде көрсетуге болады, мұнда i = 1, 2,3,4,5; j = 1, 2, 3. Онда, S ' T - A-дан C-ға баратын барлық жолдардың жиыны
n(S ' T) = n(S) x n(T) = 5x3 = 15.

Алмастырулар
n- дәрежелі алмастыруы деп n түрлі заттардың белгілі бір ретте орналастыруын айтады.
Бізге заттардың орналасуы ғана қажет, сондықтан 1 2...n сандардың алмастыруын қарастырамыз. n- дәрежелі алмастырулар саны Pn деп белгіленеді.
n = 1, n = 2, n = 3 болғанда 6 алмастыру бар: 123, 132, 213, 231, 312, 321.
Теорема. n- дәрежелі алмастырулар саны n!-ға тең.
Дәлелдемесі n саны индукциясымен дәлелдейміз. n = 1 болғанда жалғыз ғана алмастыру бар: сондықтан P1 = 1! теңдігі орындалып тұр.
Pn = n! деп болжайық, және 1, 2,..., n, n + 1 сандарының алмастыруын қарастырайық.
n + 1 санын басқа n сандарының ішінде бірінші, екінші, ..., n-ші және (n + 1)-ші орынға қоюға болады. Осы нұсқаулардың әрбіреуінде nсандарын, индукцияның болжамы бойынша, n! тәсілімен орналастыруға болады. Бұдан, (n + 1) сандарын (n + 1)xn! тәсілмен орналастыруға болады. Осылайша, Pn+1 = (n + 1)!
Математикалық индукция принципі бойынша Pn = n! формуласы кез келген натурал n үшін орындалады.
Мысал 1. 6 адамды бір қатарға қанша тәсілмен отырғызуға болады?
6 адамның әрбір орналасуы ол 6-дәрежелі алмастыру, сондықтан 6 адамның бір қатарға орналастыру тәсілдер саны 6-дәрежелі алмастырулар санына тең: 6!
Мысал 2. 6 адамды неше әдіспен дөңгелек үстел басына отырғызуға болады?
6 адамды 6! әдіспен дөңгелек үстел басына отырғызуға болады. 6 адамның бәрін бір орынға жылжытатын болсақ, онда олардың орналасуы өзгермейді, өйткені әрбір адамның көршілері сақталады. Дөңгелек үстел басындағы 6 адамды 6 рет жылжытуға болады. Сондықтан дөңгелек үстел басына 6 адамды = 5! тәсілмен отырғызуға болады.
Кейбір есептерде берілген дәреженің барлық алмастыруларын талап етеді. Әдістердің бірі - лексикографикалық (сөздік) ретпен тізбектеу.
A = a1a2...an және B = b1b2...bn алмастырулары берілсін. Кейбір i, 1 Pound i n үшін ai = bi және ai+1 bi+1 болса, онда лексикографикалық ретте A B деп есептеледі.
Лексикографикалық ретте бірінші алмастыруы 1, 2..., n болып, ал соңғысы n, (n - 1),..., 2, 1 алмастыру болады.
Лексикографикалық ретте алмастыру алгоритмі.
1) Бірінші 1, 2,..., n алмастыруы құрылады.
2) Ағымдағы a1a2...an алмастыруда ai+1 ...an және ai ai+1 максимальді азаятын суффикс бар болады.
3) Егер i = 0 болса, онда ағымдағы алмастыру соңғы болады. 7-ші пунктке көшу керек.
4) Егер i 0 болғанда ai+1 ... an сандары ішінен aj санынан үлкен, ең кіші ai саны ізделеді.
5) ai және aj сандарын орындарымен ауыстырамыз: ajai+1...aj...an
6) ajai+1...aj...an сандарын өспелі ретпен орналастырамыз. Шыққан алмастыруды шығарамыз.
7) Алгоритм соңы.
Мысал 3. (Максимальді өспелі іштізбек туралы есеп). a1, a2,..., an алмастыруы берілген. , ,..., іштізбек өспелі болатындай 1 Pound i1 i2 ... ik Pound n тізбекті табу керек.
a1, a2,..., an тізбекті кему қасиеттері бар I1,..., Is жиыншаларға бөлеміз. It жиыншасы "кему" қасиетіне ие болады, егер кез келген i, j Î Itүшін ai aj теңсіздік орындалатын болса. Басқа сөзбен айтқанда a1, a2,..., an тізбек кемімелі іштізбектерге бөлінеді.
Бұдан ұзындығы s-ке тең өспелі тізбек құрастырылады. Ол It жиындардың әрбіреуінің бір элементінен тұратын болады. s k-ның максимальді мүмкін мәні болады.
Шынымен, өспелі іштізбектің ұзындығы s-тен аспау керек: бұл іштізбек әрбір It жиыншасының бір элементінен артық тұра алмайды.
Алмастыруды кемімелі іштізбекке бөлуді ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.