118. а) klCd +2(k-l)\QxC{ +(к -2)!C*-JC*-2; в) п + 1.

119. 4* t Ж + 120. ( ( + 1)/2). 121. 1) 7 + 3 ;

1-7*

2) 2л=[9 * 32 + (-1) ]/10,м2 +1 = [9 32 +1 + 3 (-1Л/10,л>0; 3) (Т9) ; 4) (+4) ; 5) (-1) (л - 1) + 2; 6) 2 . 122. 1) С„2+2-2С2+1 +2С%;2) -2(-4) + 3 2 + 5 ; 3) 2 4) 2 +2 -2С2; 5) 6) * -y-*>-,

Ш1\ /< Л DH-I- 1\ Л . D . 1 . 1\ л\ i rV- . nl 1 J

-- \ %-j -

125. =2 +](2r, + 7), =2н1(-2н ~ 3).

126. 4 : 128.

129. Использовать формулу включений и исключений.

130. а) Щх, Q = x(l +х)3 + (1 + Зх +х2)(1 + х).

133. а) 2 , с) 2 3я 1. Составить рекуррентное соотношение (см.п.3.3). 134. а) 2 +(з° 2, б) (3 1 -(-I) -1). Составить рекуррентное соотношение (см.п.3.3). 135. 4 .

136. CJ,£(C;> =(CJ,) . Воспользуйтесь производящей функ-

Г I Л2 Л ,.( \\Ч П** циеи л + - + ! + -..... --- > cv..! + у + всех ломаных

V * У) ~q ~ { xj \ у)

маршрутов длины 2л по рассматриваемой сетке. Свободный член в правой части является искомым числом для замкнутых маршрутов (см. п.3.4). 137. С% (см. указание к предыдущей задаче).

183.а) 14;б) 18;в)9. 184.а)43; 6)61. 185. а)37;б) 100;в) 158.

Литература

I АхоА.,ХопкрофтДж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979.

2. Берж К. Теория графов и ее применения. - М.: ИЛ, 1962.

3. Виленкин Н.Я. Комбинаторика. - М: Наука, 1969.

4. Виноградов И.М. Основы теории чисел. - М: Наука, 1981.

5. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. - М.: Наука, 1977.

6. Грин Д., Кнут Д. Математические методы анализа алгоритмов. - М.: Мир, 1987.

7. Гроссман И., Магнус В. Группы и их графы. - М.: Мир, 1971.

8. Гудман С, Хидетниеми С. Введение в разработку и анализ алгоритмов. -М.: Мир, 1981.

9. Иванов Б.Н. Подсчет и оценивание. Алгоритмы на графах: Метод, указания для студентов. - Владивосток, 1991.

10. Кнут Д. Искусство программирования для ЭВМ. Сортировка и поиск. Т.З. - М.: Мир, 1978.

11. Комбинаторный анализ. Задачи и упражнения. Учебное пособие / Под ред. Рыбникова КА- М.: Наука, 1980.

12. Кофман А. Введение в прикладную комбинаторику. - М.: Наука, 1975.

13. Кристофидес М. Теория графов. - М.: Мир, 1978.

14. Курош А.Г. Лекции по общей алгебре. - М.: Наука, 1973.

15. Нефедов В.Н., Осипова В.А. Курс дискретной математики. - М.: МАИ, 1992.

16. Оре О. Теория графов. - М.: Наука, 1980.

17. Препарата Ф., ШеймосМ. Вычислительная геометрия. - М.: Мир, 1989.

18. Райзер Дж. Комбинаторная математика. - М.: Мир, 1966.

19. РейнголцЭ., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. - М: Мир, 1980.

20. Риордан Дж. Введение в комбинаторный анализ. - М.: ИЛ, 1963.

21. Рыбников К.А. Введение в комбинаторный анализ. - М.: МГУ, 1972. 22.Уилсон Р.Дж. Введение в теорию графов. - М.: Мир, 1977.

23. Форд Л.Р., ФалкерсонД.Р. Потоки в сетях. - М.: Мир, 1966.

24. Харрари Ф. Теория графов. - М.: Мир, 1973.

25. Харрари Ф., Палмер Э. Перечисление графов. - М.; Мир, 1977.

26. Холл М. Комбинаторика. М.: Мир, 1970.

27. Холл П. Вычислительные структуры. Введение в нечисленное программирование. - М.: Мир, 1978.

Предметный *---

Алгоритмы

Евклида 227-228 поиска с возвращениями 66-68 порождения (=генерация) композиций 84 перестановок 68-75 случайных 89-90 подмножеств 76 разбиений 85-88 размещений с повторениями 79 сочетаний 80 Алгоритмы на графах

выделение компонент связности 126-129

кратчайшие пути на графе 151-155 максимальное паросочетание 186-188

поиск блоков в глубину 182-184

поиск в глубину (общий) 117-123

поиск клик 160-171

поиск эйлеровой цепи 131-136

потоки в сетях 156-159

остовное дерево 137-138

ближайшего соседа 145-149 жадный 139-144

фундаментальные циклы 172-176

чередующиеся цепи 185-188 Бернсанда лемма 216 Вильсона теорема 237 Включение и исключение

правило (принцип) 56 Выпуклая оболочка многоугольника

(задача) 81 Вычеты 233

полная система 233 приведенная система 234 Гамильтонов цикл 113 Граф НО

блоки 180-184 вершины

висячие 112

изолированные 112

смежные 112 двудольный 185 двусвязные 183 диаметр, радиус, центры 196 дополнение 112 изоморфный 111 клики 160

компоненты связности 125 листы 177-179 маршрут 113 матрица весов 114

инцидентности 115 смежности 114 мост (разделяющее ребро) 178 мультиграф 111 остовное дерево 137 паросочетания 186

чередующиеся цепи 186-187 пути на графе 151-155 плоский (=планарный) 112 помеченный 113

связный 125

список ребер 116 структура смежности 117 ориентированный 111 петля 110 подграф 111 полный 112 простой 112 псевдограф 111 связный 113 сильно 113 слабо 113 транспортная сеть 156-159 фундаментальные циклы 172-176

хроматический 194

цепь ИЗ

простая 113 замкнутая 113 гамильтонова 113 эйлерова 130 цикл 113

простой 113 замкнутый 113 гамильтонов 113

эйлеров 130 эйлеров 130

Группа 197 абелевы 203 вычетов 233-234

гомоморфизм 198

образ 199 ядро 199

изоморфизм 199

теорема Кэли 212

индекс 200

коммутативная 197

подстановок 208

примарная 204

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

циклические подгруппы 206

Силова 207

симметрическая 208

смежные классы 199-200

фактор 201-202

циклическая 200-201

цикловой индекс 217 Действие групп на множестве 212-216 Декремент подстановки 209-210 Дерево (граф) 114

бинарное (двоичное) 31

корневое 31

остовное 137-144

поддерево 32

представление 31

на связной памяти 32 на смежной памяти 32

бинарное (двоичное) 33

регулярное 34

сравнений 104

Доминирующее множество 160-161 минимальное 161 число доминирования 161

Доска запрещенных позиций 60

Задача о назначениях 190-193

Инверсии перестановки 20

Индекс подгруппы 200

Клики (в графе) 160

Коллизии 108

Компоненты связности графа 125-126

Корень дерева 32

Коэффициенты полиномиальные 14

Куб и-мерный (задача) 40

Кэли теорема 212

Лагранжа теорема 200

Лес (=множество деревьев) 31,114

Линейный порядок 91

Мёбиуса функция 238

Многочлен

ладейный 60-62

попаданий 63

Множество

весов элементов 53 дополнение 8 объединение 8 пересечение 8 представление 37

смежное связанное 37-38

характеристический вектор 38

прямое произведение 8 пустое 8 разность 8 универсальное 8

Мультимножество 14

Наибольший общий делитель 227 Наименьшее общее кратное 228

Независимое множество вершин, ребер 162

Независимые циклы подстановок 206 Нормальный делитель 201 Обобщенное правило произведения 53 Образующий элемент группы 200 Орграф ориентированный граф) 111 Отношение эквивалентности 124 Паросочетание максимальное 186-188 Петля (в графе) ПО Перестановки 11

инверсии 20

обратные 21

порождение 68-73

с повторениями 13

Подгруппа 198

индекс 200

нормальный делитель 201 циклическая 200

Подстановки 208

группа симметрическая 208 декремент 209 транспозиции 210-211 цикловая структура 223-226 четность 209-210

Поиск данных 91

закон Зипфа 103 логарифмический 104-106 последовательный 102-103 Поиск с возвращениями (алгоритм) 66 Пойа теория перечисления 218-223

Порядок

элемента (в группе) 200

линейньгй 91

Потоки в сетях (в графе) 156-160

Правило

суммы 8,9,53

прямого произведения 8,9,53

Представление последовательности 24

связанное 26 смежное 24

характеристический вектор 25

Принцип включения и исключения 56

Производящая функция 39 операции 39

дополнительные суммы 42 изменение масштаба 43 линейные 41

сдвиг влево, вправо 41-42 свертка 44 частичные суммы 42

Простые числа 228

решето Эратосфена 229 Прямая адресация 106-109 Разбиение множества

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

неупорядоченное 15 Разделяющая вершина 181-182

Размещение

с повторениями 9

без повторений 10 Расстановка 9-12 Ребро (в графе) НО Рекуррентные линейные соотношения

неоднородное 51 Система различных представителей 189

двудольные графы 189

теорема Холла 190 Смежные вершины 112

Смежные левые (правые) классы 199

связанные 26-27 циклически связанные 27

Сортировка 91 внешняя 91-92 внутренняя 91-92 всплытием Флойда 95-100 вставками 92

отрезков (задача) 100-101 перечислением 94 прямой адресации 106-109 пузырьковая 93

полная 94 сложность

Сочетания 11

с повторениями 12

Стабилизатор (группа) 214 Сумма (задачи)

квадратов 47 счастливая 77 Теорема

Вильсона 237

включения и исключения 56

Кэли 212

Лагранжа 200

о двудольных графах 185

о максимальном

о максимальном потоке и минимальном разрезе Силова 207

Ферма 237

Форда и Фалкерсона 158

Холла и система различных представителей 189-190 Эйлера

о графах 130

о числах 237 Теория чисел 227-239 Точки сочленения 181 Транспозиции подстановки 210-212 Транспортная сеть 156 поток 156

максимальный 158-160

насыщенный 158 пропускная способность 156

разрез 157 Факторгруппа 201 Ферма теорема 237 Формула

бинома Ньютона 19

обращения Мёбиуса 238-239

полиномиальная 18

Фундаментальное множество циклов

172-177 Функция

Мёбиуса (свойства) 238-239 производящая 39

Эйлера (свойства) 234-235

Характеристический

вектор последовательности 25

полином (уравнение) 50

Хроматические графы 194-195 Циклическая группа 200-201 Цикловой индекс группы 217 Цикловая структура групп

подстановок 224-226 Эйлеров граф 130-136 Эйлерова теорема о числах 237 Эйлерова функция (свойства) 234-236 Эратосфеново решето 228-231

простые числа 228