ВУЗ:
Составители:
Рубрика:
5
ЛЕКЦИЯ 1
Введение
Комбинаторика или теория конечных множеств является одним из разделов
математики, имеющим большое значение в связи с применением его в теории веро-
ятностей, математической логике, вычислительной технике, кибернетике, целочис-
ленном программировании и т.п.
Цель лекций познакомить читателей с основными понятиями комбинаторики и
методами решения комбинаторных задач.
При составлении лекций использовалась следующая литература
1. Виленкин Н.Я. Комбинаторика - М.: Наука, 1979.
2. Ежов И.И., Скороход А.В., Ядренко М.М. Элементы комбинаторики - М.: Наука,
1977.
Лекции предназначены, прежде всего, для студентов, изучающих теорию ве-
роятностей. Они могут оказаться полезными и лицам, которые знакомы с определе-
ниями и свойствами основных операций
над множествами и занимаются комбина-
торными расчетами.
§ 1. Принцип математической индукции
Широко распространенный метод доказательства утверждений - это метод
математической индукции, основанный на принципе математической индукции. До-
кажем его.
Теорема 1
(принцип математической индукции)
Пусть имеется некоторое утверждение ),(n
P
которое формулируется для ка-
ждого натурального числа ,n и пусть известно, что:
1) утверждение )1(
P
верно;
2) из того, что )(n
P
верно при ,
k
n
=
следует, что )1(
+
k
P
верно.
Тогда утверждение )(n
P
верно для любого значения n ( .
N
n
∈
∀
).
Доказательство. Применим метод доказательства "от противного". Предположим,
что, несмотря на истинность условий 1 и 2 теоремы, утверждение
)(n
P
верно не для
всех натуральных .n Тогда среди тех ,n для которых )(n
P
неверно, найдется наи-
меньшее число m . Ясно, что ,1>m так как в противном случае получаем противо-
речие с условием 1 теоремы, то есть
1
−
m тоже натуральное число, для которого
)1( −m
P
верно. Но тогда )()11( m
P
m
P
=
+
− должно быть верным в силу второго
условия теоремы. Мы пришли к противоречию. Теорема 1 доказана.
Пример 1. Используя метод математической индукции, доказать формулу для
суммы кубов последовательных натуральных чисел
∑
=
+
==+++
n
m
nn
mn
1
22
3333
.
4
)1(
...21 (1)
Решение. Проверяем выполнение условий теоремы 1. 1) При 1=n левая часть в (1)
дает 11
3
= , правая -- 1
4
21
2
=
⋅
,т.е. формула (1) верна при 1
=
n . 2) Пусть формула
(1) верна для всех ,
k
n
≤
тогда =++
+
=++=
∑∑
=
+
=
3
22
3
1
3
1
1
3
)1(
4
)1(
)1( k
kk
kmm
k
m
k
m
