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

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

Комбинаторные задачи обладают общей особой приметой: явл. вопрос задачи, кот. всегда можно сформулировать так, что он будет начинаться словами: «Сколько ?», «Сколькими способами …?».

Правило произведения:Пусть нам даны k множеств по n₁, n₂, n₃, n₄,... ,n_k элементов каждое, и нам нужно произвести выбор по одному в каждом из множеств, тогда число возможных способов находим так: N = n₁ n₂ n₃ n₄ ...n_k.

Обобщение: на каждое из m мест может быть поставлен элемент n – элементного множества. Тогда количество способов расположения элементов можно найти по формуле mⁿ.

Перестановкой из n элементов называют упорядоченный набор этих элементов. Обозначают P_n= n !

Произведение P_n = 10•9•8•...•2•1 можно записать короче P_n = 10! = 3628800.

Размещением из n элементов по k называется упорядоченное подмножество из n элементов множества, имеющего k элементов. Обозначается A_k ⁿ

C очетанием из n элементов по k называется неупорядоченное подмножество из n элементов множества, имеющего k элементов. Обозначается C_kⁿ.

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

Задачи на раскраски, укладки, замощения.

Метод раскраски.

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

Диофантовы уравнения.

ДИОФАНТОВЫ УРАВНЕНИЯ - алгебраические уравнения или системы алгебраических уравнений, решения которых отыскиваются в целых или рациональных числах. Обычно предполагается, что Д. у. имеют число неизвестных, превосходящее число уравнений, в связи с чем они называются также неопределенными уравнениями.

Диофантовыми уравнениями называются уравнения вида , где  - многочлен с целыми коэффициентами.

При исследовании диофантовых уравнений обычно ставятся следующие вопросы:

1. имеет ли уравнение целочисленные решения;

2. конечно или бесконечно множество его целочисленных решений;

3. решить уравнение на мн-ве целых чисел, т. е. найти все его целочисленные решения;

4. решить уравнение на множестве целых положительных чисел;

5. решить уравнение на множестве рациональных чисел.

Решить уравнение в целых числах (уравнение с одним неизвестным).

Решение: свободный член уравнения 1. Делители свободного члена уравнения: ±1. Старший коэффициент уравнения 1. Положительные делители старшего коэффициента: 1. Следовательно, все целые корни уравнения находятся среди чисел {-1,1}. Подставляя  в уравнение заключаем, что только  является корнем этого уравнения.не пральна

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

Д. у. первой степени или так называемые линейные уравнения имеют вид  , где .

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

⇐ Предыдущая1234567Следующая ⇒

Поделиться: