• Название:

    Дискретная математика (продолж.)


  • Размер: 2.14 Мб
  • Формат: PDF
  • или
  • Сообщить о нарушении / Abuse

Установите безопасный браузер



  • Название: 1 Начальные понятия теории множеств и математической логики
  • Автор: Владимир

Предпросмотр документа

ФИНАНСОВАЯ АКАДЕМИЯ
ПРИ ПРАВИТЕЛЬСТВЕ РОССИЙСКОЙ ФЕДЕРАЦИИ
Кафедра «Математика и финансовые приложения»

В.Б. Гисин

Лекции по дискретной математике

(часть 2)

МОСКВА 2002 ГОД

2

Аннотация
Пособие предназначено студентам, изучающим дискретную
математику,

и

преподавателям,

проводящим

занятия

по

указанной дисциплине. Дисциплина «Дискретная математика»
является обязательной для студентов дневного отделения
института «Антикризисное управление и математические
методы в экономике». Настоящее пособие содержит вторую
часть курса лекций по дискретной математике. В этой части
излагаются комбинаторика (включая производящие функции,
рекуррентные последовательности и числа Фибоначчи) и
теория графов. Значительное место уделено финансовым
приложениям изучаемого материала.

3

Оглавление
8. Элементы комбинаторики .

.

.

6

8.1. Предварительные сведения

.

.

6

8.2. Размещения и перестановки

.

.

10

8.3. Сочетания .

.

.

15

.

.

20

.

24

.

.

.

.

8.4. Некоторые свойства чисел Cnk

8.5. Принцип включения и исключения
9. Биномиальная модель
ценообразования активов .

.

.

.

28

9.1. Биномиальная решетка

.

.

.

28

9.2. Опционы. Основные понятия

.

.

29

9.3. Однопериодная модель

.

.

31

9.4. Двух- и трехпериодные модели .

.

36

9.5. Многопериодная модель

.

41

.
.

.

4
10. Биномиальный ряд. Производящие
функции .

.

.

.

.

.

.

47

10.1. Степенные ряды

.

.

.

.

47

10.2. Биномиальный ряд .

.

.

.

50

10.3. Производящие функции и примеры их
применения при решении комбинаторных
задач

.

.

.

.

.

54

11. Рекуррентные последовательности .

.

61

11.1. Рекуррентные соотношения

.

.

61

.

.

63

рекуррентных последовательностей .

67

11.2. Линейные рекуррентные
соотношения

.

.

.

11.3. Производящие функции линейных
11.4. Числа Каталана. Случайное
блуждание

.

.

.

.

.

74

.

.

.

.

.

82

12.1. Простейшие свойства

.

.

.

82

.

.

84

.

.

88

12. Числа Фибоначчи

12.2. Формула Бине и некоторые
ее применения
12.3. Золотое сечение

.
.

.

12.4. Числа Фибоначчи и поиск экстремума

92

5
13. Графы. Основные понятия

.

.

104

.

.

104

13.2. Маршруты, цепи и циклы .

.

.

108

13.3. Эйлеровы цепи и циклы .

.

.

111

.

.

113

13.1. Понятие графа .

.

.

13.4. Матрицы смежности
и инцидентности

.

.

13.5. Булевы матрицы и операции над ними

119

13.6. Бинарные отношения и графы .

.

120

14. Деревья

.

.

.

.

.

.

.

126

.

.

.

126

14.2. Остовное дерево связного графа

.

129

14.1. Общее понятие дерева

14.3. Ориентированные и упорядоченные
деревья

.

.

.

.

.

.

133

.

.

.

.

137

внешняя устойчивость в графах

.

.

142

15.1. Порядковая функция графа

.

.

142

15.2. Внешняя устойчивость

.

.

.

145

15.3. Внутренняя устойчивость .

.

.

149

15.4. Ядро графа

.

.

152

14.4. Бинарные деревья

15. Доминирование. Внутренняя и

.

.

.

6

8. Элементы комбинаторики
8. 1. Предварительные сведения
Целью комбинаторики является изучение комбинаторных
конфигураций – конструкций, построенных из элементов
некоторого (как правило, конечного) множества в соответствии
с заданными правилами. Важный класс комбинаторных задач
составляют задачи перечисления и, в частности, определения
числа конфигураций данного типа. Простейшими примерами
комбинаторных

конфигураций

являются

перестановки,

размещения и сочетания, представляющие собой различного
рода выборки.
Конечное

множество,

содержащее

n

элементов,

в

комбинаторике принято называть n-множеством. Различают
упорядоченные и неупорядоченные выборки из n-множества,
выборки с возвращением и выборки без возвращения. К числу
основных задач комбинаторики относятся задачи подсчета
числа выборок заданного типа и заданного объема из
произвольного n-множества.
Решение многих комбинаторных задач основывается на двух
фундаментальных

правилах,

называемых

соответственно

правилами суммы и произведения.
Правило суммы. Если X1 и X2 – непересекающиеся конечные
множества, содержащие соответственно n1 и n2 элементов, то

7
объединение X1∪X2 содержит n1 + n2 элементов.
Сформулированное правило можно распространить на
случай произвольного числа слагаемых:
если

множества

множества X,
элементов

то

X1, X2, …,Xk

n = n1 + n2 +…+ nk,

множества

X,

а

образуют
где

ni = |Xi| –

разбиение

n = |X| –
число

число

элементов

множества Xi, i = 1, 2,…, k.
Правило суммы можно приспособить и для подсчета числа
элементов

объединения

двух

множеств

с

непустым

пересечением:
|X1∪X2| = |X1| + |X2| – |X1∩X2|.

(1)

В самом деле, множества X1\X2 и X1∩X2 образуют разбиение
множества X1, поэтому
|X1| = |X1\X2| + |X1∩X2|.
Аналогично
|X2| = |X2\X1| + |X1∩X2|.
Кроме того, множества X1\X2, X2\X1 и X1∩X2 образуют разбиение
множества X1∪X2, так что
|X1∪X2| = |X1\X2| + |X2\X1| + |X1∩X2|.
Соотношение (1) является следствием трех последних формул.
Формула (1) обобщается на произвольное число слагаемых с
помощью так называемого принципа включения и исключения
(см. п. 8.4).
Пример. Найдем число правильных несократимых дробей
со знаменателем 100. Числителем правильной несократимой

8
дроби со знаменателем 100 должно быть целое число в
промежутке от 1 до 100, не имеющее среди своих делителей
чисел 2 и 5. Обозначим через X2, X5 и X10 множества чисел из
промежутка от 1 до 100, делящихся соответственно на 2, на 5 и
на 10. Легко видеть, что |X2| = 100/2 = 50 и |X5| = 100/5 = 20 и
|X10| = 100/10 = 10. Так как X2 ∩X5 = X10, то по формуле (1)
получаем |X2 ∪ X5| = 50 + 20 – 10 = 60. Таким образом, среди
чисел от 1 до 100 имеется 60 чисел, делящихся на 2 или 5, и
100 – 60 = 40

чисел,

взаимно

простых

с

числом

100.

Следовательно, среди правильных дробей со знаменателем 100
ровно 40 являются несократимыми.
Правило

произведения.

Будем

рассматривать

упорядоченные наборы (кортежи) вида (a1, a2,…, ak) заданной
длины k. Предположим, что элемент a1 может быть выбран n1
способами; при фиксированном a1 элемент a2 может быть
выбран n2 способами; при фиксированных a1 и a2 элемент a3
может быть выбран n3 способами и т. д. (при фиксированных
a1, a2,…, ak–1 элемент ak может быть выбран nk способами).
Тогда

число

различных

кортежей

равно

произведению

n1n2⋅…⋅nk. В частности, по правилу произведения для конечных
множеств X1, X2, …, Xk имеем:
|X1×X2×…×Xk| = |X1|×|X2|×…×|Xk|.
Пример. Используя правило произведения и правило
суммы, найдем число различных трехзначных чисел, не

9
содержащих одинаковых цифр, и число различных трехзначных
чисел, содержащих хотя бы две одинаковые цифры.
Пусть a1, a2, a3 – цифры трехзначного числа. Первую цифру
a1 можно выбрать девятью способами (в качестве нее можно
взять любую цифру, кроме нуля); при фиксированной первой
цифре вторую цифру a2 можно выбрать также девятью
способами (в качестве нее можно взять любую цифру, кроме
a1); наконец, при фиксированных первой и второй цифрах
третью цифру можно выбрать восемью способами. По правилу
произведения число трехзначных чисел, не содержащих
одинаковых цифр, равно 9⋅9⋅8 = 648. Всего имеется 900
различных трехзначных чисел. Каждое из них либо содержит
две одинаковых цифры, либо нет. Следовательно, имеется 900 –
648 = 252 различных трехзначных числа, содержащих хотя бы
две одинаковые цифры.
Факториалы.
положительного

Напомним,
числа

n

что

факториалом

(обозначение

n!)

целого

называется

произведение 1⋅2⋅...⋅n. По определению считается, что 0! = 1.
Факториал как функция натурального аргумента может быть
однозначно определен рекурсивно:
0! = 1; (n + 1)! = n!⋅(n + 1).
Приближенное значение n! при больших n дает следующая
формула Стирлинга:

10
n! ∼

n

n
2 рn   .
e

(2)

Символ ∼ означает здесь, что отношение
n

n
2 рn   /n!
e
стремится к единице при n, стремящемся к бесконечности. Хотя
разность правой и левой частей в формуле Стирлинга
неограниченно возрастает, относительная ошибка быстро
убывает. Например, уже при n = 10 относительная ошибка
составляет менее одного процента:
10

10! = 3628800;

 10 
2 р ⋅ 10 ⋅  
e

≈ 3598696.

8. 2. Размещения и перестановки

Размещения с повторениями объема k из n-множества X, или
размещения с повторениями из n элементов по k, – это
упорядоченные выборки вида (a1, a2,…, ak), где ai, i = 1, 2,…, k,
– произвольные элементы множества X.
Каждый элемент ai может быть выбран n способами. По
правилу

произведения

общее

число

размещений

с

повторениями из n элементов по k равно nk.
Размещения (без повторений) объема k из n-множества X,
или размещения из n элементов по k, – это упорядоченные
выборки вида (a1, a2,…, ak), где ai, i = 1, 2,…, k, – различные
элементы множества X.

11
Элемент a1 может быть выбран n способами. При n ≥ 2
элемент a2 может быть выбран n – 1 способами: в качестве a2
можно взять любой элемент из (n – 1)-множества X\{a1}. По
правилу произведения число упорядоченных пар различных
элементов вида (a1, a2) равно n(n – 1). Аналогично (при n ≥ 3)
элемент a3 может быть произвольно выбран из (n – 2)множества X\{a1, a2}, так что число упорядоченных троек
(a1, a2, a3) равно n(n – 1)(n – 2).
Число размещений из n по k, n ≥ k, обозначается через Ank .
Как мы видели, An1 = n . Естественно считать, что
An0 = 1

(3)

(имеется ровно одна, не содержащая ни одного элемента, т. е.
пустая выборка).
Несложно показать, что при k < n имеет место соотношение
Ank +1 = (n − k ) Ank .

В

самом

деле,

упорядоченную

(4)
выборку

вида

(a1, a2,…, ak, ak+1) можно рассматривать как упорядоченную
пару, в которой первым элементом служит размещение
(a1, a2,…, ak), а вторым – ak+1. Размещение из n элементов по k
может быть составлено Ank способами, элемент ak+1 может быть
произвольно выбран из (n – k)-множества X\{ a1, a2,…, ak}.
Формула (3) получается теперь по правилу произведения.

12
Используя формулы (3) и (4), получаем:
An1 = n , An2 = n(n − 1) , An3 = n(n − 1)(n − 2) , … ,

и, в общем случае:
Ank = n(n − 1) ⋅ K ⋅ (n − k + 1) .

(5)

Предыдущую формулу можно записать следующим образом:
Ank =
Пример.

Найдем

число

n!
.
(n − k )!

всех

(6)

отображений

и

число

инъективных отображений из k-множества X в n-множество Y.
Перенумеруем элементы множества X, X = {a1, a2,…, ak}.
Всякое отображение f из X в Y однозначно определяется
упорядоченным
(b1, b2, …, bk),

набором
в

элементов

котором

bi = f(ai).

множества
Значит,

Y

вида

число

всех

отображений из X в Y равно числу размещений с повторениями
из n элементов по k, то есть числу nk. Таким образом, получаем
формулу:
|YX|= nk,
где через YX обозначено множество всех отображений из X в Y.
Если k > n, инъективных отображений из X в Y нет. При k ≤ n
отображение f из X в Y инъективно, если в наборе (b1, b2, …, bk)
все элементы различны, т. е. набор (b1, b2, …, bk) является
размещением
инъективных

без

повторений.

отображений

размещений Ank .

из

Следовательно,
X

в

Y

равно

число
числу

13
Размещения
n-множества

объема
X

n,

составленные

называются

из

элементов

перестановками

элементов

множества X.
Задать перестановку элементов множества X – это значит
линейно упорядочить элементы этого множества. Число всех
перестановок из n элементов обозначается через Pn. Используя
формулу (5) при k = n, получаем:
Pn = n!.
Пример.

Перечислим

(7)
перестановки

элементов

множества X = {1, 2, 3}:
123;

132; 213; 231; 312; 321.

В заключение рассмотрим перестановки с повторениями.
Пусть X = {a1, a2,…, ak} – некоторое k-множество. Перестановкой с повторениями типа (n1, n2,…, nk) называется упорядоченный набор элементов множества X вида (x1, x2,…, xn), в котором
элемент a1 встречается n1 раз, элемент a2 встречается n2 раз, …,
элемент ak встречается nk раз. Естественно, n1 + n2 +…+ nk = n.
Число

перестановок

типа

(n1, n2,…, nk)

обозначается

через P(n1, n2,…, nk).
Пример. Перечислим все перестановки типа (2, 2) из

элементов множества X = {a, b}:
aabb;

abab;

abba;

baab;

baba;

bbaa.

14
Чтобы получить формулу для вычисления P(n1, n2,…, nk),
воспользуемся следующей метафорой. Элементы множества X
будем считать буквами, а перестановки с повторениями –
словами. Для определенности будем считать, что X содержит
три буквы a, b, c. Рассмотрим произвольное слово w длины n,
содержащее n1 букв a, n2 букв b и n3 букв c. Подсчитаем число
перестановок букв, при которых слово w не меняется. Буквы a
можно произвольно переставлять на n1 местах, на которых они
расположены. Это можно сделать n1! числом способов. Точно
так же буквы b можно переставить n2! способами, буквы c –
n3! способами. По правилу произведения число перестановок
букв, при которых слово w не меняется, равно n1!n2!n3!. Таким
образом, для каждого слова имеется n1!n2!n3! перестановок
букв, которые его не меняют. Общее число перестановок букв
равно n!. Следовательно, число слов, т. е. перестановок типа
(n1, n2, n3), равно

n!
.
n1!n2!n3!
Предыдущее рассуждение легко переносится на общий
случай и приводит к следующей формуле:
P(n1, n2 ,K , nk ) =

n!
.
n1!n2!K nk !

(8)

Пример. Пакет акций состоит из акций четырех типов: 5

акций типа A, 3 акции типа B и по одной акции типов C и D.

15
Сколькими способами можно распродать этот пакет, продавая
по одной акции ежедневно?
Каждая

распродажа

однозначно

определяется

словом

длины 10, составленном из пяти букв A, трех букв B, одной
буквы C и одной буквы D (буква, стоящая на месте i, означает,
что в день i была продана акция соответствующего типа).
Значит, число всевозможных распродаж составляет
P(5,3,1,1) =

10!
= 5040 .
5