lekcii_dm
.pdf
Пример 4
2n n для любого n N .
Доказательство |
|
|
|
При n=1 |
неравенство очевидно: 2>1. Допустим, 2k k . Докажем, |
что |
|
2k 1 k 1. В |
самом деле, 2k 1 2 2k 2k 2k k 1, так как |
2k k |
по |
индуктивному предположению и 2k 1 – очевидное неравенство.
Пример 5
2n n2 для любого натурального n 5.
Доказательство
При n=5 получаем верное неравенство 32>25. Допустим, неравенство
верно при |
n k 5, то |
есть |
2k |
k 2 . |
Докажем, что |
2k 1 k 1 2. |
Это |
неравенство |
равносильно |
2k |
2k |
k 2 |
2k 1. Если |
мы докажем, |
что |
2k 2k 1 |
k 5 , то будет доказано и исходное неравенство. Неравенство |
2k 2k 1 |
k 5 доказываем индукцией (индукция в индукции). При |
k 5 имеем верное неравенство |
32 11. Допустим, неравенство верно при |
||
k m , то есть 2m 2m 1. Докажем при k m 1, |
то есть докажем, |
что |
|
2m 1 2 m 1 1 2m 3 или |
2m 2m 2m 1 2. |
Очевидно, что |
это |
неравенство верно в силу индуктивного предположения. |
|
||
6.05. Задачи для самостоятельного решения.
6.1 Доказать методом математической индукции, что для любого
.
6.2Доказать методом математической индукции, что для любого
; 201
6.3Доказать методом математической |
индукции, что для |
|||
6.4 |
любого |
|
|
. |
|
||||
Доказать методом математической индукции, что для любого |
||||
|
. |
|
|
|
6.5 |
Доказать методом математической индукции, что для любого |
|||
|
; |
|
|
|
6.6 |
Доказать методом математической индукции, что для любого |
|||
|
. |
|
|
|
6.7 |
Доказать методом математической индукции, что для любого |
|||
|
|
; |
||
6.8 |
Доказать методом математической индукции, что для любого |
|||
|
. |
|
|
|
6.9 |
Доказать методом математической индукции, что для любого |
|||
|
справедливо равенство |
|
|
|
6.10Доказать методом математической индукции, что для
любого
6.11Доказать методом математической индукции, что для
любого
.
6.12Доказать методом математической индукции, что для
любого
.
6.13 Доказать методом математической индукции, что для любого
.
202
6.14Доказать методом математической индукции, что для
любого
.
6.15Доказать методом математической индукции, что для
любого
.
6.16Доказать методом математической индукции, что для
любого
.
6.17Доказать методом математической индукции, что для
любого
.
6.18Доказать методом математической индукции, что для
любого
.
6.19Доказать методом математической индукции, что для
любого
; 6.20 Доказать методом математической индукции, что для
любого
.
Глава 7. Элементы комбинаторики.
7.01. Основные понятия комбинаторики.
Определение.
Комбинаторика – это раздел математики, посвященный задаче выбора и расположения элементов некоторого конечного множества в соответствии с заданными правилами.
203
Каждое такое правило определяет способ построения некоторой конструкции из элементов исходного множества, называемой комбинаторной конфигурацией. Можно сказать, что целью комбинаторики является изучение комбинаторных конфигураций. Это вопросы существования этих конфигураций, алгоритмы их построения, оптимизация этих алгоритмов, а так же задачи перечисления то есть определение числа элементов данного класса.
Простейшим примером комбинаторных конфигураций являются
размещения, сочетания и перестановки.
Возникновение и развитие комбинаторики тесно связано с развитием других разделов математики: теории чисел, алгебры. Еще математикам Древнего Востока была известна формула, выражающая число сочетаний через биноминальные коэффициенты и Бином Ньютона для натуральных n . С мистическими целями изучались свойства магических квадратов 3-его порядка.
Комбинаторика как раздел математики появилась в трудах Блеза Паскаля и Ферма по теории азартных игр. Эти труды, составив основу теории вероятностей, одновременно содержали принципы нахождения числа комбинаций элементов данного конечного множества.
С появлением работы Лейбница и Бернулли «Искусство предположений» посвященной теории вероятностей комбинаторные схемы выделились в отдельную часть математики.
Возрождение интересов к комбинаторике относится к 50 годам ХХ века. Этот интерес связан с развитием кибернетики. Большой развивающийся раздел комбинаторики это теория блок-схем. Основные проблемы этого раздела связаны с вопросами классификации, условиями существования и методами построения некоторых классов блок-схем.
204
Рассмотрим k множеств M1,M2,...,Mk , содержащий по m1,m2,...,mk элементов соответственно. Будем выбирать по одному элементу из каждого множества и составлять новое множество. Число способов, которыми это можно сделать равно m1 m2 ... mk . Будем рассматривать такие множества, в которых каждый элемент входит не более одного раза. Такие соединения называются без повторений.
Будем считать, что рассматриваем множество A , состоящее из n различных элементов.
Определение:
Размещением без повторений из n элементов по k элементов k n
называются k -элементные подмножества множества A , отличающиеся один от другого или самими элементами или их порядком. Обозначаем Ank .
Теорема.
Число размещений без повторений равно
Ank n(n 1)(n 2)...(n (k 1))
Доказательство.
Для того чтобы расположить k элементов в определенном порядке выберем один и будем считать его «первым». Это можно сделать n способами. Оставшееся множество содержит n 1 элемент. Из него выберем ещё один и будем считать его «вторым». Для выбора второго элемента существует n 1 способ. Осталось n 2 элемента. Продолжая рассуждать подобным образом понятно, что k -ый элемент можно n (k 1) способами. Пользуясь утверждением, приведенном в начале параграфа получим
Ank n(n 1)(n 2)...(n (k 1))
205
Определение.
Перестановками из n элементов называются множества из n элементов, отличающиеся один от другого порядком элементов. Обозначаем
Pn .
Теорема.
Число Перестановок без повторений равно Pn n!
Доказательство.
Повторяет доказательство предыдущей теоремы, полагая k n .
Определение.
Сочетаниями без повторений, содержащими k элементов,
выбранных из n элементов заданного множества, называются всевозможные множества из k элементов, отличающиеся хоть одним элементов (порядок не учитывается), при этом все элементы различны. Обозначаем Сnk
Теорема |
|
|
Число Сnk |
n! |
|
k!(n k)! |
||
|
Доказательство
Рассмотрим перестановку из n элементов по k . Если не считаться с порядком элементов, то существует k ! Перестановок, которые не различимы.
Следовательно Ank k!. Упрощая эту формулу, получим искомую.
206
Определение
Размещением с повторением из n элементов по k элементов k n
называются k -элементные подмножества множества A , отличающиеся один от другого или самими элементами или их порядком . При этом допускается кратное вхождение элементов множества A .
Теорема
Число размещений с повторениями из n элементов по k равно Rnk nk
Доказательство
Рассуждения очень похожи на доказательство числа размещения без повторений. Значение, которое стоит на «первом» месте можно выбрать n способами. Значение, стоящее на «втором» месте также можно выбрать n способами (т.к. они могут повторяться, элементы после выбора не удаляются из множества, из которого выбирают). И т.д. процедура повторяется k раз.
Определение.
Сочетаниями с повторениями, содержащими k элементов,
выбранных из n элементов заданного множества, называются всевозможные множества из k элементов, отличающиеся хоть одним элементов (порядок не учитывается), при этом допускается неединичное вхождение элементов. Обозначаем Snk
Теорема |
|
|
Число Snk Cnk k 1 |
|
(n k 1)! |
|
|
k!(n 1)! |
207
7.02. Декартово произведение множеств.
Определение. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
Декартовым произведением множества X и Y |
называется множество, |
|||||||||||||||||||||||||
обозначенное X Y , элементами которого являются упорядоченные пары |
|||||||||||||||||||||||||||
x;y , где |
|
|
x X , |
|
|
y Y . Равенство |
упорядоченных |
пар |
|
понимается |
в |
||||||||||||||||
следующем смысле: |
|
|
|
|
|
|
|||||||||||||||||||||
|
пусть |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
z1 x1;y1 è z2 x2;y2 z1 ,z2 X Y |
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
def |
x2 & y1 y2 . |
|
|
|
|
|
|
||||||||
|
|
|
z1 z2 x1 |
|
|
|
|
|
|
||||||||||||||||||
Теорема. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
Если |
X и Y – конечные множества, то X Y – конечное множество и |
|||||||||||||||||||||||||
|
X Y |
|
|
|
X |
|
|
|
Y |
|
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
Доказательство. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
Ясно, что в случае, когда одно |
из множеств |
X , |
Y |
пусто, то |
и |
|||||||||||||||||||||
|
X Y пусто и тривиально выполнено. |
Рассмотрим случай, |
когда X и Y – |
||||||||||||||||||||||||
непустые множества. Зафиксируем в X нумерацию |
|
|
|
|
|
||||||||||||||||||||||
|
|
|
X x1,x2, ,x |
|
x |
|
. |
|
X |
|
xi Y и |
|
xi Y |
|
|
||||||||||||
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
Ясно, |
|
|
что |
X Y |
|
|
множества |
попарно |
не |
|||||||||||||||||
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
||||||||||||||||||||||
i 1
пересекаются, тогда по правилу суммы имеем:
X
EMBED Equation.3 X Y xi Y (*).
i 1
Рассмотрим отображение fi : xi Y Y , действующее по правилу fi xi ,y y .
208
Ясно, что fi – биективное отображение, тогда по основному принципу комбинаторики получаем
xi Y Y (**).
Подставляя (**) в (*), получим:
X
X Y Y X Y .
i1
7.03.Примеры задач и упражнений.
Пример 1.
Определить, сколько трехзначных чисел можно составить из множества цифр 1,2,3,4,5 без повторений.
Решение.
n 5; |
k 3; |
A3 |
60 |
|
|
5 |
|
Пример 2.
К кассе за получением денег одновременно подошли 4 человека. Сколькими способами они могут выстроиться в очередь.
Решение.
Очередь состоит из 4 различных человек, поэтому эти очереди отличаются только порядком элементов. Это перестановки без повторений.
P4 4! 24
Пример 3
Имеется 6 штаммов бактерий. Для определения скорости их роста необходимо выбрать 3 штамма. Сколькими способами можно это сделать?
Решение
209
Способы отбора различаются, если каждая группа штаммов различаются хотя бы одним элементом. Это число
С63 3!(66! 3)! 20
Пример 4
Выбрать из 20 человек в группе 8 человек для сдачи зачета досрочно.
Решение |
|
|
|
|
С208 |
20! |
|
125970 |
|
8!(20 8)! |
||||
|
|
|||
Пример 5
В ящике 20 шаров, среди них 12 белых, остальные зелёные. Отбирается наугад 2. Сколькими способами можно отобрать а) два белых шара, б) два зелёных, в) один белый и один зелёный.
Решение
а) С122 212!10!! 66 б) С82 28!6!! 28 в) 12 8 96
Пример 6
n (n 2) человек садятся за круглый стол. Два размещения по местам будем считать совпадающими, если каждый человек имеет одних и тех же соседей в обоих случаях. Сколько существует способов сесть за стол.
Решение
Общее число перестановок равно n!. Но отношение соседства сохраняется при циклических перестановках (повороте) их n для каждого
210