ФИНАНСОВАЯ АКАДЕМИЯ ПРИ ПРАВИТЕЛЬСТВЕ РОССИЙСКОЙ ФЕДЕРАЦИИ

Кафедра «Математика и финансовые приложения»

В.Б. Гисин

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

(часть 2)

МОСКВА 2002 ГОД

2

Аннотация

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

3

Оглавление

8. Элементы комбинаторики .			.	.	.	6
8.1. Предварительные сведения				.	.	6
8.2. Размещения и перестановки				.	.	10
8.3. Сочетания .	.	.	.	.	.	15
8.4. Некоторые свойства чисел Cnk .					.	20
8.5. Принцип включения и исключения .						24
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
11.2. Линейные рекуррентные
соотношения .			.	.	.	.	63
11.3. Производящие функции линейных
рекуррентных последовательностей .							67
11.4. Числа Каталана. Случайное
блуждание		.	.	.	.	.	74
12. Числа Фибоначчи .			.	.	.	.	82
12.1. Простейшие свойства				.	.	.	82
12.2. Формула Бине и некоторые
ее применения			.		.	.	84
12.3. Золотое сечение			.	.	.	.	88
12.4. Числа Фибоначчи и поиск экстремума							92

			5
13. Графы. Основные понятия				.	.	.	104
13.1. Понятие графа .			.		.	.	104
13.2. Маршруты, цепи и циклы .					.	.	108
13.3. Эйлеровы цепи и циклы .					.	.	111
13.4. Матрицы смежности
и инцидентности			.	.	.	.	113
13.5. Булевы матрицы и операции над ними							119
13.6. Бинарные отношения и графы .						.	120
14. Деревья .	.	.	.	.	.	.	126
14.1. Общее понятие дерева .					.	.	126
14.2. Остовное дерево связного графа						.	129
14.3. Ориентированные и упорядоченные
деревья .		.	.	.	.	.	133
14.4. Бинарные деревья .				.	.	.	137
15. Доминирование. Внутренняя и
внешняя устойчивость в графах .						.	142
15.1. Порядковая функция графа					.	.	142
15.2. Внешняя устойчивость .					.	.	145
15.3. Внутренняя устойчивость.					.	.	149
15.4. Ядро графа		.	.	.	.	.	152