1. Негізгі әдебиеттер тізімі

1. Гмурман В.Е. теория веоятностей и математическая статистика.-М: ВШ,2006г.477с.

2. Гмурман В.Е. руковдство к решению задач по теории вероятностей и математической статистике.-М: ВШ,2007 г.477с.

3. Жаңбырбаев Б.С., Ықтималдықтар теориясы мен математикалық статистика элементтері.-Алматы: Мектеп, 1988.188 б.

4. Бекетаев Қ. Ықтималдықтар теориясы мен математикалық статистика.-Алматы: рауан, 1991ж. 432 б.

5. Ширяев А.Н. Вероятност-Москва: Мектеп, 1989 ж. 640с.

6. Розанов а. Лекция по теории вероятностей и ее приложения.-М.,наука,1986.

7. Феллер В. Введение в терию вероятностей и ее приложения. Том I,II – М.,Мир,1984.

2. Қосымша әдебиеттер тізімі

1. Ширяев А.Н.Вероятность.-М.:1989.

2. Розанова А.Леккция по теории вероятностей. М.: Наука 1986.

3. Феллер В.Введеня в теории вероятностей иее приложения.М.:Наука 1986.

4. Ширяев А.Н. Вероятность.-М.: Наука,1989.

5. Агапов Г.И.Задачник по теории вероятностей.-М.:Наука,1986.

6. Ақпараттар теориясының негізгі ұғымдары.

№ 3.Дәріс тақырыбы: Комбинаторикалық элементтер.

Жоспары.

1. Ықтималдықтарды есептеуге арналған комбинаторика элементтері.

2. Тәуелсіз оқиғалар.

3. Алгебра және жиындардың -алгебрасы.

4. Ықтималдықтар теориясының аксиомалары.

Ықтималдықтарды есептеу тәсілдері. Кез келген А оқиғасының ықтималдығын классикалық анықтама бойынша есептеу үшін А-ға тиісті нүктелердің (А оқиғасына «қолайлы жағыдайлардың») санын барлық нүктелер (барлық «жағыдайлар») санына бөлуіміз керек. Бұл коьбинаторика ережелерін қолдану арқылы жеңіл жүргізіледі.

Комбинаторика – математика тарауларының бірі. Мұнда шекті жиын элементтерінің түрлі қосылыстары, басқаша айтқанда, әр қилы конфигуралары қарастырлып, олардың сандары салалары саналарды жәнеде есептеледі.Теориялық зерттеу тұрғысынан алғанда комбинаторика алғаш рет XVII ғасырдағы Паскаль, Ферма, Леибнис, және XVIII ғасырдағы Я.Бернулли, Эйлер еңбектерінде қарастырлған. Ұлы математиктердің бұл шығармаларында комбинаторикалардың бір жағынан алғанда тұрмыстың сан алуан мұқтаждарына байланысты болса, ал екінші жағынан алғанда, математиканың өз ішіндегі дамуларымен шектесіп жатыр.

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

1. Элементерінің парлары.r және s элементтерден тұратын А={α ₁,...,α _r} мен В={b ₁,...,b _s} жиындарының әрқайсысынан бір–бірден элемент алып жасалған және де бірінші орында a_i А элементі, ал екінші орында b_j B элементі жазылған (a_i, b_j) қосылыстарын парлар деп атайды. Мұндай барлық парлардың саны rs көбейтіндісіне тең.

Шынында да, А және В жиындарының элементтерінен жасалған (a_i, b_j) пары i- ші жатық жол мен j-ші тік жолдың тіктөртбұрышты таблица құрамыз. Мұндай таблицада парлардың әрқайсысы бір-ақ рет кездеседі, бұдан келіп барлық парлардың саны rs көбеитіндісіне тең болатындығы шығады.

Мысалдар.

1. Екі ойын сүиегін лақтырғанда барлық жағыдайлардың саны қанша?

Шешуі. Екі ойын сүйегін лақтырғанда бірінші сүйекте түскен ұпай i, екінші сүйекте түскен ұпай j болсын. Сонда тажирбенің нәтижесі (i ,j) парлары болады, мүндағы i де, j де 1, 2, 3, 4, 5 ,6 мәндерінің бірін қабылдайды. Сөйтіп, барлық жағыдайлардың саны парлардың принципі бойынша n = 6 · 6 = 36.

2. Ұтысқа қатынасатын ақшалай –заттай лотерея билеттерінің бір-бірінен айырмашылығы серия және билет нөмірлерінде. Серия нөмірлерінің саны n₁-ге, билет нөмірінің саны n₂-ге тең болса, онда ұтысқа қатысатын лотерея билетінің саны n= n₁ n₂ көбейтіндісіне тең.

Ескерте кетелік, егер А жиынының әрбір элементіне В жиынының барлық элементері сәйкес келетіндей қосылыс жасалса, онда бұндай қосылыстар саны n(А)·n(В) көбейтіндісіне тең. Парлар принсипі есеп шығарғанда, міне, осылай қолданлады. Бұл жерде n(А) және n(В) арқылы А және В жиындарының элементтерінің санын белгілеп отырмыз. Шекті А жиынының элементтерінің санын бұдан былай n(А) арқылы белгілейміз.

2. Комбинаториканың негізгі принсипі. Әр қайысы шеткі А₁,А₂,...,А_r жиындары берілсін. Осы жиындардың жазылу нөмірлеріне қарап, бұл міндетті түрде, бір-бірлеп a_n1 А₁, a_n2 А₂,..., a_{n r} А_r элементтерін алалық. Осындай тартіппен алынған a_n1 , a_n2 ,..., a_{n r} элементерін кортеж деп атайды және оны былай жазады. .

Теорема. (Көбейтіндінің теорамасы). А₁,А₂,...,Аr ;жиындарының элементерінен жасалған барлық кортеждердің саны n(A₁) n(A₂)…n(A_r) көбейтіндісіне тең.

Дәлелдеу; Толық математикалық индукция әдісін қолданамыз. Индукцияны r бойынша жүргіземіз. r = 2 болсын. А₁₌{а₁,а₂,…, } және А₁₌{b₁,b₂,…, } деп белгілейік. А_1, b А₂ элементерінен кортежін құрайық. Сонда кортеж парға айналады. Сөйтіп мұндай кортеждердің саны п(А₁)·п(А₂) көбейтіндісіне тең. Сонымен, r = 2 үшін теорема дәлелденді. Енді теореманы r = 1 үшін орынды деп ұйғаралық. Сонда А₁,А₂,...,А_r-1 жиындарының барлық элементтерінен жасалған кортеждердің саны n(A₁) · (A₂)…n(A_r-1) көбейтіндісіне тең болады. Енді (A₁), (A₂),…,(A_r-1) және А_r жиындарының элементтерінен кортежді былай жасаймыз: ((а ,а ,...,а ),а ). Парлар принципі бойынша мұндай кортеждер саны үшін n(A₁) п(A₂)…n(A_r-1) п(А_r)= =n(A_r-1) п(А_r) теңдігі келіп шығады. Теорема толық дәлелденді.

Мысалдар.

1. Бірде-бір цифры қайталанбайтын төрторынды сандардың саны қанша?

Шешуі. Төрторынды санды (i, j, r, l) кортежі деп қарастырамыз. i-дің орныда 1,2,3,4,5,6,7,8,9 цифрларының бірі тұра алады. j-дің орынында қалған 9 цифрлардың біреуі тұра алады, өйткені бұл жерде нольде болуы мұнкін. Сондай ақ r және I-дің орынында тұра алатын цифрлардың саны -8 және 7. Сөйтіп, көбейтіді теоремасы бойынша әр түрлі және цифрлары қайталанбайтын төрторынды сандардың саны n=9·9·8·7= 4536.

2. Телефон станциясы төрт цифрдан тұратын номері бар телефон аппараттарын қамтамасыз етеді. Станция жабдықтайтын барлық аппараттар саны қанша ?

Шешуі. Әрбір аппараттар номерін (i, j, r, l) кортежі деп қарастыруға болады. i, j, r, l элементері цифрлардың қайсын болса да қабылдай алады. Демек, барлық телефон аппараттарының саны n=10·10·10·10=10000.

Кейбір оқулықтарда «кортеж» дегеннің орнына «бір-бірлеп алынған комбинатция» деп те атайды.

3.Терулер. n элементтерден тұратын М жиынын қарастыралық. n

элементтен r-дан жасалған теру деп М жиынының r элементен тұратын ішкі жиынын айтады. Бұл анықтама бойынша, сөйтіп, теру бір-бірінен өзгеше болу үшін оларды жасап тұратын элементтерінің ең болмағанда біреуінде өгешелік болу керек. Мәселен, {1,2,3} және {1, 3, 2} бір ғана теру, өйткені бұлардың элементтерінің арасында ешбір айырмашылық жоқ. n элементен k-дан жасалған терулердің саны үшін белгілеуі қолданлады. Бұны оқиғада «n элементен r-дан жасалған теру саны» деп оқиды.

1-ден бастап n-ге дейін натурал сандардың көбейтіндісі үшін n! (эн факториал) белгілеуі енгізледі. Сөйтіп, n!=1·2·...·n.

Дәлелдеуін келтірмей-ақ терулердің сандарын есептейтін формулаларды берелік.

= немесе = (4)

мұндағы 0 < r ≤ n.

Мысалдары.

1. n бұрышты көпбұрыштың диагональдарының санын табу керек.

Шешуі. Көпбүрыштың төбелерінің саны n-ге тең. Төбелердің кез келген үшеуі бір түзудің бойында жатпайды. Ал, кез-келген екі нүктені кесінділермен қосуға болады. Сол кесінділердің ішінде n кесінді көп бұрыштың қабырғалары болады да, қалғандары диагональдар жасайды. Сондықтанда диагональдар саны

- n = - n =

3. Спортлото (49-дан 6) ойынына қатысушы бір билетті сатып алып,

ұтысқа қатысу үшін оны толтырған. Сонда әр түрлі жағдайлардың саны қашан?

Шешуі. Спортлото ойының ережесі бойынша билеттегі 1- ден 49- ға

дейін жазылған натурал сандардың алтауын сызу керек. Ұтысқа қатысу үшін бұл алты санды қандай тәртіппен сызса да бәрібір. Содықтан ізделінді сан

.

Математикада С = 1 теңдігін қабылдауға келісілген.

Теру сандарын есептеу барысында оны жеңілдететін бір формуланы келтірелік: (5)

Мүны дәлелдеп алу (4) формулалар арқылы қиын емес. (5) формуланы пайдаланғанда r > болғаны жөн, әйтпегенде есептеуді ауырлатады.

теру сандарын биномдық коффиценттер деп атайды. Барлық биномдық коффиценттердің қосындысы -не тең. Бұл Ньютон биномының

жіктеуіндегі а мен b-ның орындарына 1-ді қойғаннан келіп шығады.

Сонымен, мынандай қортындыға да келейіе; n элементтерден тұратын жиыннның барлық ішкі жиындарының саны -не тең.

4. Орналастырулар. Түрлі комбинаторикалардың ұғымын енгізудің бірнеше жолы бар. Орналастырулар үшін де осылай жазуға болады. Ықтималдықтарды есептеуге қолайлылығын пайдаланып, орналасулар ұғымын кортеждер арқылы берелік.

n элеиенттен тұратын М={a₁,a₂,…,a_n } жиынынан r көлемді кортеж құралық. Бұл жерде «r көлемді кортеж» деп отырғанымыз кортежге енетін элементтердің саны r-ға тең болатындығын көрсетеді. М жиынынан ( ) кортежі екі түрлі әдіспен жасауы мүнкін; бірі-кортежге М жиынының бір элементі бірнеше рет кіруі мүнкін. Бірінші жағыдайда кортеждерді n элементтен r-дан жасалған орналасулар деп, екінші жағыдайда кортеждерді n элементтен r-дан жасалған қайталамалы орналасулар деп атайды.

Теорема. n элементтен r-дан жасалған орналастырулар саны n(n-1)(n-2)…(n-r+1) көбейтіндісінде, ал қайталамалы орналастырулар саны n^r-не тең.

Дәлелдеу. Былай орналастыруларды былай жасап шығайық; алдымен М жиынынан элнментін аламыз; содан кейін қалған n-1 элементтердің ішінен элементін аламыз. Кортеж элементерін тағы да сол сияқты біртіндеп ала отырып, ақырында қалған n-(r-1) элементтің ішінен элементін аламыз. Сөйтіп,( , ..., ) кортежі шығады. Сонда, көбейтіндінің теорамасы бойынша, барлық кортеждердің саны n(n-1)…(n-r+1) көбейтіндісіне тең болады. Теораманың бірінші бөлігі дәлелденді. Енді, қайталамалы орналастыруларды жасап шығалық; алдымен М жиынынан элементін аламыз да, оны тіркеп болғаннан кейін М жиынын қайта оралтамыз; содан кейін М жиынынан тағы да элементін аламыз және оны тіркелгеннен кейін қайтарамыз; Міне, осы процесті қайталай отырып, ( , ..., ) кортежін жасап шығарамыз. Сонда, көбейтіндінің теорамасы бойынша мұндай кортеждердің саны n·n·…n=n^r-не тең болады. Теорема толық дәлелденді. п элементтен r-дан жасалған орналастырулар саны үшін , ал қайталамалы орналастырулар үшін белгілеулерін енгізсек:

=n(n-1)…(n-r+1)= , (6)

(7)

Мысалдар.

1. Үш ойын сүйегін лақтырғанда қанша жағыдайлар болады?

Шешуі. Үш ойын сүйегін лақтырғанда пайда болатын ұпайлардан (i,j,r)

кортежін жасалық, мұндағы i,j,r 1,2,3,4,5,6 сандардың біреуін қабылдай алады. Сондықтан, ізделінді сан (7) формула бойынша 6³=216-ға тең, өйткені мұнда п = 6 және r = 3.

Бұл есепті жалпылауға болады. Егер s ойын сүйегін лақтырсақ онда

барлық жағыдайдың саны -не тең болар еді. Сол сияқты r теңгелы ні лақтырғанда барлық жағыдайлар саны -не тең.

2. 7 жолаушы бар лифт 10 этаждың әрқайысына тоқтап өтеді. Әрбір

жолаушы қай этаждан түсіп қалам десе бәрі бір. Әрбір этажда бірден артық жолаушы түсіп қалу ықтималдығы қандай?

Шешуі. Тәжирбедегі барлық жағыдайлардың, яғни элементтар оқыйғалардың санын есептеу үшін 7 адамның қайысысы болса да біреуі i-ші этажда түсіп қалуын а арқылы белгілейік. Сода бір жағыдай деп отырғанымыз (а₁,a₂,…,a_n) кортежі болады. Ал бұл қайталамалы орналастыру. (7) формуланы қолданып барлық жағыдайлардың санын табамыз: п = = 10⁷

А арқылы «әр етажда бірден артық жолаушы түсіп қалмайды» оқыиғасын белгілейік. А оқйғасына қолайлы кортеж (а₁,a_2,…,a₁₀) болады, бірақ ол орналастырудың өзі. Демек, (6) формуланы қолданып, қолайлы жағыдайлар санын табамыз: Енді (1) формула бойынша А-ның ықтималдығын есептейміз.

Р(А)= ·10·9·8·7·6·5·4 0.06.

Ықтималдықтар теориясының оқулықтарында «орналастырулар» деген терминнің орынына «таңдамалар» (орысшасы-выборки ) деп те алады.

5. Алмастырулар. n элементен n-нен жасалған орналастыруларды алмастырулар деп атайды. п элементен жасалған алмастырулар санын Р_п арқы белгілейді. Сонымен,

Р_п=n!=1·2·3·…·n. (8)

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

Мысалдар.

1. Жас бала кубиктерді қатар қойып ойнап отырған, ал кубиктерде

А,А,М,Л әріптері жазылған. Сонда АЛМА сөзінің шығу ықтималдығы қандай?

Шешуі. Есептегі тажирбенің элементар нәтижелері оқйға болатындығы

«жас бала» деген сөздермен берілген (сауаты жоқ деген мағнада, басқа жағыдайда тәжирибе нәтижесі қалай болса солай бола алмайды). Тәжирбе нәтижесін төрт әріптен тұрған кортеждер деп қарастыруға болады жане олардың бір-бірінен айырмашылығы әріптердің алыну ретінде. Олай болса, тәжирбенің әрбір натижесі алмастырулар болады. Демек, п = 4! = 24. В арқылы АЛМА сөзінің шығуын белгілелік. Екі «А» әріпінің орынын алмастырғаннан АЛМА сөзі өзгермей қалады. Сондықтан В-ға қолайлы жағыдайлардың саны т = 2! = 2. (1) формула бойынша

Р(В) = = .

2. 0,1,2,3,4 цифрларынан әр түрлі қанша сан жасап шығуға болады?

Шешуі. Берілген цифрлардан көлемі 5-ге тең кортеждер жасалық, бүлардың саны 5! болады. Бұл кортеждер бес орынды сан бола алмайды, өйткені бірінші орында 0 тұрғанда, ол бес орынды сан болмайды. Ал мұндайлардың саны 4!-ге тең. Сөйтіп, ізделінді сандардың саны n = 5!-4! = 120-24 = 96.

(4), (6) және (8) формулалардан теру, орналастыру және алмастыру сандарының арасында =

Байланысы келіп шығады.

6. Жиындарды топтарға жіктеу. Қайталамалы алмастырулар. Алдымен шекті жиындарга байланысты анықтама беріп, бір теорема дәлелдейік.

Анықтама. Егер Е жиынын өзара қиылыспайтын B₁,B₂,…,B_m жиындарының қосын дысы түрінде жазуға болса, яғни

Е = B₁ B₂ … B_m, B_i,B_j = Ǿ, i ≠ j

болса, онда Е жиыны B₁,B₂,…,B_m жиынына жіктеледі.

Теорема. r₁, r₂,…,r_m теріс емес бүтін сандары үшін r₁+ r₂+…+r_m = n болсын. Сонда п элементтен тұратын Е жиынын r₁ элементтен тұратын В₁,r₂ элементтен В₂, тағы сол сияқты r_m элементтен түратын В_m жиындарға жіктеудің барлық тәсілі мынаған тең:

Дәлелдеу. Алдымен Е жиынының r₁ элементті бар В₁ жиынын құрамыз, мұны тәсілімен жасауға болады. Содан кейін қалған n-r₁ элементтердің ішінен r₂ элементті бар В₂ жиынын құрамыз, мұны әдістерімен орындауға болады. Міне осы процестерді жүргізе отырып, ақырында, n-r₁-…-r_m-1 элементтерден r_m элементі бар B_m жиынын жасаймыз. Сонда, көбетіндінің теорамасы бойынша, Е жиынын B₁,B₂,…,B_m жиындарына жіктеу саны

көбейтіндісіне тең. Бұл санды С_п(r₁,r₂,…r_m) арқылы белгілейік (бұдан былай да осы белгілеуді қолданамыз). Сөйтіп,

С_п(r₁,r₂,…r_m)= = · ·…· = (9)

Теорема дәлелденді.

Жиынды жоғарыда көрсеткендей топтарға бөлуге сәйкес камбинаторикалардың бір-қайталамалы алмастырулар анықталады.

Анықтама. а₁ элементі r₁ рет, a₂ элементі r₂ рет, a_m элементі r_m рет кездесетін п = r₁+r₂ +…+ r_m көлемді кортежді n-ші ретті қайталамалы алмастыру деп атайды.

Қайталамалы мұндай алмастырулардың саны үшін С_п (r₁,…,r_m) белгілеуін қолданамыз. Сонда, мына формуланың орынды болуын дәлелдеп алу қиын емес: С_п(r₁,r₂,…r_m)= (9)

С_п(r₁,r₂,…r_m) сандардың полиномдық коэффициенттер деп атайды, өйткені бұл коэффициенттер полиномдық жіктеуге қатынасады, атап айтқанда

(х₁+х₂+…+х_m)ⁿ =

Мысалдар.

1. «Математика» сөзіндегі әріптерді алмастыра отырып, қанша «сөз» жасап шығуға болады?

Шешуі. Әріптерді алмастыра отырып «математйка» сөзіндегі 10 әріптен 10! сөз шығарып алуға болады. Ал, бұл сөздердегі 3 «а», 2 «м», 2 «т» әріптердің орындарын өздеріне сәйкес ауыстырсақ, онда бұл сөздер ешбір өзгермес еді. Сөйтіп, ізделінді сан тең:

С₁₀(3,2,2,1,1,1) = =151200.

2. 9студентті екі, үш және төрторындық 3 бөлмелерге қанша әдіспен орналастыруға болады?

Шешуі. Ізделінді санды былай табамыз:

С₉(2,3,4) = =1260.!!

7. Қайталамалы терулер. п элементтен r-дан жасалған қайталамалы терулер деп әрқайсысы r элементтен тұратын топтарды айтады және де әрбір элемент осы п топтардың біреуіне тиісті. Барлық қайламалы терулер санын арқылы белгілейміз.

Теорема. п элементтен r-дан жасалған қайталамалы терулер саны мына формуламен анықталады:

(10)

Дәлелдеу: Әрбір қайталамалы теруге бір және тек қана бір қайталамалы алмастыру сәйкестіруге болады. Міне осы сәйкестікті қалай орнатуға болатындығын көрсетелік. a, b, c және d элементтерінен aaabbcdddd және abbbbbbbbd терулерін жасалық. Қандай да болмасын бір элемент қанша рет қайталанса, сонша рет I жазамыз, әр түрлі екі элементке сәйкес бірлердің арасында 0 жазамыз; егер белгелі бір элемент теруге қатыспаса, онда 0 жазамыз. Сонда 0 мен 1-лерден жасалған n+k-1 ретті қайталамалы алмастырулары шығады, ал бұларда 0 цифры n -1 рет және 1 цифры k рет кездеседі. aaabbcddd теруіне 111011010111 алмастыруы, abbbbbbbd теруіне 101111111001 алмастыруы сәйкес келеді.

Сонымен ізделінді саны 0 цифры n -1 рет және 1 цифры r рет кездесетін қайталамалы алмастыру санына тең, яғни

=

Енді (4) формуланы ескерсек,

Соңғы екі теңдіктерден (10) шығады.

Мысал: f(x₁, x₂,…, x_n) аналитикалық функциясының r-шы ретті дербес туындылары дифференциалдаудың реттеріне байланысты емес, тек әрбір айнымалы бойынша қанша дифференциалдауға байланысты. Сондықтан, (10) формуланы қолданып, әр түрлі r-шы ретті дербес туындылардың саны болатындығын көреміз. (5) формуланы пайдаланып, бұл санды түрінде де жазуға бола ды.

Қайталамалы терулерді анықырақ түсіну үшін бір ескерту жасалық. n элементтен r-дан жасалған қайталамалы теруде белгілі бір элемент қанша рет енетіндігін ғана еске алынады. Мысалы, a, b, c, d төрт элементінен 8-ден жасалған aaabbcdd, abadcdd, dcbdabaa терулерінің бәрі бірдей, өйткені бұлардың бәрінде де «a» әрпі үш рет, «b» әрпі екі рет, «c» әрпі бір рет, «d» әрпі екі рет еніп тұр.