Комбинаторика: возникновение, понятие, основные правила

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

Комбинаторика занимается различным видом соединений, которые могут быть образованы из конечного многообразия элементов. В Индии были известны несколько элементов комбинаторики еще во II в. до н.э. Индийцы могли вычислить числа, которых теперь называют «сочетания». В XII веке Бхаскара рассчитывал несколько видов сочетаний и перестановок. Предполагается, что ученые Индии изучали данные, связанные с их применением в поэзии, науке по структуре стихов и поэтической литературе.

Как научная дисциплина, комбинаторика сформировалась в XVII веке. В книге «Теория и практика арифметики» 1656 года французского автора А. Таке посвящена сочетаниям и перестановке отдельная глава.

Б. Паскаль в «Трактате по арифметическому треугольнику» и «Трактате по числовым порядкам» 1665 года изложил учение о биномиальной динамике. П.Ферма знал о связи математического квадрата и фигурного числа с теорией соединения. После публикации Лейбницем в 1665 году работы «Рассуждение о комбинаторном искусстве», в которой было представлено научное объяснение теории комбинации и перестановки, впервые и появилось определение комбинаторики. Изучать размещения первым стал Я. Бернулли во второй части своей книги "Ars conjectandi" (искусство предугадывания) в 1713 г. Современную символику сочетаний предложили разные авторы учебных пособий лишь в XIX веке.

Определение комбинаторики

В смысле задачи, как правило, понятно, что есть только конечное количество объектов, которые интересуют нас, и все дело в поиске этого числа. Рассмотренные объекты обычно представляют собой определенные комбинации других предметов числа, буквы и так далее. Отсюда и следует определение – комбинаторика.

Для более широкого понимания комбинаторная теория является теорией конечных множественностей; здесь мы рассмотрим лишь задачи расчета, поэтому такого расширенного толкования нам не понадобится. Из сказанного понятно, что в комбинаторике речь идет только о натуральных числах. Может казаться, что поэтому она более «элементарна», чем другие математические разделы, оперирующие богатыми числовыми материалами – отрицательными числами, дробями, иррациональными, комплексными. Но такая дискуссия была бы поспешной. Практика свидетельствует о том, что многим, кто впервые встречается с комбинаторикой, сложно привыкнуть к комбинаторному рассуждению, более близкому к программированию, чем, к примеру, к математике.

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

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

Основное правило комбинаторики

Пусть нужно несколько раз выбирать. Есть варианты  для первого выбора,  — для второго,  — для третьего и так далее. Если выбор производится каждый раз без ограничений, общее количество возможностей в каждой последовательности выбора равно общему числу возможностей в каждой последовательности выбора:

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

Число размещений с возвращением

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

Число размещений без возвращения

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

Однако, учитывая, что количество шариков в урне на каждом этапе становится меньше на один, мы можем записать их:

Эта модель имеет важную частную особенность – модель перестановки.

Перестановка из различных шаров

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

.

Такое число называют факториалом от m и обозначают его:

Сочетание (или неупорядоченный выбор)

Модель заключается в том, что не фиксируется порядок номеров вытягивающихся шаров. По сравнению с моделями размещения, наборы, отличающиеся лишь порядком движения элементов, рассматриваются как одинаковые.

Число комбинаций без возврата

Шары, которые достали, не возвращаются в урну. Также не фиксируется порядок номеров в процессе извлечения. Иными словами, вы можете представить, что все n шары вынимают сразу один за одним. Таким образом, мы делаем выбор произвольного подмножества n из подмножества m. Из предыдущего рассуждения видно, что упрощенная выборка размеров n создает  неупорядоченных, каждая из которых однозначно может быть восстановлена.

Из обсуждений модели  известно о том, что число последовательных наборов размером n равно . Обозначим как x исходное число подмножества размера n. Рассуждения, изложенные выше, свидетельствуют о том, что:

Из этого следует, что ответ:

Если умножить числитель и знаменатель на , получим:

Это выражение называется биномиальным коэффициентом, который является важной частью теории вероятности.

Таким образом, тождество верно:

Перестановка из m шаров, неразличимых внутри групп

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

Тогда существует  новых способов размещения с учетом нумерации.

Рассуждения, которые были проведены для модели, свидетельствуют о том, что число неумеренных перестановок является частным:

Число называется мультиномиальным (или полиномиальным) коэффициентов. Когда , коэффициент становится биномиальным.

Число сочетаний с возвращением

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

​​​​​​​

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

Комбинаторика имеет огромное значение в различных областях науки. С комбинаторными величинами приходится иметь дело представителям многих специальностей: ученому – химику, биологу, конструктору, диспетчеру и т.п. Комбинаторика используется в музыке, в мебельной деятельности, в различных играх (нарды, шашки, шахматы). В каждой из этих игр приходится рассматривать различные сочетания фигур, и выигрывает тот, кто их лучше изучает, знает выигрышные комбинации и умеет избегать проигрышных. Усиление интереса к комбинаторике в последнее время обуславливается бурным развитием кибернетики.​​​​​​​

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