Дискретная математика

УДК 519.95 (075.8)
ББК 22.18
Р 33

Р е д ь к и н Н. П. Дискретная математика. — М.: ФИЗМАТЛИТ,
2009. — 264 с. — ISBN 978-5-9221-1093-8.

В учебнике представлен основной материал обязательного курса
«Дискретная математика», читающегося на механико-математическом
факультете МГУ с 1998 г. В сжатой форме он содержит для первоначального ознакомления ряд важных разделов дискретной математики:
комбинаторный анализ, графы и сети, важнейшие классы управляющих
систем, тесты, алгоритмы, кодирование, дискретные экстремальные
задачи. К каждой главе приведены задачи, самостоятельное решение
которых будет способствовать более глубокому усвоению теоретического материала и лучшей подготовке к экзамену.
Для студентов и аспирантов.
Рекомендовано УМО по классическому университетскому образованию в качестве учебника для студентов высших учебных заведений, обучающихся по направлениям подготовки 010100 «Математика»,
010200 «Математика. Прикладная математика», 011000 «Механика.
Прикладная математика».

ISBN 978-5-9221-1093-8

c⃝ ФИЗМАТЛИТ, 2009

c⃝ Н. П. Редькин, 2009

ОГЛАВЛЕНИЕ

Предисловие . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
7

Г л а в а I.
Элементы комбинаторики . . . . . . . . . . . . . . . . . . . .
9
§ 1. Комбинаторные объекты и комбинаторные числа . . . . . . . .
9
§ 2. Формула включения-исключения. Производящие функции
и возвратные последовательности . . . . . . . . . . . .. . . . . . . . .
12

Г л а в а II.
Графы и сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
§ 1. Элементы графа. Подграфы. Способы задания графов . . . .
19
§ 2. Геометрическая реализация графов. Верхняя оценка числа
неизоморфных графов с m рёбрами . . . . . . . . . . . . . . . . . . .
22
§ 3. Деревья. Характеристические свойства деревьев . . . .. . . . .
23
§ 4. Верхняя оценка числа неизоморфных корневых деревьев с
m рёбрами . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . .
26
§ 5. Теорема Кэли о числе деревьев с занумерованными вершинами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
§ 6. Двудольные графы. Паросочетания и трансверсали. Теорема Холла. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .
29
§ 7. Сети. Потоки в сетях. Теорема Форда–Фалкерсона . . . . . .
32

Г л а в а III.
Булевы функции и формулы . . . . . . . . . . . . . . . .
40
§ 1. Булевы функции. Элементарные булевы функции. . . . . . . .
40
§ 2. Формулы и функции, реализуемые формулами. Простейшие
эквивалентности . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . .
42
§ 3. Разложение булевых функций. Дизъюнктивные нормальные формы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
§ 4. Полнота систем булевых функций. Представление булевых
функций полиномами Жегалкина . . . . . . . . . . . . . . . . . . . .
47
§ 5. Функции k-значной логики . . . . . . . . . . . . . . . . . . . . . . . .
49

Оглавление

Г л а в а IV.
Предикаты. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
§ 1. Высказывания,
предикаты,
кванторы.
Геометрический
смысл кванторов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
§ 2. Модель, сигнатура модели, формулы в модели. Свободные
и связанные переменные . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
§ 3. Истинность формулы в модели, на множестве. Тождественно истинные формулы . . . . . . . . . . . . . . . . . .. . . . . . . . . . . .
56
§ 4. Эквивалентность формул. Правила преобразования формул
с кванторами. . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .
57
§ 5. Приведённые формулы . . . . . . . . . . . . . . . .. . . . . . . . . . . .
60
§ 6. Нормальные формулы . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63

Г л а в а V.
Схемы из функциональных элементов. Синтез и
оценки сложности схем. . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
§ 1. Схемы из функциональных элементов в базисе {&, ∨,− } . .
65
§ 2. Синтез схем с использованием совершенных д.н.ф. . . . .. . .
69
§ 3. Метод Шеннона . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . .
70
§ 4. Асимптотически оптимальный метод синтеза схем (метод
Лупанова) . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .
72
§ 5. Мощностной метод получения нижней оценки для сложности схем . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .
75

Г л а в а VI.
Тесты. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
80
§ 1. Полные диагностические тесты для таблиц. Оценки длины
тестов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
80
§ 2. Тесты для схем. Построение минимальных тестов методом
Яблонского . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82
§ 3. Верхние оценки длины единичных тестов для схем . . . . .. .
88
§ 4. Синтез легкотестируемых схем . . . . . . . . . . . .. . . . . . . . . .
89

Г л а в а VII.
Ограниченно-детерминированные
функции
и
реализация их автоматами . . . . . . . . . . . . . . . . . . . . . . . . .
92
§ 1. Детерминированные
и
ограниченно-детерминированные
функции . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .
92
§ 2. Способы задания ограниченно-детерминированных функций. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . .
97
§ 3. Схемы автоматов из функциональных элементов и элементов задержки . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . .
99

Оглавление
5

Г л а в а VIII.
Алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
§ 1. Алгоритмы. Машины Тьюринга. Задание машины системой
команд . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
§ 2. Композиции машин. Тезис Тьюринга . . . . . . . . . . . . . . . . . 105
§ 3. Проблема самоприменимости. Теорема о самоприменимости 106

Г л а в а IX.
Кодирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
§ 1. Алфавитное кодирование. Разделимые коды. Свойство префикса . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 109
§ 2. Неравенство Крафта–Макмиллана. . . . . . . . . . .. . . . . . . . . 112
§ 3. Коды с минимальной избыточностью. Оптимальное кодирование Хаффмена . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 115
§ 4. Самокорректирующиеся коды. Коды Хэмминга. . . . . . . . . . 120
§ 5. Геометрические свойства
самокорректирующихся кодов.
Оценки Хэмминга и Гильберта . . . . . . . . . . . . . . . . . . . . . . 123

Г л а в а X.
Дискретные экстремальные задачи . . . . . . . . . . . . 127
§ 1. Задача на покрытие. Точное решение задачи на покрытие
127
§ 2. Градиентный алгоритм поиска приближённого решения.
Оценка сложности градиентного покрытия. . . . . . . . .. . . . . . 129
§ 3. Задача о минимальном остовном дереве. . . . . . . . .. . . . . . . 133
§ 4. Поиск кратчайшего и надёжного путей в графе . . . . . . . . . 135
§ 5. Точное решение задачи на покрытие методом динамического программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
§ 6. Приближённое решение задачи об упаковке в контейнеры
141
§ 7. Классы P и NP. Полиномиальная сводимость задач . . . . . 143

Зaдачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
К главе I. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . 151
К главе II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
К главе III. . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . 155
К главе IV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
К главе V . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 160
К главе VI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
К главе VII . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 164
К главе VIII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
К главе IX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
К главе X . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 171

Оглавление

Ответы, указания, решения . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
К главе I. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . 175
К главе II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
К главе III. . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . 186
К главе IV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
К главе V . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 203
К главе VI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
К главе VII . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 224
К главе VIII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
К главе IX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
К главе X . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 254

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261

Светлой памяти моего учителя
Олега Борисовича Лупанова
посвящается

Предисловие

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

Предисловие

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

Г л а в а I

ЭЛЕМЕНТЫ КОМБИНАТОРИКИ

§ 1. Комбинаторные объекты и комбинаторные числа

В комбинаторном анализе изучаются различные объекты, порождаемые элементами из конечного множества A = {a1, ... , an},
и числовые характеристики этих объектов. Часто рассматриваются, например, упорядоченные или неупорядоченные подмножества множества A, подмножества с повторяющимися элементами
из множества A и т. п. Вместе с классами таких комбинаторных объектов естественным образом вводятся и так называемые
комбинаторные числа, задающие число объектов в том или ином
классе и зависящие от некоторых параметров, например, от мощностей исходного множества A и рассматриваемых подмножеств
множества A.
Размещения элементов. Пусть A = {a1, ... , an}. Размещением элементов из A по k (или размещением из n элементов
по k) называется упорядоченное подмножество из k элементов
множества A.
Для A = {a1, a2, a3, a4} размещениями из A по 3 будут, например, {a1, a3, a4}, {a3, a4, a1}, {a2, a3, a4}.
Обозначим число размещений из n элементов по k через (n)k.
При построении конкретного размещения первым элементом в
нём можно взять любой из n элементов множества A, вторым
элементом — любой из n − 1 оставшихся в A элементов и т. д.
Поэтому

(n)k = n(n − 1) ... (n − k + 1) при 1 ⩽ k ⩽ n.

При k > n не существует размещений из n по k, следовательно,
(n)k = 0 при k > n; при k = 0 полагаем (0)0 = (n)0 = 1. Нетрудно
заметить, что для чисел (n)k выполняются тождества:

(n)k =n(n − 1)k−1,
(n)k =(n)k−1 · (n − k + 1).

Гл. I. Элементы комбинаторики

Перестановки элементов. Перестановками элементов множества A = {a1, ... , an} (или перестановками из n элементов)
называются всевозможные упорядоченные множества из n элементов a1, ... , an.
Для A = {a1, a2, a3} перестановками будут, например, {a1, a3,
a2}, {a2, a1, a3}, {a2, a3, a1}.
Перестановки из n элементов — частный случай размещений
из n элементов по n. Поэтому

(n)n = n(n − 1) ... 2 · 1 = n!

Как обычно, полагаем 0! = 1.
Сочетания элементов. Сочетанием элементов из A = {a1, ...
... , an} по k (или сочетанием из n элементов по k) называется
неупорядоченное подмножество из k элементов множества A.
Для A = {a1, a2, a3} всевозможными сочетаниями по 2 элемента будут {a1, a2}, {a1, a3}, {a2, a3}.
В сочетании, в отличие от размещения, порядок следования
элементов не учитывается. Поэтому из одного сочетания (из n
элементов по k) получается k! размещений. Отсюда для числа
n
k
сочетаний из n элементов по k получается формула
n
k

= (n)k

k!
= n(n − 1) ... (n − k + 1)

k!
=
n!

k!(n − k)!

(0 ⩽ k ⩽ n; вместо
n
k
часто используется также обозначение Ck
n). Из последней формулы следует
0
0

=
n
0

=
n
n

= 1 и
n
k

=
n
n − k

.

Для случая k > n полагаем
n
k
= 0, поскольку при k > n не существует сочетаний из n элементов по k.
Числа
n
k
фигурируют в функциональном тождестве, называемом формулой для бинома Ньютона:

(1 + x)n =
n
0

+
n
1

x + ... +
n
k

xk + ... +
n
n

xn.
(1)

В правой части данного тождества коэффициент при xk есть количество способов, которыми можно выбрать из k скобок (1 + x)
переменную x, а из остальных скобок 1, что даёт ровно
n
k
слагаемых.

§ 1. Комбинаторные объекты и комбинаторные числа
11

Полагая в (1) x = 1, получим тождество
n
0

+
n
1

+ ... +
n
k

+ ... +
n
n

= 2n;
(2)

при x = −1 получим
n
0

−
n
1

+ ... + (−1)n
n
n

= 0.
(3)

Из соотношений (2) и (3) следуют тождества
n
0

+
n
2

+ ... +
n
n

=
n
1

+
n
3

+ ... +
n
n − 1

= 2n−1

при чётном n и
n
0

+
n
2

+ ... +
n
n − 1

=
n
1

+
n
3

+ ... +
n
n

= 2n−1

при нечётном n.
Сочетания с повторениями элементов. Сочетанием с повторениями элементов из A = {a1, ... , an} по k (или сочетанием
с повторениями из n элементов по k) называется неупорядоченный набор из k элементов множества A, в котором элементы
могут повторяться.
Для A = {a1, a2, a3} всевозможными сочетаниями с повторениями по 2 элемента будут (a1, a1), (a1, a2), (a1, a3), (a2, a2),
(a2, a3), (a3, a3).
Обозначим через Hk
n число сочетаний с повторениями из n
элементов по k; найдём это число.
Пусть a — произвольное сочетание с повторениями элементов
из A = {a1, ... , an} по k. Этому сочетанию поставим в соответствие набор α(a) длины n + k − 1 из n − 1 нулей и k единиц.
В наборе α(a) число единиц, находящихся между (i − 1)-м и i-м
нулями (i = 2, ... , n − 1), равно числу элементов ai, входящих
в сочетание a, а число единиц, стоящих перед первым нулём (после последнего нуля), равно числу элементов a1 (соответственно
элементов an), входящих в сочетание a. Указанное соответствие
между сочетаниями a и наборами α(a) взаимно однозначно.
Различных наборов длины n + k − 1, содержащих n − 1 нулей
и k единиц, имеется ровно
n+k−1
k
штук, поскольку каждому
такому набору можно взаимно однозначно сопоставить сочетание
из n + k − 1 элементов по k. В итоге получаем

Hk
n =
n + k − 1
k

.

Гл. I. Элементы комбинаторики

§ 2. Формула включения-исключения. Производящие
функции и возвратные последовательности

Рассмотрим — главным образом с иллюстративной целью —
несколько способов подсчёта комбинаторных чисел.
Формула включения-исключения. Пусть имеется m предметов и n различных свойств, которыми могут обладать эти
предметы. Пусть m(i1, ... , ik) — число предметов, обладающих
i1-м, ... , ik-м свойствами. В таком случае число m0 предметов, не
обладающих ни одним из n свойств, определяется по следующей
формуле включения-исключения:

m0 = m −

n
i=1
m(i) +
1⩽i1<i2⩽n
m(i1, i2) − ... +

+ (−1)l
1⩽i1<...<il⩽n
m(i1, i2, ... , il) + ... + (−1)nm(1, 2, ... , n).
(1)

Формулу (1) можно получить, например, индукцией по n.
При n = 1 имеем m0 = m − m(1), т. е. формула (1), очевидно, справедлива. Предположим, что формула (1) справедлива
для (n − 1) свойств. Пусть m(i1, ... , ik) — число предметов, не
обладающих ни одним из свойств i1, ... , ik. По предположению
индукции имеем

m′
0 = m(1, ... , n − 1) = m −

n−1
i=1
m(i)+

+
1⩽i1<i2⩽n−1
m(i1, i2) − ... + (−1)n−1m(1, 2, ... , n − 1).
(2)

Эта формула справедлива и для отдельно взятой совокупности
предметов, обладающих n-м свойством, т. е.

m(1, ... , n − 1, n) = m(n) −

n−1
i=1
m(i, n)+

+
1⩽i1<i2⩽n−1
m(i1, i2, n) − ... + (−1)n−1m(1, 2, ... , n − 1, n),
(3)

где m(1, ... , n − 1, n) — число предметов, обладающих свойством n, но не обладающих ни одним из свойств 1, ... , n − 1. Как
нетрудно заметить,

m(1, ... , n − 1, n) = m(1, ... , n − 1) − m(1, ... , n − 1, n).

§ 2. Формула включения-исключения
13

Отсюда следует, что формула (1) получается вычитанием формулы (3) из (2).
З а м е ч а н и е. Формулу включения-исключения можно интерпретировать ещё и таким образом. Множество всех m предметов обозначим через A, а через Ai обозначим подмножество всех
предметов, обладающих i-м свойством (i = 1, ... , n; понятно, что
подмножества A1, ... , An могут быть совершенно произвольными). В этом случае формула включения-исключения запишется
так:

|A \ (A1 ∪ ... ∪ An)| = |A| −

n
i=1
|Ai| +
1⩽i1<i2⩽n
|Ai1 ∩ Ai2| − ... +

+ (−1)l
1⩽i1<...<il⩽n
|Ai1 ∩ Ai2 ∩ ... ∩ Ail| + ... +

+ ... + (−1)n|A1 ∩ ... ∩ An|.

Производящие функции часто используются при нахождении комбинаторных чисел и при установлении комбинаторных
тождеств.
Пусть имеется последовательность a0, a1, ... , ak, ... Этой последовательности сопоставим ряд

∞
k=0
aktk

(для конечной последовательности a0, a1, ... , ak указанный ряд
превращается в многочлен). В ряде случаев, например, при определённых ограничениях, данный ряд может оказаться сходящимся и задавать некоторую функцию A(t):

A(t) =

∞
k=0
aktk.

Эта функция A(t) называется производящей для последовательности {ak}. Если производящая функция A(t) известна и
допускает разложение в ряд Маклорена, причём единственным
образом, то этим обстоятельством можно воспользоваться для
нахождения комбинаторных чисел ai.
Проиллюстрируем сказанное на следующем простом примере.
Предположим, что нужно найти
n
k
. Нетрудно заметить, что

Гл. I. Элементы комбинаторики

из правил возведения в степень и определения числа сочетаний
из n элементов по k следует равенство

(1 + t)n = 1 +
n
1

t + ... +
n
k

tk + ... +
n
n

tn;

правую часть данного равенства формально можно рассматривать как некоторый ряд, а выражение в левой части равенства —
как производящую функцию для данного ряда. Легко заметить,
что функция (1 + t)n допускает разложение в ряд Маклорена,
причём единственным образом:

(1 + t)n = 1 + n

1!t + n(n − 1)

2!
t2 + ... +

+ n(n − 1) · ... · (n − k + 1)

k!
tk + ... + n(n − 1) · ... · 2 · 1

n!
tn.

В силу единственности разложения коэффициенты при tk в обоих полученных выражениях для (1 + t)n должны быть равны,
т. е.
n
k

= n · (n − 1) · ... · (n − k + 1)

k!
.

Второй пример. С помощью производящих функций установим тождество
2n
n

=

n
k=0

n
k

2
.

Для этого возьмём тождество

(1 + t)2n = (1 + t)n(1 + t)n

и разложим функции (1 + t)2n и (1 + t)n в левой и в правой
частях этого тождества в ряды:

2n
i=1

2n
i

ti =

n
k=0

n
k

tk
n
m=0

n
m

tm
.

Сравнивая коэффициенты при tn в левой и в правой частях
последнего тождества, получаем
2n
n

=

n
k=0

n
k

n
n − k

=

n
k=0

n
k

2
.

Возвратные последовательности. При решении многих задач (и не только комбинаторного характера) возникают рекур

§ 2. Формула включения-исключения
15

рентные соотношения. Рассмотрим те из них, которые приводят
к так называемым возвратным последовательностям.
Последовательность a0, a1, ... , an, ... называется возвратной
последовательностью степени k, если для некоторого k и
всех n выполняется соотношение

an+k + p1an+k−1 + ... + pkan = 0,
(4)

где коэффициенты pi (i = 1, ... , k) не зависят от n. Многочлен

P(x) = xk + p1xk−1 + ... + pk
(5)

называется характеристическим для возвратной последовательности (4). Сформулируем и докажем несколько утверждений,
в совокупности позволяющих находить решения рекуррентных
соотношений вида (4).
У т в е р ж д е н и е 1. Возвратная последовательность степени k полностью определяется заданием её первых k членов
и соотношением (4).
Д о к а з а т е л ь с т в о легко получается индукцией по n. Первые k членов известны по условию. Далее согласно (4) каждый
последующий член последовательности однозначно находится
по k предыдущим:

an+1 = −p1an − p2an−1 − ... − pkan−k+1.

У т в е р ж д е н и е 2. Если λ является корнем характеристического многочлена, то последовательность {λn} удовлетворяет соотношению (4).
Д о к а з а т е л ь с т в о.
Требуется
доказать,
что
λn+k +
+ p1λn+k−1 + ... + pkλn = 0,
или,
что
то
же
самое,
λn(λk + p1λk−1 + ... + pk) = 0. По условию λ является корнем
многочлена (5), и выражение в скобках обращается в 0.
У т в е р ж д е н и е 3. Если λ1, ... , λk — простые корни характеристического многочлена (5), то общее решение рекуррентного соотношения (4) представимо в виде

an = c1λn
1 + ... + ckλn
k,

где c1, ... , ck — произвольные константы.
Д о к а з а т е л ь с т в о. Заметим, что если последовательности {an} и {bn} удовлетворяют соотношению (4), то и последовательность {dn}, где dn = an + bn, удовлетворяет соотношению (4). Отсюда и из предыдущего утверждения следует, что
an = c1λn
1 + ... + ckλn
k удовлетворяет соотношению (4).
Убедимся теперь, что любая последовательность {an}, удовлетворяющая (4), может быть представлена в виде an = c1λn
1 +