Комбинаторика - математика и искусство

Перейти к контенту

Главное меню:

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

Другие разделы

Число, место и комбинация - три взаимно перекрещивающиеся, но отличные сферы мыщления, к которым можно отнести все математические идеи.
Д.Сильвестр.

КОМБИНАТОРИКА, раздел математики, в котором изучаются простейшие «соединения».

  • Перестановки — соединения, которые можно составить из  n предметов, меняя всеми возможными способами их порядок

  • Размещения — соединения, содержащие по  m предметов из числа  n данных, различающиеся либо порядком предметов, либо самими предметами

  • Сочетания — соединения, содержащие по  m предметов из  n, различающиеся друг от друга, по крайней мере, одним предметом

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


Наиболее употребляемые комбинаторные конфигурации

Число размещений. Число упорядоченных различных k элементов некоторого n-элементного множества. Обозначается A nk, и вычисляется по формуле: A nk = n! / (n - k)!
Здесь и далее символ n! (читается n факториал) обозначает произведение всех натуральных чисел от 1 до n включительно. Считается, что 0!=1!=1.
Число перестановок. Число различных способов, которыми может быть упорядочено n-элементное множество. Обозначается P n, и вычисляется по формуле: P n=n!.
Число сочетаний. Произвольное k-элементное подмножество n-элементного множества. Порядок элементов не важен. Обозначается C nk, вычисляется по формуле: C nk = n! / ( k!(n - k)! )
Зависимость между числом размещений, перестановок и сочетаний выражается формулой A nk=C nkP k.
Существует два основных правила, используемые при решение задач комбинаторики.
Правило суммы: пусть объект 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 века возрождается интерес к комбинаторик
е в связи с развитием дискретной математики и кибернетики, а так же в связи с широким использованием компьютеров.

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


/БДЭМатематика/


Статья из журнала "Наука и жизнь"( рубрика Математические досуги)

БИНОМ НЬЮТОНА И ТРЕУГОЛЬНИК ПАСКАЛЯ

Сегодня, как и лет тридцать-сорок назад, абитуриенты на вступительных экзаменах в вуз традиционно опасаются вытянуть билет с вопросом о биноме Ньютона. (Автор формулы
великий английский физик, математик, астроном и философ сэр Исаак Ньютон.) Дело не только в том, что формула кажется сложной. Изучение её то включали в программу средней школы, то выводили за рамки основного курса, но в серьёзных вузах экзаменаторы спрашивали и продолжают спрашивать о биноме Ньютона.
На самом деле бояться тут особенно нечего. Бином Ньютона — формула разложения произвольной натуральной степени двучлена  в многочлен. Каждый из нас знает наизусть формулы «квадрата суммы» (a+b)² и «куба суммы» (a+b)³, но при увеличении показателя степени с определением коэффициентов при членах многочлена начинаются трудности. Чтобы не совершить ошибку и применяется формула бинома Ньютона:


В более общем виде формула коэффициентов в биноме записывается так:


где k - порядковый номер слагаемого в многочлене.

Напомним, что факториал — произведение натуральных чисел от 1 до n, то есть 1х2хЗх..n— обозначается например, 4!=1x2x3x4=24.

Запомнить формулу действительно непросто. Но попытаемся её проанализировать. Видно, что в любом многочлене присутствуют a^n и b^n с коэффициентами 1. Ясно также, что всякий иной член многочлена выглядит как произведение определённых степеней каждого из слагаемых двучлена причём сумма степеней всегда равна n. Например, в выражении (a+b)³³+За²Ь+ЗаЬ²³ сумма степеней сомножителей во всех членах равна трём (3, 2+1,1+2,3). То же самое справедливо и для любой другой степени. Вопрос лишь втом, какие коэффициенты следует ставить при членах.

Видимо, для того чтобы облегчить труд школяров и студентов, великий французский математик и физик Блез Паскаль триста пятьдесят лет назад придумал специальный инструмент для определения этих самых коэффициентов — «треугольник Паскаля».
Строится он следующим образом. В вершине треугольника пишем 1. Единица соответствует выражению  (a+b), поскольку любое число, возведённое в нулевую степень, даёт единицу. Достраивая треугольник, ниже пишем ещё по единице. Это коэффициенты разложения того же двучлена, возведённого в первую степень: (a+b)¹=a+b. Идём дальше. Стороны треугольника образуют единицы, а между ними — сумма двух единичек, находящихся сверху, то есть 2. Это и есть коэффициенты трёхчлена «квадрат суммы»: +2ab+b² .

Следующий ряд, как и предыдущий, начинается и заканчивается единицами, а между ними — суммы цифр, находящихся сверху: 1, 3, 3,
1. Мы получили коэффициенты разложения « куба суммы ». Ряд коэффициентов двучлена четвёртой степени составят 1, 4, 6, 4, 1 и так далее.
Для примера с помощью треугольника Паскаля разложим в многочлен сумму двучленов в
шестой степени:
(
a+b)+6а Ь + 15а Ь² +20а³Ь³+ 15а² Ь+6аЬ.

Всё очень несложно и запоминается на всю жизнь. Кстати, самостоятельно вспомнить и вывести формулу бинома Ньютона, нарисовав на черновике треугольник Паскаля, тоже намного проще.

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


 
Copyright 2016. All rights reserved.
Назад к содержимому | Назад к главному меню