Математика: Основы комбинаторики
История развития комбинаторики
Еще в доисторическую эпоху люди столкнулись с задачами, в которых приходилось выбирать те или иные предметы, располагать их в определенном порядке, отыскивать среди разных расположений наилучшие, выбирая наилучшее положение охотников во время охоты, воинов – во время битвы, инструментов – во время работы. Украшения на одежде, рисунок на посуде, перья в оперении стрел также располагались определенным способом. По мере усложнения производственных и общественных отношений все шире приходилось пользоваться общими понятиями о порядке, иерархии, группировании. Развитие ремесел и торговли происходило в том же направлении. Комбинаторные навыки оказались полезными и во время отдыха. Так наряду с состязанием в беге, прыжках, метании диска появились игры, требовавшие, в первую очередь, умения рассчитывать, составлять план и предвидеть действия противника.
Среди предметов, положенных в пирамиду, где 35 веков назад был похоронен египетский фараон Тутанхамон, нашли разграфленную доску с тремя горизонталями и фигурки для древней игры «сенет». Позже появились нарды, шашки и шахматы. В каждой из этих игр приходилось рассматривать различные сочетания передвигаемых фигур, и выигрывал тот, кто их лучше изучил и знал выигрывающие комбинации.
Понятие комбинаторика
Комбинато́рика — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка); в переводе от латинского combinare – соединять, сочетать. Комбинаторика связана с другими областями математики — алгеброй, геометрией, теорией вероятностей и применяется в различных областях знаний.
Рассмотрим простой пример. Допустим, у нас есть банки с краской четырех цветов: красной (К), желтой (Ж), зеленой (3) и коричневой (Кор), и нам нужно разложить их по коробкам, по две разные банки в каждую. Мы можем сделать это следующим образом:
У нас получилось шесть различных способов, так как если в одной коробке находятся банки с желтой и красной красками, то она полностью идентична той, где лежат банки с красной и желтой. Но если мы хотим парными цветами раскрасить флаги, то сделать это можно будет двенадцатью способами, так как красно-желтый флаг не является идентичным желто-красному.
Основные формулы комбинаторики
Правила сложения Если некоторый объект А можно выбрать 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
Свойства комбинаторики: перестановки, сочетание, размещение
Различие между перестановками, размещениями, сочетаниями:
В случае перестановок берутся все элементы и изменяется только их местоположение.
В случае размещений берётся только часть элементов и важно расположение элементов друг относительно друга.
В случае сочетаний берётся только часть элементов и не имеет значения расположение элементов друг относительно друга.
Вероятность. Основные понятия
Наблюдение явления, опыт, эксперимент, которые можно проводить многократно, в теории вероятностей принято называть испытанием. Результат, исход испытания называется событием. Например, сдача экзамена - это испытание; получение определенной отметки – событие, бросание игрального кубика - это испытание; появление того или иного числа очков на брошенной игральной кости - событие.
Вероятность – это число, характеризующее степень возможности появления события. Каждый из возможных результатов испытания называется элементарным исходом.
Вероятностью P события А называют отношение числа благоприятствующих этому событию исходов к общему числу всех равновозможных несовместных элементарных исходов, образующих полную группу. Вероятность P события А определяется по формуле Р = m/n , где m – число элементарных исходов, благоприятствующих A; n – число всех возможных элементарных исходов испытания.
Задача На шести одинаковых карточках написаны буквы К, Б, И, К, Е, Ш. Карточки перемешиваются и наугад раскладываются в ряд. Найдите, чему равна вероятность того, что получится слово БИШКЕК.
Задача «Волк, козел и капуста»
Крестьянину нужно перевезти через реку волка, козла и капусту. Лодка так мала, что в ней кроме крестьянина может поместиться только или волк, или козел, или капуста. Но если оставить волка с козлом, он его съест, а если оставить козла с капустой, то будет съедена капуста. Как быть крестьянину?
Для решения требуется расположить путем взаимной перестановки элементов и в соответствии с условием задачи в определенном порядке. Крестьянину следует начать переправу с перевозки козла. Затем он возвращается и берет волка, которого перевозит на другой берег и оставляет там, а козла возвращает назад на предыдущий берег. Оттуда забирает капусту и перевозит ее к волку. А затем возвращается и забирает козла.
Области применения комбинаторики
Решать комбинаторные задачи нам приходится постоянно. Например, сколько различных сочетаний букв нужно учитывать филологу? Сколько разных нарядов может придумать модельер из трех различных тканей? Как составить список покупок, расписание уроков, футбольную команду, собрать кубик Рубика, припарковаться, приготовить блюдо, рассадить учеников в классе, расставить книги по полкам, сервировать стол? Многие детские игры начинаются со считалок, бросания жребия. Гадания на картах, спичках и ромашке также основаны на комбинаторике. И даже поэзия не обходится без комбинаторики! Стихи и музыка, графика и живопись – все это комбинаторные процессы. Недаром в этих областях искусства «компьютеры» добились впечатляющих успехов. И наконец, все люди – всего лишь комбинация генов в молекулах ДНК!
В видео вошли следующие пункты: учебные заведения - составление расписаний сфера общественного питания - составление меню лингвистика - рассмотрение вариантов комбинаций букв география - раскраска карт соревнования, игры -расчёт количества игр между участниками производство- распределение нескольких видов работ агротехника -размещение посевов на нескольких полях химия - анализ возможных связей между химическими элементами экономика анализ вариантов купли-продажи акций криптография - разработка методов шифрования доставка почты -рассмотрение вариантов пересылки
Комбинаторика в программировании
Комбинаторика – это настоящий клад для программистов, так как помогает анализировать различные алгоритмы, выбор оптимальной стратегии перебора. Комбинаторные формулы требуются для расчётов вероятностей, а те, в свою очередь, для проверки статистических гипотез. Особое внимание уделяют программисты комбинаторным задачам с пандигитальными числами, для генерирования которых используют программу Generics Combinatorics.
Пандигитальными называются числа, составленные из неповторяющихся цифр и не начинающиеся с нуля. Например, 123456789.
Задачи с пандигитальными числами решаются почти так же, как и логические, и даже проще, поскольку все комбинаторные объекты представляют собой обычные числа.
Число 123456789 — наименьшее пандигитальное число в десятичной системе счисления. При умножение на 8 результатом будет 987654312 — другое пандигитальное число, близкое к палиндрому исходного, за исключением двух последних цифр, обменявшихся местами. Это число также сохраняет свою пандигитальность при умножении:
- на 2 123456789 ∙ 2 = 246913578, - на 4 123456789 ∙ 4 = 493827156, - на 5 123456789 ∙ 5 = 617283945, - на 7 123456789 ∙ 7 = 864197523.
В качестве примера другого числа, сохраняющего свою пандигитальность при умножении на ряд коэффициентов, можно назвать 1098765432, перемножаемое таким образом на 2, 4, 5 и 7. Если добавить к числу 123456789 умноженному на 8 число 9, будет получен полный палиндром этого числа. Если множитель и слагаемое увеличить на единицу, результатом аналогичных операций станут числа, состоящие из одних единиц разрядностью от десяти до двух.
Задачи
«Волк, козел и капуста»
Крестьянину нужно перевезти через реку волка, козла и капусту. Лодка так мала, что в ней кроме крестьянина может поместиться только или волк, или козел, или капуста. Но если оставить волка с козлом, он его съест, а если оставить козла с капустой, то будет съедена капуста. Как быть крестьянину? Для решения требуется путем взаимной перестановки элементов расположить их в соответствии с условием задачи в определенном порядке. В случае с крестьянином переправу следует начать с перевозки козла. Затем крестьянин возвращается и берет волка, которого перевозит на другой берег и оставляет там, а козла возвращает назад на предыдущий берег. Оттуда забирает капусту и перевозит ее к волку. А затем возвращается и забирает козла.
«Крестики-нолики»
Самая известная древняя игра. В квадрате, разделенном на девять клеток, игроки по очереди ставят в свободную клетку свой знак: крестик или нолик, стараясь выстроить три крестика или три нолика подряд. Тот, кто первым сделает это, тот и выигрывает. Если не делать ошибок, то игра оканчивается в ничью. Выиграть можно только в том случае, если противник ошибется. Самый правильный ход –занять угловую клетку. И если партнер не ответит на это своим знаком в центре, то он проиграл.
«Ним»
Пусть имеется одна или несколько групп предметов. Играющие берут по очереди предметы из групп по правилам, которые заранее устанавливают: какое количество предметов разрешается брать за один раз и из скольких групп. Существует множество вариантов игры, и для большинства известна наилучшая стратегия, ведущая к выигрышу.
Полезные ссылки
«Я не знаю ничего более прекрасного в арифметике, чем эти числа, называемые некоторыми планетарными, а другими – магическими», - писал о числах известный французский математик, один из создателей теории чисел Пьер де Ферма. Привлекающие естественной красотой, наполненные внутренней гармонией, доступные, но по-прежнему непостижимые, скрывающие за кажущейся простотой множества тайн. В своей жизни каждый из нас сталкивается с числами. Курс школьной программы, да и дальнейшую жизнь, трудно представить без них. Более подробно читаем в исследовательская работе "Магические числа" http://collegy.ucoz.ru/publ/89-1-0-3365
Глоссарий
Комбинаторика - ветвь математики, изучающая комбинации и перестановки предметов.
Библиография
- Комбинаторика. https://infourok.ru/kombinatorikaeto-interesnonauchniy-proekt-sekciya-matematika-816469.html
- Комбинаторика: основные правила и формулы. http://ya-znau.ru/znaniya/zn/80
- Савельев Л.Я. Комбинаторика и вероятность. – Новосибирск, Наука, 1975.
- Тюрин Ю.Н., Макаров А.А., Высоцкий И.Р., Ященко И.В. Теория вероятностей и статистика. – М.: МЦНМО: АО «Московские учебники», 2004.
1. Среди предметов, положенных в пирамиду, где 35 веков назад был похоронен египетский фараон Тутанхамон, нашли разграфленную доску с тремя горизонталями и фигурки для древней игры «сенет». Позже появились нарды, шашки и шахматы.
2. Первое упоминание о вопросах, близких к комбинаторным, встречаются в китайских рукописях под названием «Книга перемен».
3.Значительный толчок в развитию комбинаторики дали азартные игры, в особенности игра в кости.
4. С помощью комбинаторного метода можно прочитать забытые письменности, освоенного на наблюдениях над текстом, на сопоставлении повторяемости комбинаций.
5. Кубик Рубика – это куб, как бы разрезанный на 27 одинаковых кубиков. В исходном положении каждая грань куба окрашена в один из 6 цветов. Остроумный механизм позволяет поворачивать любой слой из 9 кубиков, примыкающий к одной грани куба, вокруг ее центра. При этом цвета граней смешиваются. Задача состоит в том, чтобы вернуть разноцветные грани кубика в исходное положение. Теоретически из любого состояния кубика можно вернуться в исходное, не более чем за 23 хода.
Лучшее время, показанное на чемпионате мира 1982 г. по скоростной сборке кубика Рубика, составило всего 22,95 секунды. А в наше время дети собирают за считанные секунды. Давайте убедимся
Математические фокусы — самые простые в исполнении. Для них не нужен реквизит, длительная подготовка и специальное место для демонстрации. Смысл таких фокусов — в отгадывании чисел, задуманных зрителями, или в каких-нибудь операциях над ними. Все чудеса основаны на математических закономерностях, такие фокусы можно проделывать на уроках математики. Смотрим и учимся математической магии.
1.
2.
3.
4.
5.
Ответы:
- Вариант
- Сочетания
- Факториал
- Событие
- Исход