Четыре лекции по комбинаторике. Семенов А.С. - 4 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

6
=
4
)2()1(
)44()1(
4
1
22
22
++
=+++
kk
kkk
, т.е. формула (1) верна и при значении
1+=
k
n . Следовательно, согласно принципу математической индукции, формула
(1) верна для любого натурального n .
Пример 2. Доказать, что для всякого натурального числа, не меньшего десяти, т.е.
)10:( ≥∈∀ m
N
m , имеет место неравенство
3
2 m
m
> .
Решение. Пусть −n любое натуральное число. Тогда доказательство данного нера-
венства сводится к доказательству неравенства
39
)9(2 n
n
+>
+
. (2)
Докажем его методом математической индукции.
1) При 1=n имеем
10001010242
310
=
>=
, т.е. неравенство (2) верно.
2) Предположим, что неравенство (2) верно для всех
k
n
≤
. Тогда последовательно
получаем
39
)9(2 k
k
+>
+
,
39
)9(222 k
k
+⋅>⋅
+
,
>+++>
+
14584865422
2310
k
k
k
k 323
)10(100030030 +=++ kkkk , т.е. нера-
венство (2) верно и при 1+=
k
n . Следовательно, на основании принципа матема-
тической индукции, неравенство (2) верно для любого натурального n .
§ 2. Основные принципы комбинаторики
Теорема 2 (принцип умножения)
Если некоторое действие может быть выполнено за
k
этапов, причем число
возможных способов осуществления
−
i го этапа равно
),,...,2,1( kin
i
=
то общее
число
k
N способов осуществления указанного действия вычисляется по формуле
∏
=
=⋅⋅⋅=
k
i
ikk
nnnnN
1
21
.... (3)
Доказательство.
Используем индукцию по числу этапов. Если ,1=
k
то, очевидно,
что
11
nN = и, следовательно, формула (3) верна для .1
=
k
Пусть далее .2
=
k
То-
гда, так как каждый из
1
n способов осуществления первого этапа может иметь место
с каждым из
2
n способов осуществления второго этапа, то ,
212
nnN ⋅= т.е. фор-
мула (3) верна и для .2=
k
Предположим теперь, что формула (3) верна при
,1−
=
m
k
т.е. имеет место
формула
∑
−
=
−
=
1
1
1
.
m
i
im
nN (4)
Тогда, если ,m
k
= то, рассматривая первые 1
−
m этапов в качестве первого этапа
с общим числом способов осуществления, определяемым формулой (4), и применяя
результат, доказанный вторым шагом индукции, получаем
,
1
1
∑
=
−
=⋅=
m
i
immm
nnNN
т.е. формула (3) верна и для .m
k
= Следовательно, согласно принципу математи-
ческой индукции, теорема 2 доказана.
Рассмотрим некоторые примеры применения принципа умножения.

Страницы