БИЛИМ БУЛАГЫ

Комбинаториканын өнүгүү тарыхынан

Адам баласы биздин заманга чейинки тарыхта эле тиги же бул предметти тандоо, аларды аныкталган тартипте жайгаштыруу, алардын арасынан ар кандай жайгашкандарынын эң ыңгайлуусун издеп табуу, мергенчилиер менчиликте жүрүшүп, жоокерлер – салгылаш учурунда, аспаптарды – жумуш учурунда эң мыкты абалдагысын тандоо сыяктуу маселелерди жолуктурушкан. Кийимдеги жасалгалоо, идиштеги сүрөттөр, жебенин учундагы канаттын сабынын жайгашышы дагы аныкталган ыкма менен кооздолунган. Өндүрүшүк жана коомдук мамилелердин мүмкүнчүлүккө жараша татаалданышы дагы барган сайынтартиби, иерархиясы, топтоштурулушу жөнүндөгү жалпы түшүнүктүн негизинде колдонулуп келген. Кол өнөрчүлүк жана соода-сатыктын өнүгүшү ошол багыт менен өнүгө баштаган. Комбинатордук көндүмдөр эс алуу учурунда да пайдалуу экендиги тастыкталган. Ал чуркоо жарышында, секирүүдө, дискти ыргытуу оюндары учурунда биринчи кезекте эсептөө билгичтигин, пладын ала план курууну жана каршылашынын кадамдарын алдын ала көрө билүү керек болгон.

Мындан 35 кылым мурун египеттик фараон Тутанхамонду көмүү зыйнатында пирамидага кошо коюлган предметтердин арасынан байыркы “сенет” оюнунда колдонгон үч горизонт фигурасындагы досканын табылгандыгы. Кийинчерээк шахмат, шашки жана нардалар табылгандыгы. Булар табылган ар бир оюнолуучу фигуралар сунушталган оюнда фигуралардын ары бери жылдырылышы аныкталган айкалышты кармануу менен ким туура билген жана ойногон оюнчу гана натыйжада утушка ээ болоорун түшүнүшкөн.

Комбинаторика түшүнүгү

Комбинато́рика — дисктреттик объектилерди, көптүктөр (айкалышы, ордун которуусу, жылдырылышы жана элементтерин саноодо) жана алар менен катыштар (айталы, жеке тартипте); латын сөзүнөн combinare которгондо – бириктирүү, айкалышы деп түшүндүрөт. Комбинаторика математиканын башка чөйрөлөрү менен да байланышкан – алгебра, геометрия, ыктымалдуулук теориясы жана билимдин ар түрдүү чөйрөлөрүндө да колдонулат.

Жөнөкөй бир мисал карап көрөлү. Мейли, краска куюлган 4 челек бар: кызыл (К), сары (С), жашыл (Ж) жана күрөң (Кң), жана биз аларды коробкаларга ар биринде ар башка эки челектен кылып счалышыбыз керек болот. Биз аны төмөндөгүчө аткарсак болот:

Бизде алты ар түрдүү ыкма бар, эгерде бир коробкада сары жана кызыл болсо, анда ал кызыл жана сары челек краска менен бирдей болот. Бирок, эгерде бир түгөй түстөр менен белгилей турган болсок, анда он эки ыкма бар, анткени кызыл-сары түс менен сары-кызылдын айырмасы бар болот.

Комбинаториканын негизги формулалары

1-миcал. Тарелкада 5 алма жана 4 апельсин салынган. Канча ыкма менен бир жемишти тандоого болот.

Чыгарылышы: Тапшырманын шарты боюнча алманы 5 ыкма, ал эми апельсинди 4 ыкма менен тандоого болот. Тапшырманын шарты болсо “же алма же пельсин” экендигин эске алуу менен 5+4=9 экенин табууга болот.

Жообу: 9 ыкма.

2-мисал. 1,4,7 сандарынан ар бири бир жолудан көп эмес колдонуп, канча эки маанилүү сан куроого болот?

Чыгарылышы: 1-ыкма: Варианттарды тандоо. Өткөрүп жибербес жана кайталабас үчүн бул сандарды өсүү тартибинде жазабыз. Алгач, 1 санына башталгандарды, андан сөн 4 жана 7 санына башталган сандарды жазабыз: 14, 17, 41, 47, 71, 74.

Жообу: 6 сан.

3-ыкма: Мүмкүн болгон вариантту дарак. Бул тапшырманы чыгаруу үчүн атайын схема курулган.

Жылдызча коёбуз. Андан ары ал жылдызчадан 3 кесинди чыгарабыз. Тапшырманын шарты боюнча 3 сан берилген – 1,4,7, кесиндинин учтарына бул сандарды жазабыз.

Андан соң, ар бир санга 2ден кесинди туташтырабыз. Алардан ары улап ар бир кесиндинин учуна 1, 4, 7 сандарын жазабыз. Жыйынтыгы: 14, 17, 41 47, 71, 74 болот. Б. А. баары 6 сан болот. Бул схема даракка окшош болгондуктан “дарак” деп аталат.

3-мисал. 1,4,7 сандарынан ар бири бир жолудан көп эмес колдонуп, канча эки маанилүү сан куроого болот?

Чыгарылышы: Биринчи эки орунду санды үч ыкма менен тандоого болот. Биринчи санды тандагансоң, экинчи санды калган сандардан эки ыкма менен тандаса болот. Андан соң, изделүүчү үч маанилүү сандын жалпы саны 3*2 санын көбөйтүндүсүнө, бюаю 6га барабар болот. искомых трехзначных чисел равно произведению 3∙2, т.е. 6.

Жообу: 6 саны.

Факториал.

0! = 1

1!=1

2! = 1∙ 2 = 2

3! = 1∙ 2 ∙ 3 = 6

4! = 1∙ 2 ∙ 3 ∙ 4 =24

5! = 1∙ 2 ∙ 3 ∙ 4 ∙ 5 = 120

6! = 1∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 = 720

7! = 1∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 = 5 040

8! = 1∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 ∙ 8 = 40 320

9! = 1∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 ∙ 8 ∙ 9 = 362 880

10! = 1∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 ∙ 8 ∙ 9 ∙ 10 = 3 628 880

Комбинаториканын касиеттери:

Которулуштуруу деп, элементтери тартиби менен жайгашкан көптүк аталат. N элементтен турган мүмкүн болушунча которулуштуруу бул формула менен эсептелинет: Pn = n!

4-мисал. Финалдык чуркоодогу 8 катышуучу 8 чуркоочу тилкеге канча ыкма менен которулууга болот?

Чыгарылышы. P8 = 8! = 40 320

Акыркы көптүгү k (мында) боюнча n элементтен турган А^k_n которулуусу ирээтелген көптүк деп аталып, k элементтен турган бул көптүк төмөнкү формула менен эсептелинет:

5-Мисал.

12 окуучунун ичинен математика, физика, тарых жана география предметтери боюнча шаардык олимпадага катышууга бирден окуучуну тандоо керек. Ар бир катышуучу бирден гана предметке катышат. Канча ыкма менен аткарууга болот?

Чыгарылышы.

n элементтен турган жана ар бир көптүктөгү k элементи бар көптүктөрдү n элементтен турган k элементтүү айкалышуу деп аталат. (Айкалышуу элементтеринен гана айырмаланат, тартиби маанилүү эмес: : ab жана ba –бул тиги да бул да айкалышуу) жана бул формула менен эсептелинет:

Орун алмашуу, которулуу, айкаыштыруу бул барабарсыздык менен байланышат:

Ыктымалдуулук. Негизги түшүнүктөр

Ыктымалдуулук теориясында бир нече жолу кубулуштарды, тажрыйбаларды, эксперименттерди байкоо текшрүү (сыноо) деп аталат. Текшерүү (сыноонун) жыйынтыгын окуя деп айтабыз. Мисалы, экзамен тапшыруу- бул сыноо; аныкталган баа алуу – бул окуя, оюн кубикти ыргытуу же өкчөө – бул сыноо; тиги же бул тараы менен түшүү же упайдын саны – бул окуя.

Ыктумалдуулук – бул окуянын пайда болуш мүмкүндүгүн мүнөздөөчү сан. Ар бир мүмкүн болгон сыноонун жыйынтыкгы элементардык жыйынтык деп аталат.

Рнын ыктымалдуулугу А окуясынын ошол окуяга карата боло (ишке аша) турган сандын, баардык мүмкүн болгон элементардык жыйынтыкка дал келбеген жалпы топту түзүүчү катышы болот. Р ыктымалдуулук А окуясын Р = m/n , мында m- элементардык жыйынтык; n – сыноодогу баардык мүмкүн болгон элементардык жыйынтыгы, Анын ылайыктуу элементардык жыйынтыгын аныктоочу формула.

Маселе Алты бирдей жасалган корточкага К, Б, И, К, Е, Ш тамгалары жазылган. Карточкалар аралаштырылып кокустук боюнча бир катарга тизилет. Натыйжада БИШКЕК деп жазылып калгандай ыктымалдуулук эмнеге барабар болоорун тапкыла.

Чыгарылышы. Изделүүчү ыктымалдуулук Р = m/n , мында m- элементардык жыйынтык; n – сыноодогу баардык мүмкүн болгон элементардык жыйынтыгы формуласы менен эсептелинет.

Биздин учурда n = 6! = 720 (6 карточканын жайгаштырылыш саны);

m = 2 (бул сөздөгү “К” тамгасынын эки жолу кайталанышы, калгандары бирден эле жолу).

Тыянак, Р=2/720=1/360.

Тапшырма: «Карышкыр, эчки жана капуста»

Дыйкан дарыянын аркы өйүзүнө карышкырды, эчкини жана капустаны алып өтүшү керек. Кайыкта орундук аз болгондуктан өзү менен кошо бирөөнү: карышкырды, эчкини же капустаны гана алып өтө алат. Бирок, карышкырды эчки менен калтырса карышкыр эчкини жеп салат, ал эми эчкини капуста менен калтырса капустаны эчки да жеп салат. Дыйкан эмне кылуу керек?

Маселени чыгаруу үчүн маселенин коюлуш шартына карата элементтерди өз ара жайгаштырууну колдонуу керек. Дыйкан бул жерде эчкини алып өтүү менен башташ керек болот. Андан соң жээке келип карышкырды тиги жээке алып келип кайра өзү менен кошо эчкини берки жээке ала кетиши керек болот. Ал жактан эчкини таштап капустаны тиги карышкыр турган жээкке алып келиш керек. Андан соң кайтып келип эчкини алып өтөт.

Комбинаториканы колдонуу чөйрөсү

Комбинатордук маселелерди чыгаруу бирге дайыма керек болот. Мисалы, филологго канча тамгалардын айкалышын эске алуу керек болот? Үч ар түрдүү кездемеден модельер канча ар түрдүү кийимди ойлоп табууга болот? Сатып алуучу буюмдардын тизмесин, сабактардын жүргүртмөсүн, футболдук команданын, Рубик кубигин, тамакты даярдоодо, класста окуучуларды отургузуу, текчелерге китептерди жайгаштыруу, столду жасалгоолоодо кантип түзүү керек? Көпчүлүк балдар оюндары чучу кулак кармоо менен башталат. Карта менен, ширенке менен же ромашка менен төлгө ачуу дагы комбинаторикага негизделген. Крек болсо поэзия дагы комбинаториканы унутта калтырбайт! Ыр жана музыка, графика – живопись искусствосу – мунун баары комбинаторжук процесстер. Бекеринен бул чөйрөдөгү “компьютерлер” таң калаардыктай ийгиликтерге жетишпесе керек. Аягында, баардык адамдар – ДНК молекуларларындагы гендердин комбинациялары экенин айтса болот.

Комбинаторика программалоодо

Комбинаторика – бул ар кандай алгоритмдерди талдоодо, оптималдуу стратегияларды тандоодо керек болгон программисттердин чыныгы кенчи. Комбинатордук формулалар ыктымалдуулукту эсептөө үчүн, өзүнүн учурунда статистикалык гипотезаларды текшерүү үчүн керек болот. Программисттер комбинатордук маселелерди чыгарууда генерациялоо үчүн өзгөчө көңүлдү Generics Combinatorics программасы колдонгон пандигиталдык сандарга бурат.

Пандигиталдык сан деп, нөлдөн башталбаган жана бир сан кайра кайталанбаган сандарды айтабыз. Мисала 123456789.

Пандигиталдык сандары бар маселелерди логикалык сыяктуу эле керек болсо андан да жөнөкөй чыгарылат, анткени комбинатордук объектилер өзүнө сандарды камтыйт.

Число 123456789 — наименьшее пандигитальное число в десятичной системе счисления. При умножение на 8 результатом будет 987654312 — другое пандигитальное число, близкое к палиндрому исходного, за исключением двух последних цифр, обменявшихся местами. Это число также сохраняет свою пандигитальность при умножении:

- 2ге 123456789 ∙ 2 = 246913578,

- 4кө 123456789 ∙ 4 = 493827156,

- 5ке 123456789 ∙ 5 = 617283945,

- 7ге 123456789 ∙ 7 = 864197523.

Мисал катары башка санды санга 2, 4, 5, жана 7 (коэффициентке) көбөйтүүдө пандигиталдуулугун сактаган сан катары 1098765432 келтирсек болот. Эгерде 123456789ны 8ге жана 9га көбөйтсөк бул сандын толук палиндрому келип чыгат. Эгерде көбөйүүчүнү жана кошулуучуларды 1ге чоңойтсок, жыйынтыгы ондо экиге чейинки разраддагы 1 1диктен турган сан пайда болот.

Полезные ссылки

Вся наша жизнь состоит из множества разнообразных программ. Чтобы запустить ту или иную программу нужно ввести соответствующий верный пароль. В качестве кода в зависимости от рода программы могут выступать всевозможные цифры, слова или комбинации слов, поведение или действие. Комбинаторика используется в музыке, в мебельной деятельности, в различных играх (нарды, шашки, шахматы) и т.д. Читайте подробнее: [Электронный ресурс] // 2011-2017 Сила знаний URL: http://ya-znau.ru/znaniya/zn/80 (Дата посещения: 19.04.2018)

Толук чыгарылыштуу комбинатордук маселелерди төмөндө караса болот: [Электрондык ресурс] //mathprofi.ru, Александр Емелин, 2010-2018 URL: http://www.mathprofi.ru/zadachi_po_kombinatorike_primery_reshenij.html (Катышуу датасы: 19.04.2018)

Необходимые теоретические сведения и формулы для решения комбинаторных задач школьного уровня можно посмотреть здесь: [Электронный ресурс] // Харламов А.В. элементы комбинаторики, 2016г. // URL: http://elibrary.sgu.ru/uch_lit/1626.pdf (Дата посещения: 21.04.2018)

Поиграем? Пусть имеется одна или несколько групп предметов. Играющие берут по очереди предметы из групп по правилам, которые заранее устанавливают: какое количество предметов разрешается брать за один раз и из скольких групп. Существует множество вариантов игры, и для большинства известна наилучшая стратегия, ведущая к выигрышу.:[Электронный ресурс] // ЮЦ «Восстание-6» URL: https://logic-games.spb.ru/nim/ (Дата посещения: 22.04.2018)

Глоссарий

Дискре́ттүүлү (лат. discretus — бөлүнгөн, үзгүлтүктүү) – үзгүлтүксүзгө карама-каршы коюлган, үзгүлтүктүү касиет. Дискреттүүлүк түшүнүгү: бин нече туруктуу абалдардын ортосундагы өзгөрүүчү бин нерсе, мисалы мүнөттүк жебечеси дискреттүү кыймылдаган механикалык сааты, 1/60га айлананын бөлүгү; өзүнчө бөлүктөрдү түзгөн, үзгүлтүктүү, бөлчөктүк бир нерсе.

Палиндро́м (грек. πάλιν — «артка, кайра» жана башка.-грек. δρóμος — «чуркоо, кыймыл»)— эки тарабынан бирдей окула турган сан, тамгалар айкалышы, сөз же текст.

Пандигиталдык сандар – бул нолдөн баштабаган жана бир сан кайра кайталанбаган сан.

Су́тра (санскр. सूत्र sūtra IAST, «жип», пали: sutta) — байыркы абадияттардагы лаконикалык жана үзгүлтүктүү айтылыш, афоризмдер, кийинчерээк – ушундай айтылыштардын. Сутраларда ар түрдүү билимдери, дээрлик Байыркы Индиянын диний-философиялык окуучлары жазылган.

Библиография

• Комбинаторика: основные правила и формулы. : [Электронный ресурс] // 2011-2017 Сила знаний URL: http://ya-znau.ru/znaniya/zn/80 (Дата посещения: 19.04.2018)
• Задачи по комбинаторике. Примеры решений.: [Электронный ресурс] //mathprofi.ru, Александр Емелин, 2010-2018 URL: *http://www.mathprofi.ru/zadachi_po_kombinatorike_primery_reshenij.html (Дата посещения: 19.04.2018)
• Сканворды, кроссворды и головоломки: [Электронный ресурс] // Пискунов Алексей © 2009-2018 http://www.graycell.ru/index.html (Дата посещения: 19.04.2018)
• Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика: М.: ФИМА, МЦНМО, 2006. — 400 с.
• Мир математики: в 40 т. Т.21: Ламберто Гарсия дель Сид. Замечательные числа. Ноль, 666, и другие бестии./Пер. с исп. –М.: Де Агостини, 2014. – 160 с.

                     Давид Гильберт