Комбинаторика - это что такое? Элементы комбинаторики

Автор Андрей July 26, 2018

Специалистам самых разных областей необходимо решать комбинационные задачи: перестановка цифр, знаков и других объектов. Например, руководителю цеха нужно распределить разные виды работ между работающими станками. Комбинаторика - это значимый раздел математики, который, как не трудно догадаться, находит свою нишу в самых разных областях и специальностях: физика, биология, лингвистика, химия, инженерия, теория кодирования и многое другое. Принципы комбинаторики также лежат в основе решения множества вероятностных задач.

История

Первые предпосылки комбинаторики как науки появились в 16 в. Способствовало развитию данной области знаний в большой степени увлечение людей азартными играми: в карты, кости, лотереи проигрывали не просто золото и драгоценности, а дворцы и имения. Поэтому, задаваясь вопросом, например, о том, как часто можно выбросить удачный набор очков на костях или получить два туза, люди постепенно пришли к основам комбинаторики и вероятности. Помогла ли комбинаторика кому-то выигрывать больше или терять меньше? Вопрос интересный, но его рассмотрение выходит за пределы данной статьи.

Первый математик, активно увлекавшийся вопросами комбинаторики - это итальянец Тарталья (1499-1557 гг.) После него в изучение данных вопросов активно погрузились такие именитые ученые, как Паскаль, Ферма, Бернулли, Лейбниц, Эйлер и др. Однако стоит заметить, что комбинаторика по прежнему оставалась если не забавной игрой с числами, то теорией, которая используется исключительно в азартных играх и не имеет права применяться где-либо еще.

Развитие комбинаторики

Значимые подвижки в вопросах комбинаторики случились с появлением в 20 в. вычислительных машин, программирования, а главное - дискретной математики. В этот период комбинаторика получает пик своего бурного развития и становится полноценной наукой. Комбинаторные методы начинают использоваться повсеместно:

решение транспортных задач;
составление расписаний;
подготовка планов производства и продажи товаров;
в теории случайных процессов;
в математической статистике и теории вероятностей;
в подготовке и проведение экспериментов;
в шахматах;
в термодинамике;
в геометрии;
и во многих других областей.

Задача о суеверном руководителе

Жил да был на свете руководитель, который верил, что число 8 приносит ему сплошные неудачи. Поэтому он решил избавиться от всех чисел, которые содержали бы восьмерку. Работало под его началом 600 человек. У каждого был идентификационный номер пропуска на работу, состоящий из трех чисел. Недолго думая, руководитель решил исключить и из номеров пропусков число 8. И тут он задумался, а хватит ли разных чисел на 600 человек из диапазона от 000 до 999, которые не включали бы 8?

Очевидным решением данной задачи является выписывание вручную всех чисел от 000 до 999 и вычеркивание тех из них, в которых присутствует восемь. Можно ли решить поставленную задачу более простым способом? Если для 999 чисел задача с перебором всех вариантов выглядит выполнимой, то диапазон от 000000 до 999999 потребует значительно больших усилий. Именно для экономии сил и времени призваны формулы комбинаторики.

Решение задачи о суеверном руководителе

Другой способ решения выглядит следующим образом. Исключив 8 из ряда, мы получим, что 0, 1, 2, 3, 4, 5, 6, 7, 9 - данные девять чисел являются допустимыми. После этого следует найти все двузначные номера, которые не содержали бы 8. Делается это просто: нужно взять любое число из допустимых и дописать к нему также любой число из допустимых. Таким образом мы легко получим все двузначные цифры, которые подходят под условие. В итоге получим, что каждый однозначный номер даст 9 разных двузначных. Итоговое число таких цифр будет 9*9 = 9² = 81.

Продолжая аналогию, можно заключить, что для получения всех трехзначных цифр без восьмерок, нужно к имеющимся двузначным числам приписать третий разряд, также из допустимых значений. Тогда получим, что число таких цифр будет 9²*9 = 9*9*9 = 729. Таким образом мы выяснили, что наш горе руководитель легко сможет обеспечить 600 работников пропусками, номера которых не будут содержать 8. Попробуйте самостоятельное решить задачу для случая с пятизначными номерами.

А что будет, если руководителю не понравится еще и число 2? Получается, тогда количество допустимых чисел будет 8, а именно: 0, 1, 3, 4, 5, 6, 7, 9. Тогда прикинув количество комбинаций чисел без 2 и 8, можно заключить, что их число равно 8*8*8 = 512, а этого явно недостаточно, чтобы обеспечить 600 человек пропусками. Комбинаторика - это наука, помогающая отвечать на подобные вопросы более эффективно, чем это можно сделать методом перебора.

Задача о лото

Всем известная игра. Есть мешок, в котором лежат бочонки с номерами от 1 до 90. Всем участникам раздаются билеты, в которых нужно закрасить некоторое количество клеток с числами. После чего ведущий лото достает из мешка один из пронумерованных бочонков. Победителем будет тот, у кого в билете зачеркнуто больше всего чисел, совпадающих с теми, которые вытянул ведущий игры.

Как-то раз Нина, играя в лото, задумалась. Она часто наблюдала, как ведущий достает из мешка один и тот же номер. Но в то же время первые два бочонка оказывались одинаковыми значительно реже. Тогда она задалась вопросом, сколькими способами можно последовательно достать из мешка два бочонка? Элементы комбинаторики помогают ответить на ее вопрос.

Решение задачи о лото

Очевидно, первый бочонок может иметь номера от 1 до 90. Иными словами, существует 90 способов извлечь первый бочонок. Но как обстоят дела дальше? Если, допустим, бочонок №63 был извлечен из мешка, то в текущей игре он больше не повторится.

Решить поставленную задачу нам поможет метод таблицы. Где в заглавной строке и в заглавном столбце будут выписаны номера от 1 до 90. Таким образом, на пересечение какой-либо строки и какого-либо столбца окажется пара чисел, или пара изъятых из мешка бочонков. При этом на диагонали таблицы будут располагаться одинаковые пары чисел. Что невозможно по условию, так как после изъятия одной цифры из мешка, ее повторение невозможно. Получится таблица следующего вида:

	1	2	...	90
1	x	1, 2	...	1, 90
2	2, 1	x	...	2, 90
...	...	...	x	...
90	90, 1	90, 2	...	x

Итого получаем таблицу, у которой количество ячеек равно 90*90 = 8100. При этом стоит помнить, что по диагонали располагается 90 пар цифр, невозможных по условиям. Тогда ответом на вопрос о том, сколькими способами можно достать из мешка 2 бочонка - будет 8100 - 90 = 8010 вариантов.

Рассуждая немного другим способом можно прийти к такому же ответу. Для первого бочонка существует 90 вариантов. После того как первый был извлечен, для второго бочонка останется 89 вариантов. Таким образом, общее количество вариантов составит 90*89 = 8010. Элементы комбинаторики могут применяться разными путями. Вопрос лишь в простоте и универсальности метода. Так, например, метод таблиц можно использовать для трех извлекаемых подряд бочонков и, очевидно, это будет предел. А что для четырех и более?

Задача об экипаже корабля

Если варианты выбора зависят от того, какие объекты были выбраны ранее, то такой процесс удобно отображать в виде "дерева". На первом шаге из одной точки откладывается столько линий, сколько существует возможных выборов на первом шаге. На концах каждой линии также проводят столько дополнительных линий, сколько можно сделать на втором шаге и т. д. В итоге будет нарисовано своего рода дерево или граф. Комбинаторика и теория может звучать достаточно запутанно и непонятно, поэтому рассмотрим на примере.

Перед началом экспедиционного года у руководства стоит задача - собрать экипажи для поездок. Каждая команда должна включать в себя три человека: командира, инженера и врача. При этом количество специалистов в той или иной области может варьироваться. Допустимо, например, чтобы в две разные экспедиции отправлялся один врач, т. к. врачей всего двое, а командиров и инженеров может быть по трое. При этом составителю экспедиционного плана необходимо учитывать психологическую совместимость членов команды. Данная характеристика является одной из самых важных в долгих и дальних экспедициях для их успешного проведения. Исходя из всех описанных условий, вырисовывается следующая картина:

Где a_i - командиры, b_i - инженеры и c_i - врачи. При этом в ходе тестирования каждого человека было выяснено, что командир a₁ психологически хорошо ладит с инженерами b₁ и b₃, a₂ - с b₁ и b₂, а вот врач c₃ несовместим с инженером b₁ и т. д. Вопрос, которые изначально ставился перед руководителем проекта - сколько экипажей можно составить при таких условиях. Из составленной диаграммы видно, что всего таких экипажей может быть 10. Но что было бы, если вопрос о психологической совместимости не имел веса? Тогда получается, что после выбора командиров a_i, существовало бы по 3 альтернативы для каждого из них в выборе инженера. Соответственно, для пары командира и инженера также имелось бы 3 варианта врачей. Тогда количество комбинаций достигнет 4*3*3 = 36 экипажей.

Размещения, перестановки и сочетания

В примерах выше решение задач происходило так называемым аксиоматическим методом. То есть, можно говорить, что существует ряд основных задач, к решению которых могут сводиться многие проблемы. Однако точно также как в стереометрии неудобно решать задачи, основываясь исключительно на аксиомах, и для этого используется более удобный инструмент под названием "теоремы", так и в комбинаторике удобнее использовать более обобщенные и доказанные методы. В ходе многовекового изучения комбинаторики стало очевидным, что ряд задач встречается куда чаще остальных, и они были выделены в отдельные классы и получили свои названия, став в комбинаторики основными - а именно: размещения, перестановки и сочетания.

Проблемы комбинаторики

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

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