БИЛИМ БУЛАГЫ

История развития комбинаторики

Еще в доисторическую эпоху люди столкнулись с задачами, в которых приходилось выбирать те или иные предметы, располагать их в определенном порядке, отыскивать среди разных расположений наилучшие, выбирая наилучшее положение охотников во время охоты, воинов – во время битвы, инструментов – во время работы. Украшения на одежде, рисунок на посуде, перья в оперении стрел также располагались определенным способом. По мере усложнения производственных и общественных отношений все шире приходилось пользоваться общими понятиями о порядке, иерархии, группировании. Развитие ремесел и торговли происходило в том же направлении. Комбинаторные навыки оказались полезными и во время отдыха. Так наряду с состязанием в беге, прыжках, метании диска появились игры, требовавшие, в первую очередь, умения рассчитывать, составлять план и предвидеть действия противника.

Среди предметов, положенных в пирамиду, где 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

Свойства комбинаторики: перестановки, сочетание, размещение

Перестановкой называется конечное множество, в котором установлен порядок элементов. Число всевозможных перестановок из n элементов вычисляется по формуле: Pn = n!

Пример 4. Сколькими способами могут быть расставлены восемь участниц финального забега на восьми беговых дорожках?

Решение. P8 = 8! = 40 320

Размещением А^k_n из n элементов конечного множества по k, где k≤n, называют упорядоченное множество, состоящее из k элементов и вычисляется по формуле:

Пример 5.

Из 12 учащихся нужно отобрать по одному человеку для участия в городских олимпиадах по математике, физике, истории и географии. Каждый из учащихся участвует только в одной олимпиаде. Сколькими способами это можно сделать?

Решение.

Подмножества, составленные из n элементов данного множества и содержащие k элементов в каждом подмножестве, называют сочетаниями из n элементов по k. (Сочетания различаются только элементами, порядок их не важен: ab и ba – это одно и тоже сочетание) и вычисляется по формуле: .

Число размещений, перестановок и сочетаний связаны равенством: .

Различие между перестановками, размещениями, сочетаниями: В случае перестановок берутся все элементы и изменяется только их местоположение. В случае размещений берётся только часть элементов и важно расположение элементов друг относительно друга. В случае сочетаний берётся только часть элементов и не имеет значения расположение элементов друг относительно друга.

Вероятность. Основные понятия

Наблюдение явления, опыт, эксперимент, которые можно проводить многократно, в теории вероятностей принято называть испытанием. Результат, исход испытания называется событием. Например, сдача экзамена - это испытание; получение определенной отметки – событие, бросание игрального кубика - это испытание; появление того или иного числа очков на брошенной игральной кости - событие.

Вероятность – это число, характеризующее степень возможности появления события. Каждый из возможных результатов испытания называется элементарным исходом.

Вероятностью P события А называют отношение числа благоприятствующих этому событию исходов к общему числу всех равновозможных несовместных элементарных исходов, образующих полную группу. Вероятность P события А определяется по формуле Р = m/n , где m – число элементарных исходов, благоприятствующих A; n – число всех возможных элементарных исходов испытания.

Задача На шести одинаковых карточках написаны буквы К, Б, И, К, Е, Ш. Карточки перемешиваются и наугад раскладываются в ряд. Найдите, чему равна вероятность того, что получится слово БИШКЕК.

Решение. Искомая вероятность вычисляется по классической формуле Р = m/n , где n - общее количество вариантов, а m - количество вариантов, соответствующих данному событию. В данном случае 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.

В качестве примера другого числа, сохраняющего свою пандигитальность при умножении на ряд коэффициентов, можно назвать 1098765432, перемножаемое таким образом на 2, 4, 5 и 7. Если добавить к числу 123456789 умноженному на 8 число 9, будет получен полный палиндром этого числа. Если множитель и слагаемое увеличить на единицу, результатом аналогичных операций станут числа, состоящие из одних единиц разрядностью от десяти до двух.

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

Вся наша жизнь состоит из множества разнообразных программ. Чтобы запустить ту или иную программу нужно ввести соответствующий верный пароль. В качестве кода в зависимости от рода программы могут выступать всевозможные цифры, слова или комбинации слов, поведение или действие. Комбинаторика используется в музыке, в мебельной деятельности, в различных играх (нарды, шашки, шахматы) и т.д. Читайте подробнее: [Электронный ресурс] // 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 с.