Бул макалада комбинаторика деп аталган математиканын атайын бөлүмү каралат. Формулалар, эрежелер, маселени чечүүнүн мисалдары - мунун баарын бул жерден макаланы аягына чейин окуу менен таба аласыз.
Анда бул бөлүм эмне? Комбинаторика кандайдыр бир объектилерди эсептөө маселеси менен алектенет. Бирок бул учурда объекттер кара өрүк, алмурут же алма эмес, башка нерсе. Комбинаторика окуянын ыктымалдыгын табууга жардам берет. Мисалы, карта ойногондо, каршылашынын козырынын болуу ыктымалдыгы кандай? Же мындай мисал - жыйырма шардан турган баштыктан так ак болуп калуу ыктымалдыгы кандай? Дал ушундай тапшырмалар үчүн биз жок дегенде математиканын бул бөлүмүнүн негиздерин билишибиз керек.
Комбинатордук конфигурациялар
Комбинаториканын негизги түшүнүктөрү жана формулалары жөнүндөгү маселени карап, комбинатордук конфигурацияларга көңүл бурбай коюуга болбойт. Алар формулировкалоо үчүн гана эмес, ошондой эле ар кандай комбинатордук маселелерди чечүү үчүн колдонулат. Мындай моделдердин мисалдары:
- жайгаштыруу;
- пермутация;
- комбинация;
- сандын курамы;
- бөлүнгөн сан.
Биринчи үчөө жөнүндө кийинчерээк кененирээк сүйлөшөбүз, бирок бул бөлүмдө композицияга жана бөлүүгө көңүл бурабыз. Белгилүү бир сандын курамы жөнүндө сөз кылганда (айталы, а) а санынын кээ бир оң сандардын иреттелген суммасы катары көрсөтүлүшүн билдирет. Ал эми бөлүү иретсиз сумма.
Бөлүмдөр
Түздөн-түз комбинаториканын формулаларына жана маселелерди кароого өтүүдөн мурун, математиканын башка бөлүмдөрү сыяктуу эле комбинаториканын да өзүнүн бөлүмчөлөрү бар экендигине көңүл бура кетели. Аларга төмөнкүлөр кирет:
- санак;
- структуралык;
- экстремалдуу;
- Рэмси теориясы;
- ыктималдуу;
- топологиялык;
- чексиз.
Биринчи учурда, кеп сандык комбинаторика жөнүндө болуп жатат, маселелер комплекстердин элементтери аркылуу түзүлгөн ар кандай конфигурацияларды санап чыгууну же эсептөөнү карайт. Эреже катары, бул топтомдорго кандайдыр бир чектөөлөр (айырмалануу, айырмаланбоо, кайталоо мүмкүнчүлүгү ж.б.) коюлат. Жана бул конфигурациялардын саны, биз бир аз кийинчерээк сөз кыла турган кошуу же көбөйтүү эрежеси менен эсептелет. Структуралык комбинаторика графиктердин жана матроиддердин теорияларын камтыйт. Экстремалдык комбинаторика маселесине мисал катары төмөнкү касиеттерди канааттандырган графиктин эң чоң өлчөмү эмнеге барабар… Төртүнчү абзацта биз кокус конфигурацияларда регулярдуу структуралардын болушун изилдеген Рэмси теориясын айттык. Ыктымалдуулуккомбинаторика суроого жооп бере алат - берилген көптүктүн белгилүү бир касиетке ээ болуу ыктымалдыгы кандай. Сиз ойлогондой, топологиялык комбинаторика топологияда ыкмаларды колдонот. Акырында, жетинчи пункт - инфинитарлык комбинаторика комбинаторика ыкмаларын чексиз көптүктөргө колдонууну изилдейт.
Кошуу эрежеси
Комбинаторика формулаларынын ичинен бизге көптөн бери тааныш болгон абдан жөнөкөйлөрүн табууга болот. Мисалы, сумма эрежеси. Бизге эки иш (С жана Е) берилди дейли, эгерде алар бири-бирин жокко чыгарса, С аракети бир нече жол менен аткарылышы мүмкүн (мисалы, а), ал эми Е аракети 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.
Үчүнчү суроо: эки жемишти канча жол менен тандоого болот? Бизде кандай варианттар бар? Kiwi жана апельсин; киви жана банан; апельсин жана банан. Башкача айтканда, үч вариант, бирок муну айкалыштыруу формуласы менен текшерүү оңой: C \u003d 3! / (1!2!)=3
Төртүнчү суроо: үч жемишти канча жол менен тандоого болот? Көрүнүп тургандай, үч жемиш тандоонун бир гана жолу бар: киви, апельсин жана бананды алыңыз. C=3! / (0!3!)=1.
Бешинчи суроо: жок дегенде бир жемишти канча жол менен тандай аласыз? Бул шарт бир, эки же үч мөмөнү тең ала алабыз дегенди билдирет. Ошондуктан, биз C1 + C2 + C3=3 + 3 + 1=7 кошобуз. Башкача айтканда, дасторкондон жок дегенде бир даана жемиш алуунун жети жолу бар.
