Статью подготовили специалисты образовательного сервиса Zaochnik.

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

Содержание:

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

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

Пример 1

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

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

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

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

Определение 1

Комбинаторика (комбинаторная математика) является разделом математики, который относится к методам подсчета количества предметов определенного происхождения.

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

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

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

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

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

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

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

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

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

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

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

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

Замечание 1

Главное правило не применимо напрямую.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если умножить числитель и знаменатель на Число комбинаций без возврата, получим:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выполненные работы по информационной безопасности
  • Информационная безопасность

    Предмет защита конфиденциальной информаци

    • Вид работы:

      Дистанционный экзамен, онлайн-тест

    • Выполнена:

      12 апреля 2022 г.

    • Стоимость:

      2 400 руб

    Заказать такую же работу
  • Статистика

    Экономикоматематический анализСтатистика

    • Вид работы:

      Контрольная работа

    • Выполнена:

      25 марта 2022 г.

    • Стоимость:

      1 400 руб

    Заказать такую же работу
  • Электроснабжение

    Сделать расчеты работу закрепил С пункта по пункт

    • Вид работы:

      Курсовая работа

    • Выполнена:

      8 февраля 2022 г.

    • Стоимость:

      4 800 руб

    Заказать такую же работу
  • Информационные системы

    прикладная информатика в экономике

    • Вид работы:

      Отчёт по практике

    • Выполнена:

      22 сентября 2021 г.

    • Стоимость:

      2 600 руб

    Заказать такую же работу
  • ПГС

    Завод электросталей фотография генерального плана завода

    • Вид работы:

      Курсовая работа

    • Выполнена:

      1 июля 2021 г.

    • Стоимость:

      8 400 руб

    Заказать такую же работу
  • Транспорт

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

    • Вид работы:

      Исправление и доработка готовой работы

    • Выполнена:

      7 июня 2021 г.

    • Стоимость:

      1 200 руб

    Заказать такую же работу
  • Не получается написать работу самому?

    Доверь это кандидату наук!