Бұл мақалада комбинаторика деп аталатын математиканың арнайы бөліміне назар аударылады. Формулалар, ережелер, есептерді шешу мысалдары - мұның барлығын мақаланы соңына дейін оқу арқылы таба аласыз.
Сонымен бұл бөлім не? Комбинаторика кез келген объектілерді санау мәселесімен айналысады. Бірақ бұл жағдайда нысандар қара өрік, алмұрт немесе алма емес, басқа нәрсе. Комбинаторика бізге оқиғаның ықтималдығын табуға көмектеседі. Мысалы, карта ойнаған кезде, қарсыластың қозырының болу ықтималдығы қандай? Немесе мұндай мысал - жиырма шардан тұратын қапшықтан дәл ақ түс алу ықтималдығы қандай? Дәл осындай тапсырмалар үшін біз кем дегенде математиканың осы бөлімінің негіздерін білуіміз керек.
Комбинаторлық конфигурациялар
Комбинаториканың негізгі ұғымдары мен формулалары мәселесін қарастыра отырып, комбинаторлық конфигурацияларға назар аудармай кете алмаймыз. Олар тұжырымдау үшін ғана емес, сонымен қатар әртүрлі комбинаторлық есептерді шешу үшін де қолданылады. Мұндай үлгілердің мысалдары:
- орналастыру;
- орналастыру;
- комбинация;
- сан құрамы;
- бөлінген сан.
Алғашқы үшеуі туралы толығырақ кейінірек айтатын боламыз, бірақ бұл бөлімде композиция мен бөлуге назар аударамыз. Олар белгілі бір санның құрамы туралы айтқанда (айталық, а) а санының кейбір оң сандардың реттелген қосындысы ретінде берілуін білдіреді. Ал бөлу ретсіз қосынды болып табылады.
Бөлімдер
Тікелей комбинаторика формулаларына және есептерді қарастыруға өтпес бұрын, математиканың басқа бөлімдері сияқты комбинаториканың да өз бөлімшелері бар екеніне назар аударған жөн. Оларға мыналар жатады:
- санақ;
- құрылымдық;
- төтенше;
- Рэмси теориясы;
- ықтимал;
- топологиялық;
- шексіз.
Бірінші жағдайда біз санамалы комбинаторика туралы айтып отырмыз, есептер жиындар элементтері арқылы құрылған әртүрлі конфигурацияларды санауды немесе санауды қарастырады. Әдетте, бұл жиынтықтарға кейбір шектеулер қойылады (ерекшелік, ажыратылмау, қайталану мүмкіндігі және т.б.). Және бұл конфигурациялардың саны қосу немесе көбейту ережесін қолдану арқылы есептеледі, ол туралы сәл кейінірек айтатын боламыз. Құрылымдық комбинаторикаға графиктер мен матроидтар теориялары жатады. Экстремалды комбинаторика есебінің мысалы ретінде келесі қасиеттерді қанағаттандыратын графтың ең үлкен өлшемін айтуға болады… Төртінші абзацта біз кездейсоқ конфигурациялардағы қалыпты құрылымдардың болуын зерттейтін Рэмси теориясын атап өттік. Ықтималдықкомбинаторика берілген жиынның белгілі бір қасиетке ие болу ықтималдығы қандай деген сұраққа жауап беруге қабілетті. Сіз болжағандай, топологиялық комбинаторика топологиядағы әдістерді қолданады. Соңында, жетінші тармақ – шексіз комбинаторика комбинаторика әдістерін шексіз жиындарға қолдануды зерттейді.
Қосу ережесі
Комбинаторика формулаларының ішінен бізге бұрыннан таныс болған өте қарапайымдарын табуға болады. Мысал ретінде қосынды ережесін келтіруге болады. Бізге екі әрекет (С және Е) берілді делік, егер олар бірін-бірі жоққа шығаратын болса, С әрекеті бірнеше жолмен орындалуы мүмкін (мысалы, а), ал Е әрекеті b-тәсілімен орындалуы мүмкін, онда олардың кез келгені (С) немесе E) a + b тәсілдерімен орындалуы мүмкін.
Теорияда мұны түсіну өте қиын, біз қарапайым мысалмен барлық ойды жеткізуге тырысамыз. Бір сыныптағы оқушылардың орташа санын алайық – жиырма бес дейік. Олардың ішінде он бес қыз, он ұл бала бар. Сыныпқа күнделікті бір кезекші тағайындалады. Бүгінгі күні сынып кезекшісін тағайындаудың неше жолы бар? Мәселені шешу өте қарапайым, біз қосу ережесіне жүгінеміз. Тапсырма мәтінінде тек ұлдар немесе тек қыздар ғана кезекшілікте бола алады деп айтылмаған. Демек, бұл он бес қыздың немесе он ұлдың кез келгені болуы мүмкін. Қосынды ережесін қолдана отырып, біз бастауыш сынып оқушысы оңай жеңе алатын қарапайым мысал аламыз: 15 + 10. Есептеп шыққаннан кейін біз жауап аламыз: жиырма бес. Яғни, бар болғаны жиырма бес жол барбүгін кезекшілік класын тағайындаңыз.
Көбейту ережесі
Көбейту ережесі де комбинаториканың негізгі формулаларына жатады. Теориядан бастайық. Бірнеше әрекетті (а) орындау керек делік: бірінші әрекет 1 тәсілмен, екіншісі - 2 тәсілмен, үшіншісі - 3 тәсілмен және т.б. соңғы а-әрекеті sa тәсілдерімен орындалғанға дейін. Сонда бұл әрекеттердің барлығын (олардың жалпы саны бар) N тәсілмен орындауға болады. Белгісіз N қалай есептеледі? Бұл бізге формула көмектеседі: N \u003d c1c2c3…ca.
Тағы да теорияда ештеңе анық емес, көбейту ережесін қолданудың қарапайым мысалына көшейік. Жиырма бес адамнан тұратын бір сыныпты алайық, онда он бес қыз, он ұл оқиды. Тек осы жолы екі қызметшіні таңдау керек. Олар не тек ұлдар немесе қыздар, не қызбен бірге ұл болуы мүмкін. Мәселенің элементарлық шешіміне жүгінеміз. Біз бірінші кезекшіні таңдаймыз, соңғы абзацта шешкеніміздей, біз жиырма бес ықтимал нұсқаны аламыз. Екінші кезекші қалған адамдардың кез келгені болуы мүмкін. Бізде жиырма бес студент бар еді, біреуін таңдадық, яғни қалған жиырма төрт адамның кез келгені екінші кезекші бола алады. Соңында біз көбейту ережесін қолданамыз және екі көмекшіні алты жүз жолмен таңдауға болатынын табамыз. Бұл санды жиырма бес пен жиырма төртке көбейту арқылы алдық.
Ауыстыру
Енді біз тағы бір комбинаторика формуласын қарастырамыз. Мақаланың осы бөлімінде бізОрын ауыстырулар туралы сөйлесейік. Мәселені бірден мысалмен қарастырыңыз. Бильярд доптарын алайық, олардың n-ші саны бар. Біз есептеуіміз керек: оларды қатарға орналастыру үшін, яғни реттелген жиынтықты жасау үшін қанша опция бар.
Бастайық, егер бізде доптар болмаса, онда бізде де орналастыру опциялары нөлдік. Ал егер бізде бір шар болса, онда орналасу да бірдей болады (математикалық түрде оны былай жазуға болады: Р1=1). Екі шарды екі түрлі орналастыруға болады: 1, 2 және 2, 1. Демек, Р2=2. Үш шарды алты түрде орналастыруға болады (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. Ал егер мұндай шарлар үш емес, он немесе он бес болса? Барлық ықтимал нұсқаларды тізімдеу өте ұзақ, содан кейін комбинаторика көмекке келеді. Орын ауыстыру формуласы біздің сұрағымызға жауап табуға көмектеседі. Pn=nP(n-1). Егер формуланы жеңілдетуге тырыссақ, мынаны аламыз: Pn=n (n - 1) … 21. Ал бұл бірінші натурал сандардың көбейтіндісі. Мұндай сан факториал деп аталады және n деп белгіленеді!
Мәселені қарастырайық. Жетекші күнде таңертең өз отрядын сапқа тұрғызады (жиырма адам). Отрядта үш жақсы дос бар - Костя, Саша және Леша. Олардың бір-бірінің қасында болу ықтималдығы қандай? Сұраққа жауап табу үшін «жақсы» нәтиженің ықтималдығын нәтижелердің жалпы санына бөлу керек. Орын ауыстырулардың жалпы саны - 20!=2,5 квинтиллион. «Жақсы» нәтижелердің санын қалай санауға болады? Костя, Саша және Леша бір супермен делік. Сонда бізБізде он сегіз ғана пән бар. Бұл жағдайда ауыстырулар саны 18=6,5 квадриллион. Мұның бәрі Костя, Саша және Леша бөлінбейтін үштікте ерікті түрде қозғала алады, ал бұл тағы 3!=6 опция. Сонымен, бізде барлығы 18 «жақсы» шоқжұлдыздар бар!3! Бізге тек қажетті ықтималдықты табу керек: (18!3!) / 20! Бұл шамамен 0,016. Процентке айналдырсақ, ол тек 1,6% болады.
Орналасу
Енді біз тағы бір өте маңызды және қажетті комбинаторика формуласын қарастырамыз. Орналастыру - бұл мақаланың осы бөлімінде қарастыруды ұсынамыз. Біз одан да күрделі боламыз. Барлық жиыннан (n) емес, кішіректен (m) мүмкін болатын ауыстыруларды қарастырғымыз келеді делік. Яғни, n элементтің m арқылы ауыстырылуын қарастырамыз.
Комбинаториканың негізгі формулаларын жаттап қана қоймай, түсіну керек. Тіпті олар күрделене түскеніне қарамастан, бізде бір емес, екі параметр бар. m \u003d 1, содан кейін A \u003d 1, m \u003d 2, содан кейін A \u003d n(n - 1) болсын делік. Егер формуланы одан әрі жеңілдетіп, факториалдар арқылы белгілеуге ауыссақ, біз өте қысқа формула аламыз: A \u003d n! / (n - м)!
Комбинация
Комбинаториканың барлық дерлік негізгі формулаларын мысалдармен қарастырдық. Енді комбинаториканың негізгі курсын қарастырудың соңғы кезеңіне – комбинациямен танысуға көшейік. Енді бізде бар n элементінен m элементті таңдаймыз, ал біз олардың барлығын барлық мүмкін тәсілдермен таңдаймыз. Олай болса, бұл тұрудан қалай ерекшеленеді? Біз болмаймызтәртіпті қарастыру. Бұл ретсіз жиын комбинация болады.
Бірден белгілеуді енгізіңіз: C. Біз n-ден m шардың орнын аламыз. Біз тәртіпке назар аударуды тоқтатып, қайталанатын комбинацияларды аламыз. Комбинациялар санын алу үшін орналастырулар санын m-ге бөлу керек! (м факторлық). Яғни, C \u003d A / м! Осылайша, барлығын дерлік таңдауға шамамен қанша тең келетін n шардан таңдаудың бірнеше жолы бар. Бұл үшін логикалық өрнек бар: аз таңдау - бәрін дерлік тастаумен бірдей. Сондай-ақ осы жерде элементтердің жартысын таңдау әрекеті кезінде комбинациялардың максималды санына қол жеткізуге болатынын атап өткен жөн.
Есепті шешу үшін формуланы қалай таңдауға болады?
Комбинаториканың негізгі формулаларын егжей-тегжейлі қарастырдық: орналастыру, ауыстыру және комбинация. Енді біздің міндетіміз комбинаторикадағы есепті шешуге қажетті формуланы таңдауды жеңілдету. Сіз келесі қарапайым схеманы пайдалана аласыз:
- Өзіңізден сұраңыз: есеп мәтінінде элементтердің реті ескерілді ме?
- Егер жауап жоқ болса, онда комбинация формуласын пайдаланыңыз (C=n! / (m!(n - m)!)).
- Егер жауап жоқ болса, сізге тағы бір сұраққа жауап беру керек: комбинацияға барлық элементтер кіреді ме?
- Егер жауап иә болса, ауыстыру формуласын пайдаланыңыз (P=n!).
- Егер жауап жоқ болса, бөлу формуласын пайдаланыңыз (A=n! / (n - m)!).
Мысалы
Комбинаторика элементтерін, формулаларды және басқа да мәселелерді қарастырдық. Енді келесіге көшейікнақты проблеманы қарастыру. Сіздің алдыңызда киви, апельсин және банан бар деп елестетіңіз.
Бірінші сұрақ: оларды қанша жолмен қайта реттеуге болады? Ол үшін ауыстыру формуласын қолданамыз: P=3!=6 жол.
Екінші сұрақ: бір жемісті қанша жолмен таңдауға болады? Бұл анық, бізде тек үш нұсқа бар - киви, апельсин немесе бананды таңдаңыз, бірақ біз комбинация формуласын қолданамыз: C \u003d 3! / (2!1!)=3.
Үшінші сұрақ: екі жемісті қанша жолмен таңдауға болады? Бізде қандай нұсқалар бар? киви және апельсин; киви және банан; апельсин және банан. Яғни, үш нұсқа, бірақ оны комбинация формуласы арқылы тексеру оңай: C \u003d 3! / (1!2!)=3
Төртінші сұрақ: үш жемісті қанша жолмен таңдауға болады? Көріп отырғаныңыздай, үш жемісті таңдаудың бір ғана жолы бар: киви, апельсин және банан алыңыз. C=3! / (0!3!)=1.
Бесінші сұрақ: кем дегенде бір жемісті қанша жолмен таңдауға болады? Бұл шарт бір, екі немесе үш жемісті де алуға болады дегенді білдіреді. Сондықтан біз C1 + C2 + C3=3 + 3 + 1=7 қосамыз. Яғни, дастарханнан кем дегенде бір жемісті алудың жеті жолы бар.
