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

Главная » Математика » Комбинаторика

Слово «комбинаторика» происходит от латинского combina — сочетать, соединять. Это раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисление элементов) и отношения на них.

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

  • Число размещений. Число упорядоченных различных k элементов некоторого n-элементного множества. Обозначается Ank, и вычисляется по формуле:
  • Ank = n! / (n - k)!

Здесь и далее символ n! (читается n факториал) обозначает произведение всех натуральных чисел от 1 до n включительно. Считается, что 0!=1!=1.

  • Число перестановок. Число различных способов, которыми может быть упорядочено n-элементное множество. Обозначается Pn, и вычисляется по формуле: Pn=n!.
  • Число сочетаний. Произвольное k-элементное подмножество n-элементного множества. Порядок элементов не важен. Обозначается Cnk, вычисляется по формуле:
  • Cnk = n! / ( k!(n - k)! )

Зависимость между числом размещений, перестановок и сочетаний выражается формулой Ank=CnkPk.

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

Правило суммы: пусть объект A можно выбрать m способами, а объект B — n способами, и существует k общих способов выбора объектов A и B одновременно, тогда один из объектов A или B можно выбрать (m + n - k) способами.

Правило произведения: пусть объект A можно выбрать m способами, а объект B — n способами, причем выбор B не зависит от выбора A, тогда пару объектов A и B можно выбрать m * n способами.

Комбинаторика развивалась параллельно с другими математическими теория, такими как алгебра, теория чисел, теория вероятно, с которыми комбинаторика тесно связана. Еще во 2 веке до нашей эры математикам Индии были известны формулы вычисляющие число сочетаний. Рождение комбинаторики как математического раздела связано с работами Блеза Паскаля и Пьера Ферма, положившими основу теории вероятности. Эти труды содержали принципы определения числа комбинаций элементов конечного множества, тем самым устанавливая связь комбинаторики с теорией вероятности.

Понятие «комбинаторика» было введено Г. Лейбницем в 1666 году в работе «Рассуждения о комбинаторном искусстве», в которой так же приводится научное объяснение теории сочетаний и перестановок. Большой вклад в развитии комбинаторики имели работы Я. Бернулли, посвященные теории вероятности, в которых изложены некоторые комбинаторные понятия и указаны их применения к вычислению вероятностей. Бернулли так же впервые занимался изучение числа размещений.

В середине 20 века возрождается интерес к комбинаторики в связи с развитием дискретной математики и кибернетики, а так же в связи с широким использованием компьютеров.

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

Поделиться


© copyright 2012 - 2016 Детская энциклопедия. Все о человеке, нашей планете, истории.