Комбинаторика жана ыктымалдуулук теориясынын элементтерин түзүүнүн негизги шарты адамдардын лотереяга, кубиктерге, картага жана башка кокустук оюндарына болгон көз карандылыгы деп айтышат. Кумар оюндары байыркы заманда чоң мааниге ээ болгон. Кээ бирөөлөр байлык, жер, аял алышты. Башкалары болсо, акыркы көйнөгүнө чейин колунда болгондун баарын жоготушту. Чынында эле, тобокелдик оюндардын же туш келди оюндардын таасири орун алган. Бирок, илимдин тез өнүгүшүн кошкондо дагы фундаменталдуу себептер бар эле: эксперименттер, бир катар эксперименттердин жүрүшүн болжолдоо жана натыйжалардагы катаны баалоо зарылчылыгы. Мунун баары жана башка көптөгөн нерселер комбинаториканын жана ыктымалдуулук теориясынын элементтеринин пайда болушуна алып келди.
Бернулли теоремасы
Комбинаторика 17-кылымда Кардано, Паскаль, Галилео, Ферма, Лейбниц, Бернулли сыяктуу илимпоздордун эмгектеринин аркасында пайда болгон деп эсептелет. Алар конкреттүү терминдерди киргизишкенбул илим үчүн бир катар фундаменталдык мыйзамдарды жана комбинаториканын алгачкы формулаларын далилдеген. Мисалы, Бернуллинин теоремасы, анда кокустук менен бири-биринен көзкарандысыз болгон жана бирдей шарттарда канча жолу кайталанышы мүмкүн болгон эксперименттерди жана эксперименттерди гана карап чыгуу керек. Бул теорема комбинаториканын жана ыктымалдуулук теориясынын илим катары андан аркы өнүгүшүн аныктаганы жалпы кабыл алынган.
Жыштыктын туруктуулугу
Комбинаторика элементтерин изилдөөгө өтүүдөн мурун, келгиле, белгилүү бир ойлорду сунуш кылган айкын мисал келтирели – чүкө ыргытуу. Жөнөкөйлүк үчүн бир сөөктү карап көрөлү. Бул алты жактуу куб, анын ар бир тарабы номерленген. Эгерде биз n ыргытуу боюнча бир катар эксперименттерди жүргүзсөк жана Г1 1-саны бар четиндеги тамчылардын саны деп эсептесек, Г2 - саны 2, ж.б.у.с., ыргытуулардын санынын көбөйүшү менен n, жыштыгы Г1/n, Г2 /n, …, Г 6/n, эксперименттин башталышында кокустук сыяктуу көрүнгөн, абдан белгилүү маанилерге ээ. Ал эми жакшы тең салмакталган сөөктөр үчүн ар бир кырдын жыштыгы чоң тактык менен бирдей болот.
Дагы бир мисал – монета эксперименти. Ошентип, илимпоз Пирсон 24 000 тыйын ыргыткандан кийин монетанын бир капталынан түшүү жыштыгы 0,5ке жакындаса, канчалык так болсо, ошончолук көп ыргытылат деген жыйынтыкка келген. Ошентип, ал гербди жоготуу үчүн 0,5005 ыктымалдык алган. Бул принципжыштык туруктуулугу да теориянын негиздеринин бири болуп саналат.
Тарыхый эскертүү
Ыктымалдуулук теориясы жана комбинаторика 20-кылымда эң активдүү өнүккөн. Ал эми бул маселеге орус жана советтик математиктер зор салым кошушту. Алардын арасында, мисалы, Колмогоров, Чебышев, Ляпунов, Марков. Колдонуу чөйрөсүн кыйла кеңейтишти, чоң сандар мыйзамын, борбордук чек теоремасын, ыктымалдуулук теориясынын аксиоматикасын изилдеп, сүрөттөп беришти. Мунун баары бүтүндөй бир илимдин негизи болуп калды. Бүгүнкү күндө физикада, химияда, биологияда жана башка көптөгөн тармактарда, өзгөчө алардын практикалык чөйрөсүндө комбинаториканын жана ыктымалдуулук теориясынын элементтеринин маанисин ашыкча баалоо кыйын.
Комбинаторикалык маселелердин мисалдары
Комбинаторика - бул белгилүү бир шарттарды эске алуу менен кандайдыр бир элементтердин жыйындысынан түзүлгөн мүмкүн болгон комбинациялардын санын баалоо. Бул үчүн керектүү маселени ыңгайлуу жана тез чечүүгө мүмкүндүк берүүчү комбинаторикада формулалар алынган. Бирок бул формулаларды көрсөтүүдөн мурун, келгиле, аларга алып келген суроолордун айрым мисалдарын карап көрөлү.
1-тапшырма. Дүйнө чемпиондугунун плей-офф этабына 16 команда катышууда. Алар өз ара орундарды канча жол менен бөлүштүрө алышат? Мисалы:
- (3, 1, 2, 4..16) - биринчи орунда №3 команда, экинчи орунда №1 команда ж.б.
- (16, 1, 2, 3, 4..15) - биринчи орунда №16 команда, …
- (1..7, 9, 8, 10..16) - команданын биринчи орундарында 1, 2, 3, …
Булардын бардыгы варианттардын мисалдары. Бул маселенин ачык-айкын чечими бардыгын жазуу болуп саналатмүмкүн болгон комбинациялар. Бирок, бул көп убакытты талап кылат, анткени алардын саны 16 цифраны кайра жайгаштыруу жолдору бар жерлерде бирдей болот. Комбинаторика элементтери ушуга окшогон мисалдарды дароо чечет.
2-маселе. Бул 16 команданын ичинен үчөө гана байге ала алат. Жеңүүчүлөр канча ыкма менен аныкталат? Мында тапшырма мурункусунан айырмаланып турат, ал турнирдик таблица кандай болору жана финалчылардын тартиби кандай экени такыр мааниге ээ эмес. Чынында эле, бардык командалардын ичинен өз ара байгелер үчүн ат салышкан үч гана команданы табуу маанилүү. Башкача айтканда, топтомдор {3, 2, 1}, {5, 12, 7}, {8, 1, 2} ж.б. окшош болушу мүмкүн.
3-маселе. Эгерде суроону бир аз башкача койсок эмне болот: плей-оффко катышкан 16 командага медалдарды бөлүштүрүүнүн канча жолу бар? Экинчи тапшырма менен айырма толугу менен ачык-айкын болушу мүмкүн эмес. Бирок, азыр байге үчүн ат салышкан үч гана команданы эмес, алардын кайсынысы кайсы орунду ээлей турганын аныкташыбыз керек. Башкача айтканда, эгерде экинчи тапшырма үчүн, мисалы, топтомдор (5, 12, 1) жана (1, 12, 5) эквиваленттүү болсо, азыр буйруктардын тартиби салмакка ээ. Чынында эле, биринчи учурда 5-команда алтынды алат, экинчисинде 1-команда.
Төмөндө биз ар бир тапшырма комбинаториканын кайсы бөлүмдөрүнө таандык экенин карап чыгабыз жана аларды чечүү жолдорун кеңири баяндайбыз. Ал ортодо, берилген суроолор боюнча өз алдынча ойлонууга аракет кылсаңыз болот.
Буйрутмасыз айкалышуулар же комбинациялар
Элементтердин жөн гана n-кечесинин айкалышыk 1ден nге чейинки маанилерди ала турган элементтердин к-бөлүкчөлөрүнүн жыйындысы, n элементтен тандалган k элементтердин каалаган айкалышы. Бул учурда, эгерде алардын бири n элементинен кандайдыр бир элементти камтыса, бирок экинчисине таандык болбосо, эки топтом башка болуп эсептелет. Башкача айтканда, алар курамы боюнча гана айырмаланат. Комбинаторика элементтеринде комбинациялар киришүүчү негиз болуп саналат.
nдан kга чейинки айкалыштардын саны C k менен белгиленет, англисче Combination деген сөздөн. C 1=n жана C =1 билдирүүлөрү абдан туура ачык-айкын Башкача айтканда, n элементтен бирден тандоо үчүн n гана вариант бар (элементтердин өздөрүнө бирдей санда) жана ошого жараша n даана санында n элементтин жыйындысын түзө аласыз, бир гана.
Ошондуктан, мисалы, үч элементтен турган {e, 2, a} топтомун карап көрөлү. Ал үчүн C31=3: {a}, {2}, {е}; C32=3: {e, 2}, {2, a}, {a, e}; жана акырында C33=1: {e, 2, a}. Эске салсак, бул учурда топтомдордогу элементтердин тартиби маанилүү эмес.
Эгер сиз C 0 эмне экенин билүүгө аракет кылсаңыз эмне болот?
Буйрутманын негизинде жайгаштыруу же айкалышы
Орнотуунун комбинаторикасын түшүнүү оңой. Бул бир эле комбинациялар, азыр гана курамы эске алынбастан, ар бир комбинациядагы тартип да эске алынат. Ошентип, n даана элементтерди k даанадан турган комбинацияларга (топтомдорго) жайгаштыруу менен, анда k 1ден nге чейинки маанилерди ала алат,белгилүү бир тартипте жайгаштырылган n элементтеринин к-бөлүктөрүнөн турган ар кандай комбинация деп аталат. Башкача айтканда, эки жайгаштыруу айкалышы үч учурда айырмаланат:
- алар курамы боюнча айырмаланат;
- алар топтомдордогу элементтердин тартиби боюнча айырмаланат;
- алар курамы жана тартиби боюнча да айырмаланат.
n баштап k чейин жайгаштыруулардын саны А k менен белгиленет. Үч элементтүү {x, e, z} топтому үчүн бардык жайгаштыруу параметрлерин карап көрүңүз:
- A31=3: (x), (e), (z);
- A32=6: (x, e), (e, x), (x, z), (z, x), (e, z), (z, e);
- A33=6: (x, e, z), (e, x, z), (z, x, e), (x, z, e), (e, z, x), (z, e, x).
Акыркы сап A33 өзгөчө көңүл бурууга татыктуу. Булар алмаштыруудан башка эч нерсе эмес.
Орнотуулар
Жогоруда айтылгандай, алмаштыруулар мааниси жагынан абдан жөнөкөй. Булар ар бири n элементтерден турган жөн эле түзүлүштөр. Башкача айтканда, биз элементтердин тартиби менен айырмаланган бардык комбинацияларга кызыкдар жана аларда гана. Же, барабар, A . Пермутациялардын саны Permutation сөзүнөн алынган P тамгасы менен белгиленет. Комбинаторика элементтеринде алмаштыруулар бир гана индекс менен камсыз кылынат. Ошентип, мисалы, P3=6, биз мурунку бөлүмдө билгендей.
Топтоо теориясы аркылуу айкалышуулар
Белгилүү болгондой, математикада белгисиз нерселер менен байланышуу кыйын: көптүк, комбинация ж.б.. Жакшы болмокэмне менен алектенип жатканыбызды математикалык жактан так аныктайт. Бул жерде көптүк теориясынын тили жардамга келет. Көптүктөр теориясынын тилинде комбинаториканын элементтери эмне экенин аныктап көрөлү.
Кээ бир n-топтомдору берилсин A={a1, a2, …, a }, ал n элементтерди камтыйт. Аны n-топтомдон анын k-подрядынан аныктоо оңой, мында k nден кичине же барабар. Анда nден kге чейинки комбинациялар n көптүгүнүн бардык к бөлүмчөлөрү деп аталат. Бул аныктаманын аркасында C 0 жазуусу кандай болот деген суроого жооп берүү оңой. Көптүктөр теориясында бош топтом кандайдыр бир көмөкчордон камтылгандыктан, анда C 0=1. Башкача айтканда, ал бирди камтыган комбинация болот. элемент - бош топтом.
Ошентип, үч элементтен турган {c, b, a} топтомун изилдеп, биз C 0 =1: { }; C31=3: {a}, {b}, {c}; C32=3: {a, b}, {b, c}, {c, a}; жана акырында C33=1: {a, b, c}.
Ошого жараша алар жайгаштыруу комбинаторикасында да ушундай эле аныкталат. Бир гана айырмасы, сиз n-топтомунан иреттелген к-топтомдорду тандооңуз керек. Ошондой эле бардык бөлүмдөр бош топтомду камтыйт. Ал шарттуу түрдө 0 даанадан турган n элементтин иреттелген айкалышы деп эсептелет, б.а. A 0=1.
Түшүнүктүү конструкциялардан көптүктөр теориясында так аныкталган объекттерге өткөндүктөн, суроолордун бирине жооп берүү анча маанилүү эмес болуп чыкты.пайда болгон суроолор. Мунун баары математика.
Кошуу принциби
Бул комбинаториканын эки негизги эрежесинин бири. Москва шаарында А чекитинен В чекитине чейин 5 автобус, 3 трамвай жана 1 метро поезди менен жетүүгө болот. Керектүү жерге жетүү үчүн 5 + 3 + 1=9 жолу бар экен. Бул кошуунун комбинатордук принциби.
Эгерде маселени карап жатканда, аны n жол менен чечүүгө мүмкүн болсо, бул ыкмалардын биринчиси m1 жолу колдонулса, экинчиси - m 2жолу ж.б., анда бул маселе чечилет m1 + m2 + … + mжол.
Көбөйтүү принциби
Эми Москвадан Казанга Нижний Новгород аркылуу жетүү керек деп элестетип көрөлү. Ошол эле учурда Москва менен Нижний Новгородду 2 поезд, 3 рейс жана 10 жеңил унаа, ал эми Нижний Новгород менен Казанды 1 поезд, 1 рейс жана 2 автобус байланыштырып турат. Кошуу принциби боюнча биз Москвадан Нижний Новгородго, андан Казаньга 13 жол бар деген жыйынтыкка келебиз - 4. Москва менен Казанды бириктирген жолдордун жалпы саны: 134=52 болот..
Ошентип, көбөйтүүнүн комбинатордук принциби төмөнкүчө окулат. Эгерде маселе n даана этап менен чечилсе, биринчи этапта m1 жолу менен, экинчи этапта m2, ж.б., менен Бул учурда, бул ырааттуу этаптар көз карандысыз, башкача айтканда, жолдордун саны мурунку этаптарда кандай чечим кабыл алынганына жараша өзгөрбөйт, андан кийин маселе чечилет m1 m2 …m жолдору. Кадамдарда жок дегенде бир айырмачылык болсо, эки чечим башка болуп эсептелет.
Негизги формулалар
Формулаларды дароо көрсөтөлү, анан алар кайдан келгенин кыскача сүрөттөп алалы жана комбинаториканын бул элементтерин колдонуу менен мурда сүрөттөлгөн мисалдарды чечели.
Турак жай. Бул формуладан баштайбыз, анткени башкалар андан алынган
| A k= | n(n-1)(n-2)(n-3)(n-4)(n-5)…(n-k+1)= | n! |
| (n-k)! |
Орнотуулар
| P= | A = | n(n-1)(n-2)(n-3)(n-4)(n-5)…4321= | n! |
Комбинациялар
| C k= | A k | n(n-1)(n-2)(n-3)(n-4)(n-5)…(n-k+1) | n! |
| k! | k! | k!(n-k)! |
Бул формулалардын далили комбинаториканын элементтеринин принциптерине - кошуу жана көбөйтүү эрежелерине негизделген. жайгаштыруу санын табуу үчүн биринчи формуланы карап көрөлү. Биринчи этапта биз элементтердин n бөлүгүн алабыз жана муну жасоонун n жолу бар. Экинчи этапта бизде n-1 элементтер жана ошого жараша n-1 тандоолор калат. Үчүнчүсү боюнча - n-3 жолдору. Биз муну биздин топтомубузда k даана элементтер болмоюнча жасай беребиз. Көбөйтүү эрежеси боюнча, биз бардыгы болуп n (n-1) (n-2) (n-3) (n-4) (n-5) … (n-k + 1) бар экенине келебиз.) k элементти тандоо жолдору. Алмашууларды табуу үчүн экинчи формула биринчисинин жөнөкөй натыйжасы болуп саналат.алмаштыруу саны m=k. Комбинациялардын санын берүүчү акыркы формула n элементтин комбинацияларын издөөдө к даана к-ну көрүү үчүн келген сайын к! нден kге чейинки аранжировкалар (алар k элементтердин алмашуусу катары алынат). Демек, бизде A k=C kk!.
Эми биз мурда жарыяланган тапшырмаларга кайрылып, варианттардын санын баалай алабыз. Биринчи маселе үчүн биз алмаштыруу формуласын колдонушубуз керек, б.а. P16=16!=20 922 789 888 000 ≈ 211012 16 команданы турнирдик таблицага кантип жайгаштыруунун мүмкүн болгон варианттары. Экинчи маселе комбинацияларга тиешелүү, бул C163=16! / [3!(16-3)!]=560 жеңүүчү. Акырында, акыркы көйгөй жайгаштырууга тиешелүү, б.а. A163=16! / (16-3)!=16 команданын ичинен 3 команда байгелерди бөлүшө ала турган 3360 ыкма.
Жогорудагыларды эске алуу менен, чоң сандар комбинаторикасы кандай иштээри жөнүндө сөз кылуу ашыкча.
