Составители:
Рубрика:
90
Оглавление
Введение ...............................................................................................................................................3
Комбинаторика.....................................................................................................................................3
Предмет комбинаторики. ................................................................................................................3
Правила суммы и произведения. ....................................................................................................5
Формула включения и исключения................................................................................................7
Размещения с повторениями...........................................................................................................9
Размещения без повторений .........................................................................................................11
Перестановки..................................................................................................................................12
Перестановки с повторениями......................................................................................................13
Сочетания........................................................................................................................................15
Свойства чисел
k
n
C .........................................................................................................................17
Сочетания с повторениями. ..........................................................................................................19
Комбинаторика разбиений ............................................................................................................21
Вероятность ....................................................................................................................................26
Бином Ньютона ..............................................................................................................................28
Треугольник Паскаля.....................................................................................................................31
Полиномиальная формула.............................................................................................................32
Рекуррентные соотношения..........................................................................................................34
Асимптотики ..................................................................................................................................42
Задачи по комбинаторике..................................................................................................................44
Общие правила комбинаторики ...............................................................................................44
Формула включения и исключения..........................................................................................46
Размещения с повторениями.....................................................................................................46
Размещения без повторений .....................................................................................................48
Перестановки..............................................................................................................................49
Сочетания....................................................................................................................................50
Сочетания с повторениями .......................................................................................................51
Разные задачи .............................................................................................................................51
Комбинаторика разбиений ........................................................................................................55
Вероятность ................................................................................................................................58
Бином Ньютона. Полиномиальная формула. ..........................................................................60
Рекуррентные
соотношения......................................................................................................60
Задачи по теории графов ...................................................................................................................63
Основные определения и примеры графов. ............................................................................63
Матрицы, ассоциированные с графом .....................................................................................65
Изоморфизм графов...................................................................................................................67
Достижимость и связность........................................................................................................67
Циклы ..........................................................................................................................................70
Алгоритмы обхода связного графа. .........................................................................................71
Деревья........................................................................................................................................73
Двудольные графы.....................................................................................................................76
Ориентированные графы и мультиграфы................................................................................78
Игры и головоломки ..................................................................................................................81
Плоские графы ...........................................................................................................................82
Стереографическая проекция ...................................................................................................83
Двойственные графы .................................................................................................................83
Раскраски графа .........................................................................................................................84
Список рекомендуемой литературы по теории графов..................................................................87
Список литературы
............................................................................................................................89
