Раздел 3. Основные теоремы комбинаторики

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

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

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

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

Тема 3.1. Метод математической индукции

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

Теорема (принцип математической индукции)

Пусть имеется некоторое утверждение которое формулируется для каждого натурального числа и пусть известно, что:

утверждение верно;

из того, что верно при следует, что верно.

Тогда утверждение верно для любого значения.

Доказательство:

Применим метод доказательства «от противного». Предположим, что, несмотря на истинность условий теоремы, утверждение верно не для всех натуральных . Тогда среди тех , для которых неверно, найдётся наименьшее число . Ясно, что так как в противном случае получаем противоречие с первым условием теоремы, то есть тоже натуральное число, для которого верно. Но тогда должно быть верным в силу второго условия теоремы. Мы пришли к противоречию, доказав тем самым утверждение теоремы.

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

Решение:

Проверяем выполнение условий принципа математической индукции. При левая и правая части равны 1 т.е. формула верна. Пусть формула верна для всех тогда