Виды комбинаторных задач

ЭЛЕМЕНТЫ КОМБИНАТОРИКИ

ГЛАВНЫЕ ПОНЯТИЯ

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

Разглядим пара примеров:

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

2) верные записи математических выражений, составленных посредством математических знаков;

3) разнообразные комбинации цветов (букеты) кроме этого являются примерами конструкций (увидим, что в этом случае правила составления букетов смогут быть достаточно сложными а также тяжело объяснимыми);

4) радиоустройства, конструируемые как соединения разных радиодеталей, кроме этого возможно разглядывать как комбинаторные объекты;

5) мозаики, составляемые из фигур заданной формы.

К постановкам задач изучения комбинаторных объектов приводят разные практические потребности в разнообразных областях деятельности.

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

Ясно, что данный полином является суммой вида: Тут am,n — коэффициент при произведении переменных xmyn.

Для нахождения значения произвольного коэффициента am,n достаточно выяснить, какое количество различными методами в последовательности из k перемножаемых выражений (x + y) возможно выделить m таких, из которых в составляемое произведение входит x. Наряду с этим из остальных m — k выражений x + y произведения (x + y)k выбирается y.

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

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

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

ВИДЫ КОМБИНАТОРНЫХ ЗАДАЧ

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

1. Существует ли конструкция, которую возможно выстроить из элементов данного множества по заданным правилам?

2. Как выглядит описание структуры всех комбинаторных объектов, владеющих заданными особенностями?

3. Как выстроить пример комбинаторного объекта, имеющего заданные особенности?

4. Как выстроить все комбинаторные объекты с заданными особенностями?

5. какое количество существует разных комбинаторных объектов, владеющих заданными особенностями?

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

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

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

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

Примеры комбинаторных задач | Алгебра 9 класс #30 | Инфоурок


Также читать:

Понравилась статья? Поделиться с друзьями: