Что такое комбинаторные методы

Комбинаторное мышление

Логическое мышление, творческое мышление, аналитическое мышление – известные всем виды мышления. Однако, есть и такие, услышать о которых можно не часто. К их числу относится комбинаторное мышление, и в этой статье мы хотим поговорить именно о нем: рассмотрим само понятие, побеседуем на тему актуальности его развития (а о развитии мышления глобально вы можете узнать отсюда) и коротко коснемся комбинаторики – раздела математики, изучающего комбинаторные задачи.

Что такое комбинаторное мышление

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

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

Ко всему прочему есть еще и разные типы комбинаторного мышления. Всего их три категории:

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

О развитии комбинаторного мышления

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

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

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

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

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

Сама комбинаторика возникла в 17 веке и изначально рассматривала комбинаторные задачи, касающиеся азартных игр. По мере их изучения вырабатывались общие методы решения задач и определялись формулы, позволяющие подсчитывать число комбинаций. Также появление комбинаторики тесно связано с теорией вероятности, для решения задач которой изначально было необходимо уметь вести подсчет количества различных комбинаций, подчиненных конкретным условиям. В 18 веке такие задачи изучались Г. Галилеем, Н. Тартальей, Д. Кардано, а позже – математиками П. Фермой, Б. Паскалем и другими. Множество достижений в представленной области принадлежит также Л. Эйлеру. Задачами из области комбинаторики были заинтересованы, кроме всех прочих, математики, составлявшие и разгадывавшие шифры и изучавшие древние письменности.

Сегодня же комбинаторика применятся с целью решения огромного количества теоретических и практических задач, где речь идет о возможных исходах, в том числе и благоприятных, для конкретных случаев. Применение она нашла и во всех научно-технических областях, включая биологию (посредством нее, например, исследуется состав ДНК и белков), химию, механику и другие области.

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

И в заключение еще несколько слов о связи комбинаторного мышления и математики.

Комбинаторное мышление и математика

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

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

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

Надеемся, эта информация будет для вас полезной, но выводы делать, естественно, вам.

Источник

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

Комбинато́рика (Комбинаторный анализ) — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими другими областями математики — алгеброй, геометрией, теорией вероятностей и имеет широкий спектр применения в различных областях знаний (например в генетике, информатике, статистической физике).

Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».

Иногда под комбинаторикой понимают более обширный раздел дискретной математики, включающий, в частности, теорию графов.

Содержание

Примеры комбинаторных конфигураций и задач

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

Примерами комбинаторных задач являются:

Разделы комбинаторики

Перечислительная комбинаторика

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

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

Типичным примером задач данного раздела является подсчёт количества перестановок. Другой пример — известная Задача о письмах.

Структурная комбинаторика

К данному разделу относятся некоторые вопросы теории графов, а также теории матроидов.

Экстремальная комбинаторика

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

Теория Рамсея

Теория Рамсея изучает наличие регулярных структур в случайных конфигурациях элементов. Примером утверждения из теории Рамсея может служить следующее:

в группе из 6 человек всегда можно найти трёх человек, которые либо попарно знакомы друг с другом, либо попарно незнакомы.

В терминах структурной комбинаторики это же утверждение формулируется так:

в любом графе с 6 вершинами найдётся либо клика, либо независимое множество размера 3.

Вероятностная комбинаторика

Этот раздел отвечает на вопросы вида: какова вероятность присутствия определённого свойства у заданного множества.

Топологическая комбинаторика

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

Инфинитарная комбинаторика

Инфинитарная комбинаторика (англ.) — применение идей и методов комбинаторики к бесконечным (в том числе, несчётным) множествам.

Открытые проблемы

Комбинаторика, и в частности, теория Рамсея, содержит много известных открытых проблем, подчас с весьма несложной формулировкой. Например, неизвестно, при каком наименьшем N в любой группе из N человек найдутся 5 человек, либо попарно знакомых друг с другом, либо попарно незнакомых (хотя известно, что 49 человек достаточно). [1]

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

См. также

Примечания

Литература

Ссылки

Полезное

Смотреть что такое «Комбинаторика» в других словарях:

КОМБИНАТОРИКА — (лат. ars combinatoria). Наука о законах сочетания известных предметов. Словарь иностранных слов, вошедших в состав русского языка. Чудинов А.Н., 1910. КОМБИНАТОРИКА лат. ars combinatoria. Наука о законах сочетания известных предметов. Объяснение … Словарь иностранных слов русского языка

КОМБИНАТОРИКА — КОМБИНАТОРИКА, и, жен. Раздел дискретной математики, изучающий всевозможные сочетания и расположения предметов. | прил. комбинаторный, ая, ое. К. анализ. Толковый словарь Ожегова. С.И. Ожегов, Н.Ю. Шведова. 1949 1992 … Толковый словарь Ожегова

КОМБИНАТОРИКА — раздел математики, где рассматриваются сочетания, размещения, перестановки элементов и связанные с ними задачи. Широко применяется при вероятностном моделировании геол. процессов. Геологический словарь: в 2 х томах. М.: Недра. Под редакцией К. Н … Геологическая энциклопедия

комбинаторика — — [http://www.dunwoodypress.com/148/PDF/Biotech Eng Rus.pdf] Тематики биотехнологии EN combinatorics … Справочник технического переводчика

КОМБИНАТОРИКА — раздел математики, посвящённый решению задач выбора и расположения элементов из некоторого основного (обычно конечного) множества в соответствии с заданными правилами. Простейшими задачами К. являются перестановки, сочетания и размещения … Большая политехническая энциклопедия

комбинаторика — и; ж. [лат. combinare соединять] Раздел математики, изучающий все возможные способы простейших перестановок элементов, цифр, каких л. данных. * * * комбинаторика раздел математики, в котором изучаются простейшие «соединения». Перестановки … … Энциклопедический словарь

Комбинаторика — 1) то же, что математический Комбинаторный анализ. 2) Раздел элементарной математики, связанный с изучением количества комбинаций, подчинённых тем или иным условиям, которые можно составить из заданного конечного множества объектов… … Большая советская энциклопедия

Комбинаторика — ж. Раздел математики, изучающий различного рода соединения элементов: перестановки, сочетания, размещения. Толковый словарь Ефремовой. Т. Ф. Ефремова. 2000 … Современный толковый словарь русского языка Ефремовой

комбинаторика — комбинаторика, комбинаторики, комбинаторики, комбинаторик, комбинаторике, комбинаторикам, комбинаторику, комбинаторики, комбинаторикой, комбинаторикою, комбинаториками, комбинаторике, комбинаториках (Источник: «Полная акцентуированная парадигма… … Формы слов

Источник

Учебное пособие «Элементы комбинаторики»

Онлайн-конференция

«Современная профориентация педагогов
и родителей, перспективы рынка труда
и особенности личности подростка»

Свидетельство и скидка на обучение каждому участнику

Министерство образования, науки и молодежной политики Краснодарского края

для студентов специальности

09.02.03 «Программирование в компьютерных системах»

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

Соединения без повторений

Размещения без повторений

Перестановки без повторений

Сочетания без повторений

Соединения с повторениями

Размещения с повторениями

Перестановки с повторениями

Сочетания с повторениями

Свойства разложения бинома

Задания для самостоятельного решения

Тест для самоконтроля

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

Знание закономерностей массовых случайных явлений (предмет теории вероятностей) и важнейших методов и приёмов обработки результатов наблюдений (изучает математическая статистика) необходимо современному программисту при разработке алгоритмов решения практических задач. Изучение же теории вероятностей и математической статистики немыслимо без предварительного знакомства с основами комбинаторики.

Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве». Сегодня комбинаторные методы используются для решения проблем теории информации, задач линейного программирования, для решения транспортных задач и много другого. Комбинаторные задачи представляют богатый материал для изучения основных конструкций, методов и приемов программирования, позволяют показать не только красоту математики, но и возможности новых компьютерных технологий при решении практических математических задач. Задачи дискретной математики, к которым относятся многие задачи практического программирования, часто сводятся к перебору различных комбинаторных конфигураций объектов и выбору среди них наилучшего, с точки зрения условия той или иной задачи. Поэтому знание алгоритмов генерации наиболее распространенных комбинаторных конфигураций является необходимым условием успешного решения задач в целом.

1. Основные понятия комбинаторики

1.1. Понятие о комбинаторике

Опр. Комбинаторика – раздел математики, изучающий различные комбинации элементов, обладающие определёнными свойствами.

(!!) В отличие от множеств комбинации элементов могут содержать одинаковые (повторные) элементы.

1.2. Задача, приводящая к понятию факториала.

Опр. Произведение всех натуральных чисел от 1 до п включительно называется п-факториалом и обозначается п!

(!!) Считается, что о! = 1.

(!!) Факториал отрицательного числа не существует.

Пример 1. Вычислите:

Пример 2. Упростите выражение:

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

При решении комбинаторных задач часто применяются два важных правила.

Правило сложения: Если некоторый элемент « а » можно выбрать т числом способов, а другой элемент « в » – п числом способов, то выбор элемента « либо а, либо в » можно сделать ( т + п ) числом способов.

Задача 1. В группе 20 девушек и 5 юношей. Каким числом способов можно выбрать старосту?

/ Старостой может быть выбрана одна из 20 девушек или один из 5 юношей, а значит, общее число способов выбора старосты равно 20+5=25 /

(!!) При использовании правила суммы в такой формулировке нужно следить, чтобы ни один из способов выбора объекта А не совпадал с каким-нибудь способом выбора объекта В. Если такие совпадения есть, то правило суммы утрачивает силу и получается лишь (m+n-k) способов выбора, где k-число совпадений.

/ Английский или немецкий язык знают 49 + 32 – 15 = 66 преподавателей. А значит, не знают ни одного из этих языков 77 – 66 = 10 преподавателей. /

Правило умножения : Если некоторый элемент « а » можно выбрать т числом способов, а затем элемент « в » – п числом способов, то выбор пары « а и в » можно осуществить ( т∙п ) числом способов.

Задача 3. В группе 30 человек. Необходимо выбрать старосту и профорга. Сколькими способами это можно сделать?

/ Старостой может быть выбран любой из 30 учащихся, т.е. существует 30 способов выбора старосты. После того как староста уже выбран, профоргом можно выбрать любого из оставшихся 29 учащихся. Таким образом, одному способу выбора старосты соответствуют 29 способов выбора профорга. Следовательно, общее число способов выбора старосты и профорга равно 30 ∙29 = 870. /

(!!) Правила сложения и умножения имеют место для любого конечного числа элементов.

Задача 4. Сколько трёхзначных чётных чисел можно составить из цифр 0,1,2,3,4,5,6, если цифры могут повторяться?

/ При составлении трёхзначного числа авс из данных цифр вместо а можно взять любую цифру, кроме нуля (6 возможностей), вместо в можно взять любую из них (7 возможностей), вместо с можно взять любую из цифр 0,2.4.6 (4 возможности). Т.о., согласно правилу умножения, имеем 6∙7∙4= 168 способов составить число, удовлетворяющее условию задачи. /

(!!) Часто при решении комбинаторных задач работают оба правила.

Задача 5. Имеются 20 изделий 1-го сорта и 30 изделий 2-го сорта. Необходимо выбрать два изделия одного сорта. Сколькими способами это можно сделать?

/ По правилу умножения, два изделия 1-го сорта можно выбрать 20∙19=380 способами. Аналогично. Два изделия 2-го сорта можно выбрать 30∙29=870 способами. Т.к. по условию задачи следует выбрать два изделия одного сорта, неважно какого, то общее число способов выбора изделий одного сорта равно 380 + 870 = 1250. /

Задача 6. Сколько однозначных, двузначных и трехзначных четных чисел можно составить из цифр 0,1,2,3, если цифры могут повторяться?

/ Очевидно, что из данных цифр можно составить только одно четное однозначное число – 2.

При составлении двузначного числа ав из данных цифр вместо а можно взять любую цифру, кроме нуля (3 возможности), вместо в можно взять взять любую из цифр 0 и 2 (2 возможности). Т.о, согласно правилу умножения, имеем 3∙2= 6 способов составить нужное нам число.

При составлении трехзначного числа авс из данных цифр вместо а можно взять любую цифру, кроме нуля (3 возможности), вместо в можно взять любую из них (4 возможности), вместо с можно взять любую из цифр 0 и 2 (2 возможности). Т.о., согласно правилу умножения, имеем 3∙4∙2= 24 способа составить число, удовлетворяющее условию задачи.

Применяя правило сложения, получим: 1 + 6 + 24 = 31 /

2. Соединения без повторений

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

2.1. Размещения без повторений

Опр. Размещениями из п элементов по т (0) называются соединения, содержащие т различных элементов и отличающиеся или составом, или порядком их расположения .

Обозначение: («а из эн по эм»)

Ясно, что на первое место можно поместить любой из п эл-тов. Т.о., = п .

Если на первом месте стоит один из п элементов, то на второе место можно поместить один из ( п-1 ) оставшихся элементов. А значит, согласно правилу умножения,

Выведем более универсальную формулу, для чего умножим и разделим произведение, стоящее в правой части формулы, на ( п-т)!. Получим:

Задача 7. Сколько различных натуральных чисел можно составить из цифр 1, 2, 3, 4, 5 при условии, что любая из цифр в написании числа встречается не более одного раза?

По правилу сложения: 5+20+60+120+120= 325 /

2.2. Перестановки без повторений

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

Задача 8. Сколько существует четырехзначных чисел, состоящих из цифр 1,3,5 и 7 (без повторений).

Задача 9. Сколькими способами можно расставить на полке в один ряд семь книг, среди которых четыре книги разных авторов и трёхтомник одного автора, так, чтобы книги трёхтомника стояли рядом?

/ Если считать трехтомник за одну книгу, то будет 5 книг, которые можно переставить Р ₅ = 5! = 120 способами. Т.к. книги трёхтомника можно переставлять между собой Р ₃ = 3! = 6 способами, то по правилу умножения, всего возможно 120·6 = 720 перестановок /

2.3. Сочетания без повторений

Опр. Сочетаниями из п элементов по т ( называются соединения т различных элементов, отличающиеся лишь составом (порядок не играет роли).

Обозначение: («цэ из эн по эм»)

Задача 10. Сколькими способами читатель может выбрать две книжки из пяти имеющихся?

Задача 11. В соревнованиях по волейболу участвуют 8 команд. Насколько более продолжительным будет турнир, организованный по круговой системе, чем по олимпийской?

3. Соединения с повторениями

3.1. Размещения с повторениями

Задача 12. Сколько различных трёхзначных чисел можно составить из цифр 1 и 2?

Задача 13. Сколько различных двузначных чисел можно составить из цифр 1, 2, 3?

3.2. Перестановки с повторениями

Если бы все т элементов были между собой различны, то таких перестановок было бы т! = (т ₁ + т ₂ + … + т _п )! Но так как не все элементы различны, то их будет меньше.

Задача 14. Сколько различных пятизначных чисел можно составить из цифр 1, 2, 3, если 1 встречается 1 раз, 2 – 2 раза, 3 – 2раза?

Задача 15. Сколькими способами можно переставить буквы в слове « математика », чтобы получить всевозможные различные наборы букв?

3.3. Сочетания с повторениями

Очевидно, единиц записано т ₁ + т ₂ + … + т _п = т штук, а нулей – ( п – 1) . Если какой-то элемент не входит в наше сочетание, то вместо соответствующей групы единиц пишется нуль.

Задача 16. Имеются конфеты трёх сортов в коробках. Сколько можно составить различных наборов из пяти коробок?

4.1. Треугольник Паскаля

Формула = имеет несколько следствий:

— при п = 2 и т = 1 получим:

— при т = 4 и т = 3: и т.д.

Если числа расположить в виде следующей треугольной таблицы

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

Числа, стоящие в 3-ей и 4-ой строках треугольника Паскаля, появляются при возведении двучлена (бинома) а + в в квадрат и в куб. Действительно, формулы

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

Используя знак суммы, эту формулу можно записать так:

Правая часть формулы Ньютона называется разложением натуральной степени бинома .

Коэффициенты называются биномиальными коэффициентами .

Пример 4. Возведите в 7-ю степень двучлен (х+1).

/ (х+1) 7 = + + + + + + = + 7 + 21 + 35 + 35 + 21 + 7х + 1 /

4.3. Свойства разложения бинома

Число всех членов разложения на 1 больше показателя степени бинома, т.е. равно п+1.

Сумма показателей степеней « а » и « в » каждого члена разложения равна показателю степени бинома ( п-т+т=п ). При этом показатель степени при « а » в любом следующем члене разложения на единицу меньше, чем в предыдущем, а показатель степени « в » – на единицу больше.

Общий член разложения (обозначим его Т _т+1 ) имеет вид:

Т обозначает член разложения, а индекс т+ 1 – его порядковый номер в разложении бинома, считая слева направо. Так,

Задания для самостоятельного решения

1. В президиум избрали 3 человека. Каким числом способов они могут распределить обязанности председателя, секретаря и члена?

2. Сколько всех четырёхзначных чисел можно составить из цифр 1, 5, 6, 7?

3. Сколько существует двузначных чисел, имеющих обе чётные цифры?

4. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?

5. Сколько существует шестизначных чисел, которые делятся на 5?

6. Сколько различных натуральных чисел можно составить из цифр 1, 2, 3, 4, 5 при условии, что любая из цифр в написании числа встречается не более одного раза?

7. Любой телефонный номер состоит из пяти цифр. Сколько всего телефонных номеров, не содержащих других цифр, кроме 1, 2 и 3?

8. Сколькими способами можно расположить в ряд 2 зелёные и 4 красные лампочки?

9. Сколькими способами можно выбрать четыре монеты из 4-х пятикопеечных и 4-х десятикопеечных монет?

10. Сколькими способами можно разместить 8 пассажиров в 2 вагона?

11. В кондитерской имеется 5 сортов пирожных. Сколькими способами можно выбрать набор из 4-х пирожных?

Источник