Введение в дискретную математику

С. К. Ландо

ФАКУЛЬТЕТ МАТЕМАТИКИ

ВВЕДЕНИЕ В ДИСКРЕТНУЮ
МАТЕМАТИКУ

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

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

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

ISBN 978-5-4439-0205-0

9 785443 902050 >

С. К. Ландо | ВВЕДЕНИЕ В ДИСКРЕТНУЮ МАТЕМАТИКУ

С. К. Ландо

Введение в дискретную
математику

Электронное издание

Москва
Издательство МЦНМО


УДК .
ББК .
Л

Ландо С. К.
Введение в дискретную математику
Электронное издание
М.: МЦНМО, 
 с.
ISBN ----

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

Подготовлено на основе книги: С. К. Ландо. Введение в дискретную
математику. –– М.: МЦНМО, .

Издательство Московского центра
непрерывного математического образования
, Москва, Большой Власьевский пер., . Тел. () --
http://www.mccme.ru

ISBN ----
© Ландо С. К., .
© МЦНМО, .

Оглавление

От автора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


Часть I
Элементы перечислительной комбинаторики

Глава . Элементарные производящие функции
§1.1. Перестановки и сочетания . . . . . . . . . . . . . . . . . . . . . . . .
11
§1.2. Бином Ньютона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
§1.3. Экспонента . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
§1.4. Производящие функции и действия над ними . . . . . . . . . . .
18
§1.5. Дифференцирование и интегрирование производящих функций 22
§1.6. Алгебра и топология формальных степенных рядов . . . . . . .
25
§1.7. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26

Глава . Рациональные производящие функции
§2.1. Геометрическая прогрессия . . . . . . . . . . . . . . . . . . . . . . .
30
§2.2. Последовательность Фибоначчи . . . . . . . . . . . . . . . . . . . .
31
§2.3. Рекуррентные соотношения и рациональные производящие
функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
§2.4. Неоднородные рекуррентные соотношения . . . . . . . . . . . . .
36
§2.5. Произведение Адамара рациональных производящих функций
38
§2.6. Асимптотика коэффициентов рациональных функций . . . . . .
40
§2.7. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42

Глава . Перечисление путей на графах
§3.1. Пути в графах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
§3.2. Пути, перечисляемые рациональными производящими функциями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
§3.3. Числа Каталана . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
§3.4. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57

Глава . Производящие функции нескольких переменных
§4.1. Треугольник Паскаля . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
§4.2. Экспоненциальные производящие функции
. . . . . . . . . . . .
62
§4.3. Треугольник Дика
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
§4.4. Треугольник Бернулли––Эйлера и перечисление up-down-перестановок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
64
§4.5. Числа Эйлера в треугольнике Дика с кратностями . . . . . . . .
69


Оглавление

§4.6. Производящая функция для треугольника Дика с кратностями
71
§4.7. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72

Глава . Теневое исчисление
§5.1. Определения и примеры . . . . . . . . . . . . . . . . . . . . . . . . .
75
§5.2. Применения биномиальных последовательностей . . . . . . . .
76
§5.3. Биномиальные последовательности и сдвиги
. . . . . . . . . . .
77
§5.4. Явное построение биномиальных последовательностей . . . . .
81
§5.5. Последовательности Шеффера . . . . . . . . . . . . . . . . . . . . .
83
§5.6. Коалгебра многочленов . . . . . . . . . . . . . . . . . . . . . . . . . .
84
§5.7. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
85

Глава . Разбиения
§6.1. Разбиения и разложения . . . . . . . . . . . . . . . . . . . . . . . . .
89
§6.2. Тождество Эйлера . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
94
§6.3. Разбиения множеств в треугольнике Моцкина с кратностями .
96
§6.4. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99

Глава . Производящие функции Дирихле
§7.1. Принцип включения-исключения . . . . . . . . . . . . . . . . . . . 103
§7.2. Производящие функции Дирихле и действия над ними . . . . . 106
§7.3. Обращение Мjбиуса . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
§7.4. Мультипликативные последовательности . . . . . . . . . . . . . . 111
§7.5. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

Часть II
Графы, их перечисление и инварианты

Глава . Перечисление деревьев и лесов
§8.1. Перечисление помеченных деревьев . . . . . . . . . . . . . . . . . 117
§8.2. Леса и многочлены Абеля . . . . . . . . . . . . . . . . . . . . . . . . 126
§8.3. Перечисление посаженных лесов
. . . . . . . . . . . . . . . . . . . 128
§8.4. Обращение функции и суммирование по деревьям . . . . . . . . 130
§8.5. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

Глава . Числа Гурвица
§9.1. Графы и перестановки
. . . . . . . . . . . . . . . . . . . . . . . . . . 135
§9.2. Числа Гурвица . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
§9.3. Уравнение транспозиции . . . . . . . . . . . . . . . . . . . . . . . . . 143
§9.4. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

Глава . Соотношение удаление-стягивание и теорема Татта
§10.1. Графы, изоморфизм и инварианты
. . . . . . . . . . . . . . . . . 146
§10.2. Хроматический многочлен . . . . . . . . . . . . . . . . . . . . . . . 147
§10.3. Немного о топологии графа . . . . . . . . . . . . . . . . . . . . . . 151

Оглавление


§10.4. Многочлен Пенроуза . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
§10.5. Соотношения Татта . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
§10.6. Теорема Татта . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
§10.7. Доказательство теоремы Татта . . . . . . . . . . . . . . . . . . . . 157
§10.8. Новые примеры инвариантов Татта . . . . . . . . . . . . . . . . . 160
§10.9. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

Глава . Алгебра Хопфа графов
§11.1. Алгебра Хопфа графов . . . . . . . . . . . . . . . . . . . . . . . . . . 167
§11.2. Примитивные элементы
. . . . . . . . . . . . . . . . . . . . . . . . 171
§11.3. Факторалгебры биалгебры графов . . . . . . . . . . . . . . . . . . 175
§11.4. 4-инварианты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
§11.5. Оснащенные модификации графовых алгебр . . . . . . . . . . . 182
§11.6. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183

Часть III
Языки, грамматики, автоматы

Глава . Языки и конечные автоматы
§12.1. Язык Дика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
§12.2. Конечные автоматы . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
§12.3. Автоматы со стеком . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
§12.4. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

Глава . Языки и формальные грамматики с однозначным выводом
§13.1. Правила вывода в языке Дика . . . . . . . . . . . . . . . . . . . . . 199
§13.2. Формальные грамматики с однозначным выводом . . . . . . . 201
§13.3. Производящие функции регулярных языков
. . . . . . . . . . . 205
§13.4. Представления производящих функций в виде непрерывных
дробей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
§13.5. Сравнения в последовательностях . . . . . . . . . . . . . . . . . . 211
§13.6. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214

Ответы, указания, решения
Решения задач главы 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
Решения задач главы  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
Решения задач главы  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
Решения задач главы  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
Решения задач главы  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
Решения задач главы  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
Решения задач главы  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
Решения задач главы  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
Решения задач главы  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244


Оглавление

Решения задач главы  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
Решения задач главы  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
Решения задач главы  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
Решения задач главы  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251

Контрольные задания
Задачи зачета . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
Домашняя работа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
Задачи экзамена . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257

Библиографические замечания
. . . . . . . . . . . . . . . . . . . . . . . . . 

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 

Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 

Памяти Филиппа Флажоле
(––)

Дискретную математику можно определить как науку, изучающую конечные множества. При таком определении она становится всепроникающей –– трудно представить себе раздел математики,
не связанный с конечными множествами, –– и необъятной. Поэтому
всякий курс дискретной математики, как начальный, так и более
сложный, поневоле ограничивается какими-то аспектами этой науки. Выбор излагаемых аспектов обычно опирается на вкусы автора.
В настоящем курсе я следовал своим пристрастиям и исследовательскому опыту. Я также стремился связать курс дискретной математики с другими математическими курсами. Так, изучение производящих функций поддерживает изучение разложений функций в ряд
в курсе математического анализа.
Курс разбит на три части. Первые две посвящены перечислительной комбинаторике и графам. В третьей, посвященной конечным автоматам, формальным языкам и грамматикам, дается представление о том, как подходы, описанные в первых двух частях, могут применяться для построения простейших вычислительных моделей. В свою очередь, эти модели дают новые подходы к решению
перечислительных задач. В приложениях даются решения задач, сопровождающих каждую главу, и образцы контрольных и экзаменационных работ.
Разумеется, вводный характер изложения сказывается и на содержании каждой из частей. Так, из всего богатства результатов
о конечных графах я излагаю лишь начальные сведения об их перечислении и инвариантах. В то же время я стремился к тому, чтобы
в изложении присутствовал материал, активно используемый в современных математических исследованиях, например в топологии
и статистической физике.
При работе с конечными объектами –– конечными множествами, графами, словами и т. д. –– ключевую роль играют действующие на них группы, в первую очередь, симметрические группы,
или группы перестановок. Любые другие конечные группы являют


От автора

ся подгруппами в группах перестановок. Свойства объектов в значительной мере определяются комбинаторикой соответствующих
групп, что позволяет этим группам играть связующую роль между
частями книги. Оказывается, однако, что несмотря на многолетние
усилия по изучению конечных групп даже в комбинаторике симметрических групп остается много неизведанного, а некоторые вопросы еще и не поставлены.
В основе первой части книги лежат мои «Лекции о производящих функциях» (первое издание вышло в  г. при поддержке
РФФИ, в  г. издательство Московского центра непрерывного математического образования выпустило их -м изданием, а в  г.
в издательстве Американского математического общества вышел
их перевод на английский язык). Эти лекции читались первокурсникам Независимого Московского университета. Для курса «Введение в дискретную математику», который читается на факультете
математики Высшей школы экономики во втором семестре первого года обучения, они были существенно переработаны, расширены и обогащены новыми задачами. Помимо отдельных параграфов
в эту часть вошла новая глава про теневое исчисление.
В разные годы вместе со мной этот курс вели Г. Л. Рыбников,
А. И. Зыкин и П. Н. Пятов. Многие задачи –– в том числе для контрольных и экзаменационных работ –– предложены ими, и я им
очень благодарен. П. Н. Пятов, кроме того, написал решения целого
ряда задач. Я также благодарен студентам факультета математики
ВШЭ, живая реакция которых позволила, я надеюсь, заметно улучшить первоначальные записки лекций.
Некоторые разделы курса рассчитаны на студентов, уровень
подготовки которых выше среднего. Сюда относятся, в первую очередь, вопросы, связанные со структурами алгебр Хопфа на пространствах многочленов и пространствах графов. Остальной материал не опирается на эти структуры, и их изучение можно безболезненно опустить.

ЧI

ЭГлава 

Элементарные производящие функции

В первой части курса мы займемся задачами перечисления. Они
заключаются в подсчете числа объектов, принадлежащих некоторому семейству конечных множеств. У каждого множества семейства
имеется свой номер, и результатом перечисления служит некоторая
последовательность натуральных чисел. Перечислительные задачи
встречаются во всех областях математики, и в последние годы они
вышли на первый план в алгебраической геометрии, топологии,
многих направлениях математической физики.
Как правило, задача перечислительной комбинаторики «в принципе» разрешима: для каждого множества из семейства можно выписать все его элементы и таким образом узнать их число. Проблема, однако, состоит в том, чтобы найти «хорошее» решение, не
требующее выписывания всех элементов изучаемых множеств. При
этом понять, что такое хорошее решение, довольно трудно. Зачастую удается лишь сравнить два решения и сказать, какое из них
лучше.
Наиболее подходящим языком для решения перечислительных
задач оказывается язык производящих рядов. Операции с комбинаторными объектами очень естественно выражаются в терминах
производящих функций. Однако перечислительная комбинаторика
не сводится к производящим функциям –– привлечение методов из
смежных областей математики (например, из анализа или теории
групп) дает новый взгляд на перечислительные задачи и позволяет
находить неожиданные подходы к их решению.

§ .. Перестановки и сочетания

Будем обозначать число элементов в конечном множестве A через |A|; например, |{4, 5, 7}|=3.
Пусть Nn обозначает множество натуральных чисел от 1 до n,
т. е. Nn = {1, 2, …, n}. Перестановка этого множества –– это его взаимно однозначное отображение в себя, σ: Nn → Nn. Тождественная


Глава . Элементарные производящие функции

перестановка оставляет каждый элемент на месте. Множество всех
перестановок этого множества обозначается через Sn. Композиция
перестановок является перестановкой, и у каждой перестановки
есть обратная –– такая, композиция с которой является тождественной перестановкой. Поэтому множество Sn образует группу.
Подсчитаем количество различных перестановок, т. е. количество элементов в группе Sn. Это количество равно количеству различных взаимно однозначных отображений любых двух множеств
из n элементов (не обязательно одинаковых). Подсчитать их можно, например, так. Группа S1 состоит, очевидно, из одного элемента –– тождественного отображения множества N1 ={1} в себя. Разобьем теперь все взаимно однозначные отображения из Nn в себя
на n подмножеств в зависимости от того, в какой элемент перешел
элемент 1. Все эти n подмножеств содержат одинаковое количество
элементов, и это количество равно количеству взаимно однозначных отображений двух (n −1)-элементных множеств, т. е. числу элементов группы Sn−1. Поэтому

|Sn| = n|Sn−1| = n(n −1)|Sn−2| = … = n ·(n −1)·(n −2)·…·1.

Это число –– произведение всех натуральных чисел от 1 до n –– принято называть факториалом числа n и обозначать n! .
Множество Nn содержит n одноэлементных подмножеств. Нетрудно видеть, что число двухэлементных подмножеств в нем рав
но n(n −1)

2
. Действительно, первый элемент из двух мы можем выбрать n способами, а второй n − 1 способами из еще невыбранных
элементов. Значит, упорядоченную пару элементов можно выбрать
n(n − 1) способами. Поскольку две пары a, b и b, a образуют одно
и то же множество, для подсчета двухэлементных подмножеств
необходимо количество упорядоченных пар поделить на 2.
Как подсчитать число k-элементных подмножеств в Nn для произвольного натурального числа k? Во-первых, очевидно, что при
k > n это число равно 0. Если же k ⩽ n, то будем строить все k-элементные подмножества в Nn следующим образом. Возьмем произвольную перестановку множества Nn, и возьмем первые k элементов в этой перестановке (т. е. те элементы, в которые перешли
1, 2, …, k). Ясно, что таким образом мы получим все k-элементные
подмножества, причем каждое из них будет встречаться одно и то
же количество раз. Это количество раз равно k!(n − k)! , поскольку
перестановки первых k элементов и оставшихся n − k элементов

§ .. Перестановки и сочетания


не меняют выбранное подмножество. Поэтому для подсчета числа k-элементных подмножеств в Nn нужно разделить общее число
перестановок на k!(n − k)! . Полученное число называется числом
сочетаний из n элементов по k и обозначается через
n
k

=
n!

k!(n − k)!.
(.)

(В литературе на русском и французском языках чаще встречается
обозначение Ck
n, однако его использование предполагает, что n ––
натуральное число; мы же будем пользоваться сочетаниями в ситуациях, когда n –– не обязательно натуральное число, что и объ
ясняет наш выбор обозначения
n
k

, принятого в англоязычных

текстах.) Поскольку дополнение k-элементного множества в множестве из n элементов состоит из n − k элементов, количество k-элементных подмножеств в n-элементном множестве равно количеству
(n − k)-элементных подмножеств в нем, что прекрасно подтверждается выведенной нами формулой для числа сочетаний:
n
k

=
n!

k!(n − k)! =
n!

(n − k)!k! =
n
n − k

.

В случае k = n формула для числа сочетаний имеет вид
n
n

=
n!

n!0! = 1

0!.

Поскольку число n-элементных подмножеств в n-элементном множестве, очевидно, равно 1, мы обязаны положить 0!=1. Тогда формула для числа сочетаний приобретает смысл и при k =0:
n
0

=
n!

0!n! = 1

–– в произвольном множестве имеется ровно одно 0-элементное подмножество (пустое множество).
Числа сочетаний –– это в точности коэффициенты, встречающиеся в разложении степеней бинома:

(x+ y)n =
n
0

xn+
n
1

xn−1y+…+
n
k

xn−k yk+…+
n
n

yn. (.)

Действительно,

(x + y)n = (x + y)(x + y)…(x + y),

и коэффициент при xn−k yk в произведении равен количеству k-элементных подмножеств в множестве из n скобок (x + y). Это в точности те скобки, из которых мы выбираем слагаемое y.


Глава . Элементарные производящие функции

Уже это простое наблюдение позволяет вывести нетривиальные
комбинаторные тождества. Например,
n
0

+
n
1

+…+
n
k

+…+
n
n

= 2n,

как результат подстановки x = 1, y = 1 в разложение бинома (.).
(Вот другой вывод того же тождества: 2n –– это общее количество
подмножеств в множестве из n элементов, а в левой части равенства
суммируются количества подмножеств с данным числом элементов.) Точно так же получаем
n
0

−
n
1

+…+(−1)kn
k

+…+(−1)nn
n

= 0
при n > 0.

При нечетном n это равенство очевидным образом следует из сим
метрии
n
k

=
n
n − k

, а вот при четном n его проще всего получить

подстановкой x =1, y =−1 в разложение бинома.
Разложение бинома нам еще не раз встретится в этой книге,
в том числе и в настоящей главе.

§ .. Бином Ньютона

Числитель и знаменатель дроби в формуле (.) для числа сочетаний можно сократить на (n − k)!, переписав ее в виде
n
k

= n(n −1)(n −2)…(n − k +1)

k!
.
(.)

Такое сокращение позволяет расширить круг значений, к которым
она применима –– в качестве аргумента n можно брать произвольное число, не обязательно натуральное. Например,

1/2
k

=

1
2

−1

2

−3

2

−5

2

… 3−2k

2

k!
= (−1)k−11·3·5·… ·(2k −3)

2kk!
.

При таком подходе число сочетаний перестает быть целым и теряет прямой комбинаторный смысл (нельзя сказать, что это число
k-элементных подмножеств в «полуэлементном множестве»). Вообще, число n может быть иррациональным и даже комплексным.
Однако по-прежнему естественно полагать
n
0

= 1

для произвольного n ̸=0.

§ .. Экспонента


Если n натуральное или 0, то при k > n в числителе формулы (.) встречается нулевой множитель, и поэтому все выражение
равно 0. Напротив, если n не является целым неотрицательным чис
лом, то число сочетаний
n
k

не является нулевым ни при каком k.

Такие обобщенные числа сочетаний можно применить для получения разложения бинома в произвольной степени, не только в целой. А именно,

(1+ s)α = 1+
α
1

s +
α
2

s2 +
α
3

s3 +
α
4

s4 +…
(.)

Здесь в обозначениях n заменено на α, чтобы подчеркнуть, что мы
больше не считаем показатель натуральным, а первая переменная
заменена на 1, чтобы не было необходимости решать, что такое x
в ненатуральной степени (1α = 1 для любого показателя α). В случае, если число α является натуральным, разложение (.) совпадает с обычной степенью бинома. Для ненатурального показателя степени оно было введено Ньютоном и представляет собой бесконечный степенной ряд. Этот ряд можно считать определением левой
части (а можно –– и в курсе математического анализа это делается ––
доказывать, что ряд сходится при |s| < 1, причем слева от знака равенства действительно написана функция, к которой он сходится).

Вот пример разложения бинома для α= 1

2:

(1+ s)1/2 = 1+
1/2
1

s +
1/2
2

s2 +
1/2
3

s3 +
1/2
4

s4 +… =

= 1+ 1

2 s − 1

8s2 + 1

16s3 −
5

128s4 +…

§ .. Экспонента

Экспонента является одной из важнейших функций во всей математике. Ее определяющее свойство состоит в том, что она преобразует сумму в произведение. Давайте найдем такую функцию
f = f (s), что тождественно выполняется равенство

f (s + t) = f (s) f (t).
(.)

Подставляя s = 0, t = 0, мы сразу заключаем, что f (0) = f (0) · f (0),
откуда f (0) равняется либо 0, либо 1. Мы рассмотрим только случай
f (0) = 1, оставив случай f (0) = 0 в качестве задачи в конце главы
(см. задачу .).