Что такое комбинаторика?

Начнем изучение комбинаторики на позитивной ноте, с анекдота, который отлично иллюстрирует суть этого замечательного, интересного и очень полезного раздела математики:

Экзамен по комбинаторике

Два студента приходят к профессору домой сдавать экзамен по комбинаторике. Ну, сдавали, сдавали, за картами засиделись, за костями игральными, стемнело. А в то время и студенты, и профессора были бедные, домой их не отправишь, пришлось спать укладывать в профессорской трехкомнатной квартире.

В одной комнате - два студента, в другой - профессор с женой, в третьей - профессорская дочь. Все чин по чину, спят.

Просыпается студент, думает, что я тут лежу, как идиот, пойду-ка профессорскую дочь навещу. Глядь в одну комнату - две головы из под одеяла торчат, ну, то профессор с женой, глядь в другую - одна голова. Дочка! Юрк к ней под одеяло, спят.

Не спится и профессору. Встает среди ночи, дай, думает, пойду посмотрю, как там дочка, мало ли что от этих балбесов ждать. Шнырь в одну комнату, две головы, - ага, студенты, шнырь в другую - одна. Дочка, не иначе. Прыг - спит.

Ну, тут и второй студент проснулся, и, как вы уже догадались, отправился по стопам друга, на поиски профессорской дочки.

Утро. Просыпается профессор. Один. В комнате студентов. Хм... Заглядывает в одну комнату - там студент с дочкой, в другую - студент с женой. Чешет репу:

— Сколько лет преподаю комбинаторику, но таких перестановок еще не видел!

Комбинации вокруг нас

Задумайтесь, а как часто в повседневной жизни вы занимаетесь комбинированием, то есть составлением комбинаций из чего-либо? Это вопрос с подвохом. В такой формулировке возникает соблазн ответить «редко» или даже «никогда». Но стоит лишь копнуть глубже и окажется, что все мы каждый день:

• Прикидываем комбинации дел и задач, занимаясь планированием.

• Пишем комбинации букв, получая слова.

• Набираем комбинации цифр, чтобы кому-нибудь позвонить.

• Выстраиваем комбинации мыслей, образуя рассуждения.

Выходит, что мы постоянно составляем комбинации, то есть наборы из самых разных объектов: задач, букв, цифр и даже мыслей! Комбинации повсюду!

Комбинаторика

Нас окружают бесконечно много изменяющихся тел и мы придумали отдельную науку — физику, которая занимается изучением явлений с материей. Каждый из нас имеет уникальный и сложный характер, для изучения которого мы придумали психологию. Наконец, вокруг нас полно живых организмов с самыми разными размерами и устройством. Для их изучения мы придумали биологию.

Теперь, вдогонку телам, характерам и животным мы выяснили, что нас повсюду окружают самые разные комбинации, которые могут состоять из совершенно любых объектов, расположенных по каким-то правилам. Значит, подобно примерам выше, у нас должна быть наука, которая изучает комбинации? И она есть, правда это не полноценная наука, а раздел математики. Называется он «комбинаторика».

Чем она занимается

Есть бесконечно много способов составить комбинации, а значит бесконечно много задач, для решения которых понадобится комбинаторика. Раз задач бесконечно много, попытаемся поделить их на группы, которые будем называть «целями комбинаторики».

Представьте, что вы отправляетесь в туристическое путешествие по нескольким городам! На этапе планирования вы будете пытаться найти самый короткий или дешевый маршрут — комбинацию городов которые надо посетить. Поиск конкретных комбинаций с нужными нам свойствами — первая цель, которую решает комбинаторика.

Иногда получается так, что искомой комбинации просто не существует. Например, невозможно составить комбинацию из городов так, чтобы суммарная длительность путешествия не превысила 1 минуту. Задачи, в которых мы проверяем существование комбинаций, составляют вторую цель комбинаторики.

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

Итак, мы на простых примерах выделили 3 основные группы задач, в решении которых используется комбинаторика:

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

Чем она НЕ занимается

Важно еще и четко обозначить, чем комбинаторика не занимается. Еще раз обратите внимание на определение, а конкретно на слова «изучаются закономерности составления комбинаций». Зачем так сложно? Почему не просто «изучаются комбинации»?

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

В арифметике на вопрос 2 + 3 мы отвечаем 5 и заметьте, нас совершенно не волнует, какой смысл спрашивающий вкладывает в сумму этих чисел: ящики с фруктами, шоколадные батончики двух друзей или зарплата двух человек. Для решения задачи нужны только конкретные данные (числа 2 и 3) и вопрос (какая сумма?).

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

Зачем изучать комбинаторику?

Вы заметили, что приведенные ранее примеры и аналогии всем нам очень хорошо знакомы: слова, путешествия, распорядок дня, телефонные номера? Это не случайность.

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

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

Наконец, комбинаторика используется для исследования самой математики, которая в сущности и состоит из строго заданных комбинаций абстрактных объектов, записываемых конкретными символами по строгим правилам.

Исторический экскурс

Для полноты картины будет полезно знать не только то, чем комбинаторика является сегодня, но и то, какой путь она прошла. А начался он в Средние века, а может и раньше. Компьютеров, телефонов и даже телевизоров тогда не было, поэтому способов развлечься было мало.

Среди более-менее образованного населения большую популярность имели самые разные азартные и настольные игры. Люди рубились в карты, бросали кости, кто-то морщил лбы над более интеллектуальными играми, например, над шахматами.

Ставки в подобных играх были самыми разными: от щелбанов и кружек пива, до бриллиантов и дворцов. Чтобы не проиграть свое состояние, игроки внимательно следили за процессом игры, анализировали его, искали выигрышные стратегии.

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

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

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