От Фибоначчи до Эрдёша 7

Предисловие 8

К русскому изданию 14

Значения обозначений 15

1 Возвратные задачи 17
 

1.1 Задача о ханойской башне 17

1.2 Задача о разрезании пиццы 21

1.3 Задача Иосифа Флавия 25
 

Упражнения 34

2 Исчисление сумм 39
 

2.1 Обозначения сумм 39

2.2 Суммы и рекуррентности 43

2.3 Преобразование сумм 48

2.4 Кратные суммы 52

2.5 Общие методы суммирования 60

2.6 Исчисление конечного и бесконечного 66

2.7 Бесконечные суммы 76
 

Упражнения 83

3 Целочисленные функции 88
 

3.1 Пол/потолок: определения 88

3.2 Пол/потолок: применения 91

3.3 Пол/потолок: рекуррентности 101

3.4 'mod': бинарная операция 104

3.5 Пол/потолок: суммы 108
 

Упражнения 117

4 Элементы теории чисел 125
 

4.1 Отношение делимости 125

4.2 Простые числа 129

4.3 Простые примеры 131

4.4 Факториальные факты 135

4.5 Взаимная простота 139

4.6 Отношение сравнимости 148

4.7 Независимые остатки 151

4.8 Дополнительные примеры 154

4.9 Фи- и мю-функции 157
 

Упражнения 169

5 Биномиальные коэффициенты 178
 

5.1 Основные тождества 178

5.2 Необходимые навыки 199

5.3 Специальные приемы 213

5.4 Производящие функции 224

5.5 Гипергеометрические функции 232

5.6 Гипергеометрические преобразования 245

5.7 Частичные гипергеометрические суммы 252

5.7 Механическое суммирование 259
 

Упражнения 271

6 Специальные числа 287
 

6.1 Числа Стирлинга 287

6.2 Числа Эйлера 297

6.3 Гармонические числа 303

6.4 Гармоническое суммирование 309

6.5 Числа Бернулли 313

6.6 Числа Фибоначчи 322

6.7 Континуанты 333
 

Упражнения 341

7 Производящие функции 353
 

7.1 Теория домино и размен 353

7.2 Основные маневры 364

7.3 Решение рекуррентных соотношений 371

7.4 Специальные производящие функции 385

7.5 Свертки 387

7.6 Экспоненциальные производящие функции 399

7.7 Производящие функции Дирихле 405
 

Упражнения 407

8 Дискретная вероятность 418
 

8.1 Определения 418

8.2 Математическое ожидание и дисперсия 424

8.3 Производящие функции случайных величин 432

8.4 Бросание монеты 438

8.5 Хеширование 448
 

Упражнения 464

9 Асимптотика 477
 

9.1 Иерархия 478

9.2 Символ О 481

9.3 Операции с О 488

9.4 Два асимптотических приема 502

9.5 Формула суммирования Эйлера 508

9.6 Завершающее суммирование 515
 

Упражнения 529

А Ответы к упражнениям 537

В Список литературы 651

С Первоисточники упражнений 684
 

Указатели 689
 
Именной указатель 689

Предметный указатель 695

Указатель таблиц 703

Copyright © ЦЭМИ 1996-99 г. 117418, Москва, Нахимовский пр, 47

тел: (095) 129-10-11, факс: (095) 718-96-15 Отправить письмо: director@cemi.rssi.ru