Предисловие

Посвящается Леонарду Эйлеру (1707-1783)

В ОСНОВУ ЭТОЙ КНИГИ положен одноименный курс лекций, который ежегодно читается в Станфордском университете, начиная с 1970 года. Каждый год его слушателями становятся около пятидесяти человек — студентов предпоследнего и последнего курсов, но, в основном, дипломников, — а ряд наших выпускников уже начал насаждать подобные курсы и в других местах. Так что настала, видимо, пора ознакомить с материалами курса более широкую аудиторию (включая младшекурсников).

Конкретная математика зарождалась в смутное и неспокойное десятилетие. В те бурные годы казавшиеся незыблемыми ценности постоянно подвергались сомнениям: студенческие городки превращались в очаги жарких дискуссий. Оспаривались сами учебные программы, и математика не стала исключением. Как раз в то время Джон Хаммерсли написал полемическую статью „О снижении уровня математической подготовки в школах и университетах благодаря ‘современной математике’ и подобной ей жидкой интеллектуальной похлебке" [330]; другие обеспокоенные математики [279] даже задавались вопросом: „Можно ли спасти математику?" Когда один из авторов настоящей книги задумал серию книг под названием Искусство программирования для ЭВМ, то при написании первого тома он (Д. Э.К.) обнаружил, что в его арсенале отсутствуют важные математические инструменты: математика, которая требовалась для досконального, обоснованного истолкования компьютерных программ, совершенно отличалась от той, которую автор изучал в колледже в качестве профилирующей дисциплины. Поэтому он ввел новый курс, содержащий материал, который он, в свое время, предпочел бы прослушать сам.

С самого начала название курса — „конкретная математика" — подразумевало его противопоставление „абстрактной математике", поскольку конкретные классические результаты стремительно вымывались из современного математического образования новой волной абстрактных идей, популярно именовавшихся „новой маткой! Абстрактная математика — чудесный предмет, и в ней нет ничего плохого: она красива, обща и полезна. Однако ее приверженцы впали в заблуждение, что вся остальная математика занимает более низкое положение и далее не заслуживает внимания. Погоня за обобщениями оказалась столь захватывающей, что целое поколение математиков потеряло способность находить

прелесть в частностях, в том числе получать удовольствие от решения численных задач или оценить по достоинству роль математических методов. Абстрактная математика стала вырождаться и терять связь с действительностью — математическое образование нуждалось в конкретном противовесе для восстановления устойчивого равновесия.

Когда Д. Э. К. приступал к чтению курса конкретной математики в Станфорде, он объяснял несколько странное название курса тем, что это попытка преподавания математики в стиле „хард“ вместо „софт“ Он объявил, что вопреки ожиданию некоторых его коллег он не собирается излагать ни теорию агрегатов Вейрштрасса, ни теорему вложения Стоуна, ни даже компактификацию Стоуна—Чеха. (Несколько студентов с факультета гражданского строительства поднялись со своих мест и потихоньку покинули аудиторию.)

Хотя конкретная математика возникла в качестве реакции на другие тенденции в математике, основные причины ее появления скорее позитивны, нежели негативны. И по мере того как этот курс продолжал занимать надлежащее место в учебном процессе, содержание предмета „отвердевало" и доказывало свою ценность в целом ряде новых приложений. Тем временем поступило другое независимое подтверждение уместности подобного наименования курса: 3. А. Мелзяк опубликовал два тома Справочника по конкретной математике [216].

На первый взгляд, содержание конкретной математики может показаться беспорядочным нагромождением уловок, но на деле — это упорядоченный набор инструментов. Более того, методы конкретной математики обладают не только внутренним единством, но и внешней привлекательностью. Когда другой автор этой книги (Р. Л. Г.) впервые прочитал данный курс в 1979 г., студенты пришли в такой восторг, что договорились продлить это удовольствие на следующий год.

Но что же в действительности представляет собой конкретная математика? Это смесь континуальной и дискретной математики. Еще более конкретно: это осмысленное оперирование математическими формулами с использованием определенного набора методов решения задач. После того как вы, читатель, изучите материал этой книги, все, что вам потребуется, - это ясная голова, большой лист бумаги и сносный почерк для вычисления ужасных сумм, решения запутанных рекуррентных соотношений и выявления коварных закономерностей в данных. Вы овладеете алгебраической техникой в такой степени, что зачастую вам будет проще получить точные результаты, нежели удовлетвориться приближенными ответами, которые справедливы лишь в пределе.

Исчисление сумм, рекуррентные соотношения, элементарная теория чисел, биномиальные коэффициенты, производящие функции, дискретная теория вероятностей и асимптотические методы — вот наиболее важные темы этой книги. При этом предпочтение отдается технической стороне дела, а не теоремам существования

или комбинаторным рассуждениям: наша цель состоит в том, чтобы сделать каждого читателя настолько осведомленным в дискретных операциях (типа вычисления функции „наибольшего целого" или конечной суммы), насколько изучающие анализ знакомы с непрерывными операциями (типа вычисления функции „абсолютной величины" или определенного интеграла).

Заметим, что этот перечень тем совершенно отличается от того, что в наши дни обычно читается в качестве спецкурсов под названием „Дискретная математика" Поэтому наш предмет нуждается в отличительном наименовании, и название „Конкретная математика", право, не хуже любого другого.

Первоначальным руководством по конкретной математике для станфордского курса служил раздел „Математическое введение" из Искусства программирования для ЭВМ [139]. Но изложение на тех 110 страницах было слишком сжатым, поэтому еще один автор книги (О. П.) загорелся желанием составить длинный ряд дополнений. Настоящая книга выросла на их почве: она одновременно предваряет и дополняет материал „Математического введения" Некоторые вопросы повышенной сложности были опущены; в то же время в книгу включено несколько тем, которых не было раньше и без которых изложение было бы неполным.

Авторы с удовольствием объединили свои усилия для работы над этой книгой, поскольку ее предмет начал зарождаться и обретать свою собственную жизнь на наших глазах; кажется, что книга написана как бы сама собой. Более того, отчасти разнородные подходы, которые выбирал каждый из нас, оказались после стольких лет совместной работы настолько плотно подогнанными друг к другу, что мы не могли удержаться от ощущения, что эта книга — своего рода манифест единодушно выбранного нами пути занятий математикой. Поэтому мы полагаем, что наша книга прозвучит одой математической красоте и очарованию, и надеемся, что наши читатели разделят с нами хотя бы того удовольствия, которое мы испытали при ее написании.

Поскольку книга родилась в университетской среде, мы попытались передать дух аудитории наших дней, выбрав неформальный стиль изложения. Есть люди, полагающие, что математика — это нудное занятие, которое всегда уныло и скучно; мы же находим математику развлечением и не стыдимся признаться в этом. К чему проводить четкую грань между делом и игрой? Конкретная математика полна тому примеров: действия не всегда доставляют удовольствие, но результаты могут быть удивительно приятны. Радости и горести математической работы явно присутствуют в этой книге, поскольку являют собой части нашего бытия.

Студенты всегда умнее своих учителей, поэтому мы попросили изучавших впервые этот материал откровенно поделиться своим мнением в форме „граффити" на полях. Некоторые из их маргиналий были попросту банальны, некоторые не лишены смысла: одни предупреждали о двусмысленностях или неясностях,

другие были типичными комментариями умников с последних рядов. Часть замечаний позитивна, часть — негативна, ценность остальных равна нулю. Но все они, несомненно, отражают реальные чувства читателей, что должно облегчить восприятие книги. (Вдохновляющая идея для подобных маргинальных пометок почерпнута из Справочника для поступающих в Станфорд, где официальной линии университета противопоставляются ремарки покидающих его студентов. К примеру, справочник гласит: „Есть несколько вещей, которые нельзя пропустить в таком аморфном образовании, каковым является Станфорд", а на полях помечено: „Образование, блин! Кругом одни псевдоинтеллектуалы" Справочник: „Потенциал группы совместно проживающих студентов безграничен" Граффити: „Станфордские общаги — это зверинец без смотрителя")

На полях также цитируются знаменитые математики прошлого — подлинные слова, которыми они сопровождали некоторые свои фундаментальные открытия. Отчего представляется уместным свести воедино высказывания Лейбница, Эйлера, Гаусса и других с высказываниями тех, кому предстоит продолжить их дело в будущем? Математика по-прежнему продолжает привлекать своих приверженцев — из многих нитей сплетается богатое полотно!

Книга содержит более 500 упражнений, разбитых на шесть категорий:

• разминочные упражнения, которые должен попытаться выполнить каждый читатель при первом чтении книги;

• обязательные упражнения, предназначенные для установления фактов, которые лучше всего усваиваются, если их выводить самостоятельно, а не читать о том, как это сделали другие;

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

• контрольные работы, обычно охватывающие материал двух и более глав одновременно, в основном они предназначены для выполнения дома (а не в аудитории при нехватке времени);

• конкурсные задачи, превышающие возможности, которые предполагаются у среднего студента, изучающего курс конкретной математики на базе этой книги, — они продвигают изложение в важных направлениях;

• исследовательские проблемы, разрешимые или неразрешимые человеком, но те из них, что предложены в книге, наверное следует попробовать решить (без ограничения времени).

Ответы ко всем этим упражнениям приводятся в приложении А, зачастую с дополнительной информацией о родственных результатах.

татах. (Разумеется, „ответы" на исследовательские проблемы являются неполными, но даже в этих случаях могут оказаться полезными частичные результаты или указания.) Читателям не возбраняется заглянуть в ответы главным образом разминочных задач, но только после серьезных попыток решить задачу без заглядывания украдкой в ответы.

В приложении С мы постарались воздать должное первоисточникам каждого упражнения, поскольку составление той или иной поучительной задачи зачастую является весьма творческим процессом с некоторой долей везения. К сожалению, у математиков сложилась традиция заимствовать упражнения без выражения какой бы то ни было признательности; мы полагаем, что гораздо лучше противоположная традиция, практикуемая, например, в шахматных книгах и журналах (где заведен порядок специально оговаривать авторов, дату и место появления оригинальных шахматных задач). Как бы то ни было, мы не смогли выявить источники многих задач, ставших частью математического фольклора. Если кому-нибудь из читателей известно о происхождении того или иного упражнения, ссылка на которое нами пропущена или неточна, мы были бы рады узнать об этом подробнее, с тем чтобы восполнить подобный пробел в последующих изданиях этой книги.

Шрифт, которым набраны математические обозначения в книге — это новая разработка Германа Цапфа [159], заказанная Американским математическим обществом и выполненная при содействии комиссии, в состав которой вошли Б. Битон, Р. П. Боас, Л. К. Дерст, Д. Э. Кнут, П. Мёрдок, Р. С. Пале, П. Ренц, Э. Свенсон, С. Б. Уидден и У. Б. Вульф. Основная идея дизайна Цапфа — отразить особенности написания математических знаков идеальным почерком. Рукописный стиль в отличие от механического более естествен, поскольку математические формулы обычно выходят из-под карандаша, ручки или куска мела. (Примером одного из фирменных знаков этого нового дизайна является начертание символа нуля, ‘О’, который слегка заострен сверху, поскольку рукописный нуль редко закругляется в исходной точке гладко.) Буквы расположены прямо, а не наклонно, с тем чтобы нижние и верхние индексы, а также штрихи, было легче совмещать с обычными символами. Новое семейство шрифтов получило название в честь великого швейцарца Леонарда Эйлера (1707-1783), открывшего так много в математике из того, что мы сегодня знаем. Алфавиты включают в себя текстовые готические и рукописные прописные ( буквы, а также греческие буквы и спецзнаки типа . Нас особенно радует возможность торжественно представить эйлерово семейство шрифтов в нашей книге, поскольку дух Леонарда Эйлера живет поистине на каждой ее странице: конкретная математика — это эйлерова математика!

Авторы чрезвычайно признательны Андрею Бродеру, Эрнсту

Мэйру, Эндрю и Фрэнсис Яо, внесшим значительный вклад в эту книгу в те годы, когда они преподавали конкретную математику в Станфорде. Кроме того, мы выражаем 1024 благодарности ассистентам, творчески подошедшим к записи происходившего в аудитории каждый год и помогавшим составлять экзаменационные вопросы; их имена перечислены в приложении С. Эта книга, представляющая в сущности компендиум всего ценного, прозвучавшего на лекциях за шестнадцать лет, была бы невозможной без их первоклассной работы.

И еще многие помогли этой книге стать реальностью. Например, достойны похвалы студенты университетов Брауна и Райса, Колумбийского, Нью-Йоркского, Принстонского и Станфордского университетов, внесшие вклад в отобранные граффйти и оказавшие помощь в вылавливании ошибок первых вариантов этой книги. Наши контакты с издательством Эддисон-Уэсли были особенно эффективны и плодотворны; в частности, мы хотим поблагодарить нашего издателя (Питер Гордон), технического директора (Бет Аронсон), дизайнера (Рой Браун) и редактора (Лин Дюпре). Национальный научный фонд и Отделение военно-морских исследований оказали нам неоценимую помощь. Ширли Грэхем была воистину незаменима при составлении указателя. А сверх того мы хотим поблагодарить наших жен (Фэн, Джилл и Эми) за их терпение, поддержку, ободрение и советы.

Это второе издание отличается новым разделом 5.8, описывающим ряд важных идей, которые Дорон Зильбергер открыл вскоре после выхода первого издания. Кроме того, исправления к первому изданию встречаются почти на каждой странице.

Мы пытались создать безупречную книгу, но мы — небезупречные авторы и поэтому призываем оказать содействие в исправлении допущенных ими ошибок. Мы с признательностью выплатим вознаграждение в сумме 2.56 доллара первому нашедшему любую ошибку, будь то математическая, историческая или типографская.

Мюррей Хилл, Нью Джерси, — Р. Л. Г.

Станфорд, Калифорния, Д. Э. К.

май 1988 и октябрь 1993 О. П.