Математика: Комбинаториканын негиздери
Комбинаториканын өнүгүү тарыхынан
Адам баласы биздин заманга чейинки тарыхта эле тиги же бул предметти тандоо, аларды аныкталган тартипте жайгаштыруу, алардын арасынан ар кандай жайгашкандарынын эң ыңгайлуусун издеп табуу, мергенчилиер менчиликте жүрүшүп, жоокерлер – салгылаш учурунда, аспаптарды – жумуш учурунда эң мыкты абалдагысын тандоо сыяктуу маселелерди жолуктурушкан. Кийимдеги жасалгалоо, идиштеги сүрөттөр, жебенин учундагы канаттын сабынын жайгашышы дагы аныкталган ыкма менен кооздолунган. Өндүрүшүк жана коомдук мамилелердин мүмкүнчүлүккө жараша татаалданышы дагы барган сайынтартиби, иерархиясы, топтоштурулушу жөнүндөгү жалпы түшүнүктүн негизинде колдонулуп келген. Кол өнөрчүлүк жана соода-сатыктын өнүгүшү ошол багыт менен өнүгө баштаган. Комбинатордук көндүмдөр эс алуу учурунда да пайдалуу экендиги тастыкталган. Ал чуркоо жарышында, секирүүдө, дискти ыргытуу оюндары учурунда биринчи кезекте эсептөө билгичтигин, пладын ала план курууну жана каршылашынын кадамдарын алдын ала көрө билүү керек болгон.
Мындан 35 кылым мурун египеттик фараон Тутанхамонду көмүү зыйнатында пирамидага кошо коюлган предметтердин арасынан байыркы “сенет” оюнунда колдонгон үч горизонт фигурасындагы досканын табылгандыгы. Кийинчерээк шахмат, шашки жана нардалар табылгандыгы. Булар табылган ар бир оюнолуучу фигуралар сунушталган оюнда фигуралардын ары бери жылдырылышы аныкталган айкалышты кармануу менен ким туура билген жана ойногон оюнчу гана натыйжада утушка ээ болоорун түшүнүшкөн.
Комбинаторика түшүнүгү
Комбинато́рика — дисктреттик объектилерди, көптүктөр (айкалышы, ордун которуусу, жылдырылышы жана элементтерин саноодо) жана алар менен катыштар (айталы, жеке тартипте); латын сөзүнөн combinare которгондо – бириктирүү, айкалышы деп түшүндүрөт. Комбинаторика математиканын башка чөйрөлөрү менен да байланышкан – алгебра, геометрия, ыктымалдуулук теориясы жана билимдин ар түрдүү чөйрөлөрүндө да колдонулат.
Жөнөкөй бир мисал карап көрөлү. Мейли, краска куюлган 4 челек бар: кызыл (К), сары (С), жашыл (Ж) жана күрөң (Кң), жана биз аларды коробкаларга ар биринде ар башка эки челектен кылып счалышыбыз керек болот. Биз аны төмөндөгүчө аткарсак болот:
Бизде алты ар түрдүү ыкма бар, эгерде бир коробкада сары жана кызыл болсо, анда ал кызыл жана сары челек краска менен бирдей болот. Бирок, эгерде бир түгөй түстөр менен белгилей турган болсок, анда он эки ыкма бар, анткени кызыл-сары түс менен сары-кызылдын айырмасы бар болот.
Комбинаториканын негизги формулалары
Правила сложения Если некоторый объект А можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить m + n способами.
Пример 1. На тарелке лежат 5 яблок и 4 апельсина. Сколькими способами можно выбрать один плод?
Чыгарылышы: По условию задачи яблоко можно выбрать пятью способами, апельсин – четырьмя. Так как в задаче речь идет о выборе «либо яблоко, либо апельсин», то его, согласно правилу сложения, можно осуществить 5 + 4 = 9 способами.
Ответ: 9 способов.
Пример 2. Сколько двузначных чисел можно составить из цифр 1,4,7, используя в записи числа каждую из них не более одного раза?
Чыгарылышы: 1 способ: перебор вариантов. Для того, чтобы не пропустить и не повторить ни одно из чисел, будем записывать их в порядке возрастания. Сначала запишем числа, начинающиеся с цифры 1, затем с цифры 4, и, наконец, с цифры 7: 14, 17, 41, 47, 71, 74.
Ответ: 6 чисел.
2 способ: дерево возможных вариантов. Для этой задачи построена специальная схема. Ставим звездочку. Далее отводим от звездочки 3 отрезка. Так как в условии задачи даны 3 цифры – 1, 4, 7, то на концах отрезков ставим цифры 1, 4, 7. Далее от каждой цифры проводим по 2 отрезка. На концах этих отрезков записываем также цифры 1, 4, 7. Получились числа: 14, 17, 41 47, 71, 74. То есть всего получилось 6 чисел. Эта схема действительно похожа на дерево, правда «вверх ногами» и без ствола.
Правила умножения Если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать п способами, то выбор пары (А, В) в указанном порядке можно осуществить m ∙ п способами.
Пример 3. Сколько двузначных чисел можно составить из цифр 1,4,7, используя в записи числа каждую из них не более одного раза?
Чыгарылышы: Первую цифру двузначного числа можно выбрать тремя способами. Так как после выбора первой цифры останутся две, то вторую цифру можно выбрать из оставшихся цифр уже двумя способами. Следовательно, общее число искомых трехзначных чисел равно произведению 3∙2, т.е. 6.
Ответ: 6 чисел.
Факториал. Факториалом натурального числа n называется произведение всех натуральных чисел от 1 до n. Обозначение n!
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. Сколькими способами могут быть расставлены восемь участниц финального забега на восьми беговых дорожках?
Чыгарылышы. P8 = 8! = 40 320
Размещением Аkn из n элементов конечного множества по k, где 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 с.
Математика – жөнөкөй эрежелерге ылайык жана мааниге анча деле ээ эмес белгилөөлөрду колдонуу менен ойнолуучу жөн гана оюн.
Давид Гильберт
Оюн ырахат жана кубаныч эле тартуулабастан, толук кандуу эс алуу менен кошо интеллектти машыктырууга үйрөтөт. Математиканын жетишкендиктерин колдонуу жаңы оюндардын теориясын андан ары өнүктүрүү үчүн жана жаңы машыктырууча маселелерди түзүүдө кзмат кылаарын ырахат менен ырастоого болот.
Кубик Рубика – это куб, как бы разрезанный на 27 одинаковых кубиков. В исходном положении каждая грань куба окрашена в один из 6 цветов. Остроумный механизм позволяет поворачивать любой слой из 9 кубиков, примыкающий к одной грани куба, вокруг ее центра. При этом цвета граней смешиваются. Задача состоит в том, чтобы вернуть разноцветные грани кубика в исходное положение. Теоретически из любого состояния кубика можно вернуться в исходное, не более чем за 23 хода.
Лучшее время, показанное на чемпионате мира 1982 г. по скоростной сборке кубика Рубика, составило всего 22,95 секунды. А в наше время дети собирают за считанные секунды. Давайте убедимся
Жебечелер
Ар бир клеткадагы сандардан алардын саны алгачкы санга тең болуп, мында торчодогу сан эсепке алынбагандай кылып жебечелерди жүргүзүү керек. Жебечелер тигинен жана туурасынан жүргүзүлүшү керек. Жебечелер баардык бош клеткаларда болушу керек.
Судоку
1ден 9га чейинки сандардын бош торчосунда ар бир сапчадагы, ар бир мамычадагы жана ар бир квадраттагы сандар бирден гана жолу кездешкендей жайгаштыруу керек.
Лесенка
Пирамиданын чокусунан негизине чейинки сандары ар башка болгондой жолду табуу керек.
Пирамида
Уячалардын 1ден 9га чейин төмөнкү эрежеге ылайык толтуруу керек: уячадагы сан төмөнкү эки уячадагы сандардын суммасы же айырмасы катары болуп, пиармиданын ар бир сабындагы сандар кайталнбашы керек.
Крестики-нолики Самая известная древняя игра. В квадрате, разделенном на девять клеток, игроки по очереди ставят в свободную клетку свой знак: крестик или нолик, стараясь выстроить три крестика или три нолика подряд. Тот, кто первым сделает это, тот и выигрывает.
Если не делать ошибок, то игра оканчивается в ничью. Выиграть можно только в том случае, если противник ошибется. Самый правильный ход –занять угловую клетку. И если партнер не ответит на это своим знаком в центре, то он проиграл.
Ответы:
- Вариант
- Сочетания
- Факториал
- Событие
- Исход