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

Комбинаторные задачи

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

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

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

Содержание

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

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

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

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

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

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

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

Типичным примером задач данного раздела является подсчете количества перестановок (см. выше). Число перестановок n-элементного множества равно факториалу числа n, то есть n!. Другой пример — известная Задача о письмах.

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Литература

Полезное

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

КОМБИНАТОРНЫЕ ЗАДАЧИ — класс и ческ незадачи выбора и расположения элементов конечного множества, имеющие в качестве исходной нек рую формулировку развлекательного содержания типа головоломок. Одной из классических К. з., фигурирующей еще в мифах Древнего Востока,… … Математическая энциклопедия

Комбинаторные методы решения экономических задач — [com­binatorial methods in economics] совокупность (не вполне определенная) методов, основанных на идеях комбинаторики отдела математики, изучающего вопросы, связанные с размещением и взаимным расположением частей конечного множества объектов. С… … Экономико-математический словарь

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

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

История комбинаторики — освещает развитие комбинаторики раздела конечной математики, который исследует в основном различные способы выборки заданного числа m элементов из заданного конечного множества: размещения, сочетания, перестановки, а также перечисление и смежные… … Википедия

Удовлетворение ограничений — Содержание 1 Введение 2 История 3 Примеры задач удовлетворения ограничений … Википедия

ВЕРОЯТНОСТЕЙ ТЕОРИЯ — занимается изучением событий, наступление которых достоверно неизвестно. Она позволяет судить о разумности ожидания наступления одних событий по сравнению с другими, хотя приписывание численных значений вероятностям событий часто бывает излишним… … Энциклопедия Кольера

Нейронная сеть Хопфилда — Нейронная сеть Хопфилда полносвязная нейронная сеть с симметричной матрицей связей. В процессе работы динамика таких сетей сходится (конвергирует) к одному из положений равновесия. Эти положения равновесия являются локальными минимумами… … Википедия

ВЕРОЯТНОСТЕЙ ТЕОРИЯ — математическая наука, позволяющая по вероятностям одних случайных событий находить вероятности других случайных событий, связанных к. л. образом с первыми. Утверждение о том, что к. л. событие наступает с вероятностью, равной, напр., 1/2, еще не… … Математическая энциклопедия

Псевдополиномиальный алгоритм — полиномиальный алгоритм, проявляющий экспоненциальный характер только при очень больших значениях числовых параметров. Более строгое определение выглядит так. Пусть M(z) – некоторая функция, задающая значение числового параметра индивидуальной… … Википедия

Источник

«Комбинаторные задачи и способы их решения»

Ищем педагогов в команду «Инфоурок»

Описание презентации по отдельным слайдам:

Комбинаторные задачи и способы их решения Выполнил учащийся 6 класса средней школы при Посольстве России в Израиле Мидхатов Казим учитель математики Акишина Л.В.

Оглавление. Введение. Что такое комбинаторика и комбинаторные задачи. Из истории комбинаторики. Способы решения комбинаторных задач. Комбинаторные задачи. Используемая литература.

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

2. Что такое комбинаторика и комбинаторные задачи. Область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов, называется комбинаторикой. Слово «комбинаторика» происходит от латинского слова combinate, которое означает «соединять», «сочетать». Комбинаторные задачи – это задачи, требующие осуществления перебора всех возможных вариантов или подсчета их числа.

Древний период. Комбинаторные мотивы можно заметить в символике китайской «Книги Перемен» (V век до н. э.). По мнению её авторов, всё в мире комбинируется из различных сочетаний мужского и женского начал, а также восьми стихий: земля, горы, вода, ветер, гроза, огонь, облака и небо. Историки отмечают также комбинаторные проблемы в руководствах по игре в Го и другие игры. Большой интерес математиков многих стран с древних времён неизменно вызывали магические квадраты. Классическая задача комбинаторики: «сколько есть способов извлечь m элементов из N возможных» упоминается ещё в сутрах древней Индии (начиная примерно с IV века до н. э.). Индийские математики, видимо, первыми открыли биномиальные коэффициенты и их связь с биномом Ньютона. Во II веке до н. э. индийцы знали, что сумма всех биноминальных коэффициен- тов степени n равна. Античные греки также рассматривали отдельные комбинаторные задачи, хотя систематическое изложение ими этих вопросов, если оно и существовало, до нас не дошло. Хрисипп (III век до н. э.) и Гиппарх (II век до н. э.) подсчитывали, сколько следствий можно получить из 10 аксиом; методика подсчёта нам неизвестна, но у Хрисиппа получилось более миллиона, а у Гиппарха — более 100000. Аристотель при изложении своей логики безошибочно перечислил все возможные типы трёхчленных силлогизмов. Аристоксен рассмотрел различные чередования длинных и коротких слогов в стихотворных размерах. Какие-то комбинаторные правила пифагорейцы, вероятно, использовали при построении своей теории чисел и нумерологии (совершенные числа, фигурные числа, пифагоровы тройки и др.).

Средневековье. В XII веке индийский математик Бхаскара в своём основном труде «Лилавати» подробно исследовал задачи, связанные с перестановками и сочетаниями, включая перестановки с повторениями. В Западной Европе ряд глубоких открытий в области комбинаторики сделали два еврейских исследователя, Авраам ибн Эзра (XII век) и Леви бен Гершом (он же Герсонид, XIV век). Ибн Эзра обнаружил симметричность биномиальных коэффициентов, а Герсонид дал явные формулы для их подсчёта и применения в задачах вычисления числа размещений и сочетаний. Несколько комбинаторных задач содержит «Книга абака» (Фибоначчи, XIII век). Например, он поставил задачу найти наименьшее число гирь, достаточное для взвешивания любого товара весом от 1 до 40 фунтов.

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

Одним из первых занялся подсчетом числа различных комбинаций при игре в кости итальянский математик Тарталья. Он составил таблицу, показывающую, сколькими способами могут выпасть r костей. Однако при этом не учитывалось, что одна и та же сумма очков может быть получена различными способами (например, 1+3+4 = 4+2 +2). Теоретическое исследование вопросов комбинаторики предприняли в XVII веке французские ученые Паскаль и Ферма. Исходным пунктом их исследований тоже были проблемы азартных игр. Дальнейшее развитие комбинаторики связано с именами Якова Бернулли, Лейбница и Эйлера. Однако и у них основную роль играли приложения к различным играм (лото, солитер и др.).

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

Дерево возможных вариантов. Самые разные комбинаторные задачи решаются с помощью составления специальных схем. Внешне такая схема напоминает дерево, отсюда и название метода – дерево возможных вариантов. Задача. Задача. Какие трехзначные числа можно составить из цифр 0, 3, 5? Решение. Построим дерево возможных вариантов, учитывая, что 0 не может быть первой цифрой в числе. Далее.

Задача № 7. В нашем классе 8 человек. Нам нужно выбрать старосту класса и его заместителя. Сколько возможно вариантов выбора старосты и его заместителя. Задача № 8. У Васи есть 2 пары обуви, 2-е брюк и три рубашки. Сколько у него вариантов одеться по-разному? Задача № 9. Имеется батон, черный хлеб, сыр, колбаса и джем. Сколько видов бутербродов можно приготовить? Задача № 10. На тарелке лежат 5 груш и 4 яблока. Сколькими способами можно выбрать один плод? Задача № 11. На тарелке лежат 5 яблок и 4 апельсина. Сколькими способами можно выбрать пару плодов, состоящую из яблока и апельсина? Задача № 12. Учащиеся 6 класса решили обменяться фотографиями. Сколько фотографий для этого потребуется, если в классе 8 человек?

6. Используемая литература. Вероятность и статистика. 5-9 кл.: пособие для общеобразоват. учеб. заведений / Е. А. Бунимович, В. А. Булычев. – 2-е изд. стереотип. – М.: Дрофа, 2004. Виленкин Н.Я. Комбинаторика, М., 1969 г. Виленкин Н.Я. «Индукция. Комбинаторика», М. «Просвещение», 1976 г. Ткачёва М. В. «Домашняя математика», М. Просвещение, 1993 г. Интернет-ресурсы.

Источник

Какие задачи называются комбинаторными

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

В зависимости от правил составления можно выделить три типа комбинаций: перестановки, размещения, сочетания.

Предварительно познакомимся с понятием факториала.

Произведение всех натуральных чисел от 1 до n включительно называют

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

Число перестановок можно вычислить по формуле

Запишем эту формулу в факториальной форме:

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

Источник

Виды комбинаторных задач и способы их решения

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

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

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

С точки зрения теории множеств комбинаторика изучает подмножества конечных множеств, их объединения и пересечения, а также различные способы упорядочивания этих подмножеств.

В математической литературе отмечаются три отличительные черты комбинаторных задач, которые заключаются в следующем:

1. Все объекты, описываемые в задачах, состоят из отдельных дискретных элементов;

2. Множества этих элементов конечны.

3. Преимущество отдано двум видам операций: отбор подмножеств и упорядочению элементов множества.

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

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

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

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

Задача 2. На первой прямой взяты три точки, а на параллельной ей прямой четыре точки. Сколько существует треугольников, вершинами которых являются эти точки?

Задача 3. Сколько различных четырехзначных чисел имеется в пятиричной системе счисления?

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

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

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

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

Помимо термина «перебор» в литературе можно встретить и другие: «метод проб и ошибок», «метод проб», «прием целенаправленных проб», «способ подбора и догадки».

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

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

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

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

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

A.M. Пышкало, Стойлова Л.П., Рожденственская В.В. графом называют «особый чертеж, состоящий из точек и линий, идущих из одной точки в другую».

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

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

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

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

Источник

КОМБИНАТОРИКА

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

Правила сложения и умножения в комбинаторике

Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить m способами, а В – n способами, то выполнить одно любое из этих действий (либо А, либо В) можно n + m способами.

Пример 1.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить одного дежурного?

Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.

По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.

Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n₁ способами, второе действие n₂ способами, третье – n₃ способами и так до k-го действия, которое можно выполнить n_k способами, то все k действий вместе могут быть выполнены:

Пример 2.

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

Первым дежурным можно назначить либо мальчика, либо девочку. Т.к. в классе учится 16 мальчиков и 10 девочек, то назначить первого дежурного можно 16+10=26 способами.

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

По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.

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

Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов ?

Пример 3.

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

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

.

Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m () из этих (n*r) предметов?

.

Пример 4.

В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?

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

.

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

Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?

Пример 5.

В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?

В данной задаче мы не просто выбираем фотографии, а размещаем их на определенных страницах газеты, причем каждая страница газеты должна содержать не более одной фотографии. Таким образом, задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:

Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.

Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n предметов, среди которых есть одинаковые?

Пример 6.

У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера– составить каталог. Сколько различных пятизначных номеров может составить мальчик?

Можно считать, что опыт состоит в 5-кратном выборе с возращением одной из 3 цифр (1, 3, 7). Таким образом, число пятизначных номеров определяется числом размещений с повторениями из 3 элементов по 5:

.

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

Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?

Пример 7.

Сколько можно составить четырехбуквенных «слов» из букв слова«брак»?

Генеральной совокупностью являются 4 буквы слова «брак» (б, р, а, к). Число «слов» определяется перестановками этих 4 букв, т. е.

Для случая, когда среди выбираемых n элементов есть одинаковые (выборка с возвращением), задачу о числе перестановок с повторениями можно выразить вопросом: сколькими способами можно переставить n предметов, расположенных на n различных местах, если среди n предметов имеются k различных типов (k

Пример 8.

Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?

Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв. Следовательно, число перестановок с повторениями равно

ОПОРНЫЙ КОНСПЕКТ ПО РАЗДЕЛУ «КОМБИНАТОРИКА»

Источник